Contoh Soal Bentuk Normal Chomsky

5 min read Dec 01, 2024

Contoh Soal Bentuk Normal Chomsky (CNF)

Bentuk Normal Chomsky (CNF) adalah bentuk standar dalam tata bahasa formal yang digunakan dalam teori bahasa formal dan kompilasi. CNF membatasi struktur tata bahasa sehingga setiap aturan produksi memiliki salah satu dari dua bentuk berikut:

A → BC, di mana A adalah simbol non-terminal dan B dan C adalah simbol non-terminal (bisa sama).
A → a, di mana A adalah simbol non-terminal dan 'a' adalah simbol terminal.

Tujuan mengubah tata bahasa ke CNF adalah untuk mempermudah analisis dan pemrosesan, terutama dalam algoritma parsing. Berikut beberapa contoh soal dan penyelesaiannya:

Soal 1: Konversi ke CNF

Tata Bahasa:

S -> aSb | ε

Penyelesaian:

Tata bahasa ini tidak dalam CNF karena mengandung ε (epsilon, string kosong) dan aturan S -> aSb yang tidak sesuai dengan bentuk CNF. Berikut langkah-langkah konversinya:

Hilangkan ε-produksi: Karena S dapat menghasilkan string kosong, kita perlu menghilangkan produksi ini. Kita perlu mengidentifikasi semua non-terminal yang dapat menghasilkan string kosong. Dalam kasus ini, hanya S. Kemudian, kita perlu menambahkan produksi baru untuk setiap produksi yang menggunakan S.
- S -> aSb | ε menjadi S -> aSb | SS
Hilangkan produksi unit: Tata bahasa ini tidak memiliki produksi unit (produksi yang menghasilkan hanya satu simbol non-terminal).
Ubah produksi yang mengandung lebih dari dua simbol di sisi kanan: Produksi S -> aSb melanggar aturan CNF karena mengandung tiga simbol di sisi kanan. Kita perlu menambahkan non-terminal baru.
- Buat non-terminal baru, misalnya A dan B, sehingga aturan baru S -> AS, A -> aB, B -> bS.
- Tata bahasa baru dalam CNF menjadi:
```
S -> AS | SS
A -> aB
B -> bS
```

Jadi, tata bahasa CNF yang setara adalah:

S -> AS | SS
A -> aB
B -> bS

Soal 2: Menerima Kalimat?

Tata Bahasa (dalam CNF):

S -> AB | a
A -> BA | b
B -> AB | a

Pertanyaan: Apakah kalimat "aba" diterima oleh tata bahasa ini?

Penyelesaian:

Kita perlu mencari pohon parsing untuk kalimat "aba". Ini membutuhkan trial and error, dan penelusuran ruang pencarian.

Kita mulai dari S.
S -> AB (Kita perlu mengembang A dan B)
A -> BA (A menjadi BA) => S -> BAB
B -> a (B menjadi 'a') => S -> aAB
A -> b (A menjadi 'b') => S -> abB
B -> a (B menjadi 'a') => S -> aba

Kesimpulan: Kalimat "aba" diterima oleh tata bahasa ini karena kita dapat membangun pohon parsing.

Soal 3: Membuat Tata Bahasa CNF

Buatlah tata bahasa dalam Bentuk Normal Chomsky yang menghasilkan bahasa {a<sup>n</sup>b<sup>n</sup> | n ≥ 1}.

Penyelesaian:

Tata bahasa sederhana yang menghasilkan bahasa ini (belum dalam CNF) adalah:

S -> aSb | ab

Konversi ke CNF serupa dengan soal 1. Langkah-langkahnya akan menghasilkan tata bahasa CNF yang ekuivalen. (Proses konversi ini diserahkan sebagai latihan bagi pembaca).

Ingat, mengubah tata bahasa ke CNF bisa menjadi proses yang rumit, terutama untuk tata bahasa yang kompleks. Namun, pemahaman akan prinsip-prinsip dasar dan langkah-langkah yang terstruktur sangat penting dalam menyelesaikan permasalahan tersebut.

Contoh Soal Bentuk Normal Chomsky