Modul 4

Hierarki Chomsky & Chomsky Normal Form (CNF)

Pahami klasifikasi bahasa formal menurut Noam Chomsky, lalu konversikan CFG Anda menjadi CNF dan uji keanggotaan string menggunakan algoritma CYK.

Hierarki Chomsky
Type 0
Unrestricted Grammar / Recursively Enumerable

Tidak ada batasan bentuk aturan produksi. Ini adalah kelas bahasa paling umum/kuat.

α -> β (α mengandung minimal 1 variabel, β bebas)

Mesin: Turing Machine

Type 1
Context-Sensitive Grammar

Aturan produksi tidak boleh mengurangi panjang string (panjang ruas kanan >= ruas kiri).

αAβ -> αγβ (dengan γ tidak boleh kosong)

Mesin: Linear Bounded Automaton

Type 2
Context-Free Grammar

Ruas kiri produksi harus berupa 1 variabel tunggal. Ini adalah jenis grammar yang dipakai pada modul CFG & PDA.

A -> γ

Mesin: Pushdown Automaton

Type 3
Regular Grammar

Bentuk paling sederhana/terbatas. Setara dengan Regular Expression dan FSA.

A -> aB atau A -> a (right-linear)

Mesin: Finite Automaton (DFA/NFA)

Chomsky Normal Form (CNF):
Bentuk baku CFG di mana setiap produksi berbentuk A → BC (dua non-terminal) atau A → a (satu terminal), kecuali S → ε untuk start symbol. Konversi CFG → CNF melalui 5 langkah: START → TERM → BIN → DEL → UNIT. Bentuk CNF ini memungkinkan pengecekan keanggotaan string secara efisien menggunakan algoritma CYK (Cocke-Younger-Kasami) dengan kompleksitas O(n³).
Definisi CFG

Gunakan "eps" untuk produksi epsilon (ε).
Uji Keanggotaan String (CYK)

Catatan: jalankan konversi CNF terlebih dahulu sebelum menjalankan CYK, karena CYK membutuhkan grammar dalam bentuk CNF.

Langkah Konversi CFG → CNF
Grammar Hasil (CNF)

Tabel CYK (table[panjang][posisi_awal])