Hierarki Chomsky & Chomsky Normal Form
Sejauh ini sudah dipakai dua "level" bahasa formal: bahasa reguler (Modul 1 & 2, dikenali FSA) dan bahasa bebas konteks (Modul 3, dikenali PDA). Noam Chomsky mengurutkan semua bahasa formal jadi empat tingkat berdasarkan seberapa ketat aturan produksinya, dari yang paling longgar (Tipe 0) sampai paling ketat (Tipe 3). Di halaman ini, grammar bebas konteks (Tipe 2) diubah ke Chomsky Normal Form (CNF), sebuah format baku di mana setiap aturan produksi cuma boleh berbentuk dua pola tertentu. Kenapa direpotkan menyeragamkan bentuknya? Karena algoritma pengenal bahasa seperti CYK (dipakai di Modul 3) cuma bisa jalan kalau grammar-nya sudah dalam bentuk CNF.
| Tipe | Nama | Mesin Pengenal | Contoh pada Otomatika |
|---|---|---|---|
| Tipe 0 | Unrestricted Grammar | Mesin Turing | tidak dipakai secara eksplisit |
| Tipe 1 | Context-Sensitive Grammar | Linear Bounded Automaton | tidak dipakai secara eksplisit |
| Tipe 2 | Context-Free Grammar | Pushdown Automaton | Grammar ekspresi aritmatika (Modul 3) |
| Tipe 3 | Regular Grammar | Finite State Automaton | Tokenizer & Regex (Modul 1 & 2) |
Setiap tipe bahasa yang lebih tinggi (angka lebih kecil) mencakup seluruh bahasa di tipe bawahnya (Tipe 3 ⊂ Tipe 2 ⊂ Tipe 1 ⊂ Tipe 0), artinya semua yang bisa dikenali FSA pasti juga bisa dikenali PDA, tapi tidak sebaliknya. Otomatika mendemonstrasikan hubungan Tipe 3 dan Tipe 2 secara langsung: token dari lexer (Tipe 3) menjadi terminal bagi grammar ekspresi (Tipe 2).
A → BC (dua nonterminal) atau
A → a (satu terminal), dengan pengecualian S → ε untuk simbol awal saja.
Konversi dilakukan lima langkah berurutan: START (tambah simbol awal baru), DEL (hilangkan
produksi kosong/ε), UNIT (hilangkan produksi tunggal A → B), hilangkan simbol yang
tidak berguna, lalu TERM+BIN (pastikan tiap aturan cuma dua simbol).