Pertanyaan

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

Solusi

Terverifikasi Ahli
4.3 (280 Suara)
Lokesh lanjutan ยท Tutor selama 1 tahun

Jawaban

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:** - 2. **Produksi A:** - 3. **Produksi B:** - 4. **Produksi C:** - 5. **Produksi D:** - ### Langkah-langkah Mengubah ke CNF:#### Langkah 1: Mengubah Produksi yang Menghasilkan Lebih dari Dua Simbol- **Produksi S:** - A \rightarrow a \vert bc \vert i B \rightarrow BC \vert Ab \vert BcG B \rightarrow B'C \vert A'b \vert B'cG B' \rightarrow BC \vert Ab \vert BcG C \rightarrow aB \vert b C \rightarrow aB \vert b D \rightarrow gA D \rightarrow gA S \rightarrow aB \vert CA \vert DD \vert DbA A \rightarrow a \vert bc \vert i B \rightarrow B'C \vert A'b \vert B'cG C \rightarrow aB \vert b D \rightarrow gA S \rightarrow aB \vert CA \vert DD \vert DbA A \rightarrow a \vert bc \vert i B \rightarrow B'C \vert A'b \vert B'cG C \rightarrow aB \vert b D \rightarrow gA$Dengan demikian, CFG ini sekarang sudah dalam bentuk CNF.