Tata Bahasa Hirarki Chomsky dan Aturan Produksi

Halo teman teman semua, pada artikel ini kita akan membahas mengenai Tata Bahasa, bagaimana itu Hirarki Chomsky dan apa itu Aturan Produksi serta bagaimana aturan yang digunakan pada setiap tipe hirarki chomsky.

Simbol terminal dan non terminal

Apa itu simbol terminal?

• simbol terminal adalah simbol yang tidak dapat diturunkan lagi
• arti bisa diturunkan yaitu misalkan simbol A yang dapat diturunkan menjadi bc

yang termasuk simbol terminal:

• huruf kecil alfabet: a,b,c
• simbol operator: + (tambah), – (kurang)
• simbol tanda baca: , (koma) ! (tanda seru)
• string yang tercetak tebal, misalnya: if, then dan else

Apa itu simbol NON terminal (Variabel)?

• adalah simbol yang masih bisa diturunkan menjadi simbol terminal atau non terminal lainnya

yang termasuk simbol NON terminal (variabel):

• huruf besar alfabet: A, B, C
• huruf S sebagai simbol awal
• String yang tercetak miring misal expr dan stmt

Aturan Produksi

Dalam teori bahasa dan otomata, aturan produksi dinyatakan dalam:

α → β

(dibaca: alpha menghasilkan atau menurunkan beta)

• Dengan menerapkan aturan produksi, suatu tata bahasa bisa menghasilkan sejumlah string.
• Himpunan semua string tersebut adalah bahasa yang didefinisikan oleh tata bahasa tersebut.

contoh aturan produksi:

T → a

(dibaca: T menghasilkan a)

Contoh lain:

E → T | T + E

(dibaca: E menghasilkan T atau E menghasilkan T + E)

Hirarki Chomsky

Grammar

• Grammar atau tata bahasa didefinisikan secara formal sebagai kumpulan dari himpunan himpunan variabel, simbol simbol terminal, simbol awal, yang dibatasi oleh aturan aturan produksi.

4 tingkatan tata bahasa menurut Chomsky:

1. Tipe 0 – Unrestricted Grammar
2. Tipe 1 – Context Sensitive Grammar
3. Tipe 2 – Context Free Grammar
4. Tipe 3 – Regular Grammar

Tipe 0 – Unrestricted Grammar

• Aturan produksinya tidak memiliki batasan
• Dalam aturan α → β pada tipe 0:
  • alpha adalah string terminal dan non-terminal dengan setidaknya 1 non-terminal
  • alpha tidak boleh kosong
  • beta adalah rangkaian simbol terminal dan non – terminal
  • α adalah (V + T)*V(V+T)*
  • β adalah (V+T)*
  • note:
  • (tanda plus ‘+’ dibaca atau)
  • (tanda * (asterisk) yang berarti bisa tidak muncul atau bisa juga muncul hingga berkali kali (0 – n))
• Tipe ini menghasilkan bahasa yang dikenali oleh mesin Turing
• Bahasa ini juga dikenal dengan nama “Recursively Enumerable Languages”.

jadi aturan yang perlu diingat adalah:

• α adalah (V + T)*V(V+T)*
• β adalah (V+T)*

Contoh penerapan aturan tipe 0:

• S → ACaB (Terpenuhi, karena di ruas kiri ada non terminal, di ruas kanan ada terminal dan non-terminal)
• Bc → acB (Terpenuhi, karena di ruas kiri ada non terminal, di ruas kanan ada terminal dan non-terminal)
• CB → DB (Terpenuhi)
• aD → Db (Terpenuhi)
• Sab → ba (Terpenuhi)
• A → S (Terpenuhi)

Tipe 1 – Context Sensitive Grammar

• Aturan produksinya sama dengan tipe 0 namun dibatasi dengan aturan |a|≤|b| (jumlah simbol di ruas kiri harus lebih kecil atau sama dengan jumlah simbol di ruas kanan)
• Aturan S → Ɛ dibolehkan jika S tidak muncul pada ruas kanan setiap aturan
• Menghasilkan bahasa yang dikenali oleh Linear Bound Automata

jadi aturan yang perlu diingat adalah:

• |a|≤|b|
• a adalah (V+T)*V(V+T)*
• b adalah (V+T)* (V+T) (V+T)*

Contoh penerapan:

• S → AB (Terpenuhi)
• AB → abcd (Terpenuhi, ukuran ruas kiri lebih kecil dari ruas kanan)
• B → b (Terpenuhi)
• aD → Db (Terpenuhi, ukuran kedua ruas sama)
• aB → aa | aaAA (Terpenuhi)
• Ac → Bbcc (Terpenuhi)

Tipe 2 – Context Free Grammar

• Aturan produksi ini sama dengan tipe 0 namun a sisi kiri hanya boleh memiliki 1 variabel non terminal (|a| = 1) dan b tidak memiliki batasan
• a adalah sebuah simbol non terminal
• b dapat berupa rangkaian atau simbol terminal, non terminal atau epsilon
• tipe ini menghasilkan bahasa yang dikenali oleh Non Deterministic Push Down Automata

jadi aturan yang perlu diingat adalah:

• |a| = 1
• a adalah V
• b adalah (V+T)*

contoh:

• S → X a (Terpenuhi, di ruas kiri hanya ada satu non terminal yaitu S dan di ruas kanan boleh terminal atau non terminal)
• X → a (Terpenuhi)
• X → aX (Terpenuhi)
• X → abc (Terpenuhi)
• X → Є (Terpenuhi)
• S → AB (Terpenuhi)
• A → a (Terpenuhi, di ruas kiri hanya ada satu non terminal dan di ruas kanan ada satu terminal)
• B → b (Terpenuhi)

Tipe 3 – Regular Grammar

• Aturan S → Ɛ dibolehkan jika S tidak muncul pada ruas kanan setiap aturan
• α adalah sebuah simbol non terminal
• β adalah simbol terminal atau simbol terminal dengan sebuah simbol variabel yang jika ada terletak pada posisi paling kanan
• Menghasilkan bahasa yang dikenali oleh Finite State Automata

jadi perlu diingat:

• α adalah V
• β adalah T* atau T*V

Contoh:

• X → Ɛ
• X a | aY
• Y → b
• S → abB
• B → cd

Kesimpulan

Pada artikel ini kita telah membahas mengenai simbol Terminal dan Non Terminal, kemudian hirarki Chomsky serta Aturan Produksi yang digunakan. Oke teman teman semua terima kasih telah membaca.

Referensi:

Artikel ini merupakan hasil resume dari video PAKKODING (web, youtube).

Video berjudul #3 Teori Bahasa & Otomata – Tata Bahasa Hirarki Chomsky dan Aturan Produksi.

Terima kasih banyak ke pada PAKKODING atas materi yang disampaikan serta cara penyampaiannya yang mudah dipahami.