Hierarki Chomsky dan Bentuk Normal Chomsky
Klasifikasikan grammar dan konversi ke CNF secara bertahap
Apa itu Hierarki Chomsky dan CNF?
Hierarki Chomsky membagi bahasa formal ke dalam empat tingkatan berdasarkan kompleksitas aturan produksinya - Tipe 0 (paling umum/tak terbatas) hingga Tipe 3 (paling sederhana/reguler). Semakin kecil nomor tipenya, semakin longgar aturannya; semakin besar nomornya, semakin ketat batasannya.
Chomsky Normal Form (CNF) adalah bentuk standar dari CFG di mana setiap aturan produksi hanya boleh berbentuk A → BC (dua simbol non-terminal) atau A → a (satu simbol terminal).
Tujuan mengonversi grammar ke CNF adalah menyederhanakan strukturnya agar lebih mudah diproses oleh algoritma parsing, tanpa mengubah bahasa yang dihasilkan.
Cara menggunakan modul ini
- Tulis aturan produksi grammar, satu baris satu simbol, format
A->produksi1|produksi2. - Tentukan simbol awal (biasanya
S). - Klik "Analisis".
- Sistem akan menampilkan klasifikasi tipe grammar, lalu tahapan konversi menuju CNF satu per satu: eliminasi produksi ε, eliminasi produksi unit, pemisahan terminal, hingga hasil akhir CNF.
Aturan produksi grammar
Huruf besar = non-terminal, huruf kecil = terminal, satu simbol satu karakter. Gunakan ε untuk produksi kosong.