Kode Soal :34622 Ubahlah aturan produksi bentuk CFG pada gambar berikut ke CNF? Sarrow aBvert CAvert DDvert DbA Aarrow avert bcvert i Barrow BCvert Abvert BcG Carrow aBvert b Darrow gA

Untuk mengubah aturan produksi dari Context-Free Grammar (CFG) ke Chomsky Normal Form (CNF), kita harus memastikan bahwa setiap produksi menghasilkan tepat dua simbol dan tidak ada simbol tunggal di sebelah kanan. Berikut adalah langkah-langkah untuk mengubah CFG tersebut ke CNF:

1. Produksi Awal:
- $S \rightarrow aB \vert CA \vert DD \vert DbA$

2. Produksi A:
- $A \rightarrow a \vert bc \vert i$

3. Produksi B:
- $B \rightarrow BC \vert Ab \vert BcG$

4. Produksi C:
- $C \rightarrow aB \vert b$

5. Produksi D:
- $D \rightarrow gA$

Langkah-langkah Mengubah ke CNF:

Langkah 1:

Mengubah Produksi yang Menghasilkan Lebih dari Dua Simbol

- Produksi S:
- $S \rightarrow aB \vert CA \vert DD \vert Db - Ini sudah sesuai dengan CNF karena semua produksi menghasilkan dua simbol.

- Produksi A:
- $A \rightarrow a \vert bc \vert i$
- Ini juga sudah sesuai dengan CNF.

- Produksi B:
- $B \rightarrow BC \vert Ab \vert BcG$
- Ubah menjadi:
- $B \rightarrow B'C \vert A'b \vert B'cG$
- $B' \rightarrow BC \vert Ab \vert BcG$

- Produksi C:
- $C \rightarrow aB \vert b$
- Ubah menjadi:
- $C \rightarrow aB \vert b$
- Ini sudah sesuai dengan CNF.

- Produksi D:
- $D \rightarrow gA$
- Ubah menjadi:
- $D \rightarrow gA$
- Ini sudah sesuai dengan CNF.

Langkah 2:

Memastikan Tidak Ada Simbol Tunggal di Sebelah Kanan

- Produksi S:
- $S \rightarrow aB \vert CA \vert DD \vert DbA$
- Semua produksi di sini menghasilkan dua simbol, jadi sudah sesuai.

- Produksi A:
- $A \rightarrow a \vert bc \vert i$
- Semua produksi di sini menghasilkan dua simbol, jadi sudah sesuai.

- Produksi B:
- $B \rightarrow B'C \vert A'b \vert B'cG$
- Semua produksi di sini menghasilkan dua simbol, jadi sudah sesuai.

- Produksi C:
- $C \rightarrow aB \vert b$
- Semua produksi di sini menghasilkan dua simbol, jadi sudah sesuai.

- Produksi D:
- $D \rightarrow gA$
- Semua produksi di sini menghasilkan dua simbol, jadi sudah sesuai.

Kesimpulan

Setelah melakukan perubahan yang diperlukan, kita mendapatkan CFG yang sesuai dengan CNF sebagai berikut:

- Produksi S:
- $S \rightarrow aB \vert CA \vert DD \vert DbA$

- Produksi A:
- $A \rightarrow a \vert bc \vert i$

- Produksi B:
- $B \rightarrow B'C \vert A'b \vert B'cG$

- Produksi C:
- $C \rightarrow aB \vert b$

- Produksi D:
- $D \rightarrow gA$

Dengan demikian, CFG ini sekarang sudah dalam bentuk CNF.