Modul 4
Hierarki Chomsky & Konversi ke CNF
Klasifikasikan grammar ke dalam Tipe 0-3 menurut Hierarki Chomsky, lalu lihat tahapan lengkap transformasi CFG menjadi Chomsky Normal Form (CNF).
Grammar
Format:
NonTerminal -> alternatif1 | alternatif2, gunakan epsilon untuk produksi
kosong.
Hierarki Chomsky
- Tipe 0 — Tak Terbatas (diterima Mesin Turing)
- Tipe 1 — Sensitif Konteks (diterima LBA)
- Tipe 2 — Bebas Konteks (diterima PDA)
- Tipe 3 — Reguler (diterima DFA/NFA)