Assalamualaikum Wr. Wb.
Nama : Muhammad Diki Hendriyanto
Kelas : 4G
NPM : 1810631170199
Dalam postingan kali ini saya akan membahas soal latihan dari pohon penurunan tata bahasa bebas konteks.
Untuk menjawab soal latihan ini yang harus dilakukan adalah simbol awal dari tata bahasa bebas konteks menjadi akar dari pohon penurunannya(root). Setelah itu saya melakukan percobaan kepada aturan produksi yang ada dalam soal dan memilih aturan produksi yang dapat menuju ke solusi sesuai dengan untai pohon penurunan yang terdapat pada soal.
Latihan Membuat Pohon Penurunan Parsing/Parse Tree Tata Bahasa Bebas Konteks
Soal Latihan 1 Parsing/Parse Tree
S → AA
A → AAA | a | bA | Ab
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "bbabaaba".
Jawab :
Langkah pengerjaan :
Pertama, buat akar dari pohon yang di dapat dari simbol awal himpunan aturan produksi pada soal yaitu S.
Kedua, memilih penurunan aturan produksi yang dapat menuju ke solusi agar mendapatkan sususan string seperti pada soal.
Pada simpul kiri (S => A) :
A => AAA
S => bA (agar mendapat string b sebagai awal sehingga didapat {b})
A => bA (agar mendapat string b sebagai lanjutannya sehingga didapat {bb})
A => a (agar mendapat string a sebagai lanjutannya sehingga didapat {bba})
A => bA (agar mendapat string b sebagai lanjutannya sehingga didapat {bbab})
A => a (agar mendapat string a sebagai lanjutannya sehingga didapat {bbaba})
A => a (agar mendapat string a sebagai lanjutannya sehingga didapat {bbabaa})
Pada simpul kanan (S => A) :
A => bA (agar mendapat string b sebagai lanjutannya maka kita dapat {bbabaab})
A => a (agar mendapat string a sebagai lanjutannya maka kita dapat {bbabaaba})
Pohon Penurunan untuk susunan string "bbabaaba" :
Jawab :
Langkah pengerjaan :
Pertama, buat akar dari pohon yang di dapat dari simbol awal himpunan aturan produksi pada soal yaitu S.
Kedua, memilih penurunan aturan produksi yang dapat menuju ke solusi agar mendapatkan sususan string seperti pada soal.
Pada simpul kiri (S => A) :
A => AAA
S => bA (agar mendapat string b sebagai awal sehingga didapat {b})
A => bA (agar mendapat string b sebagai lanjutannya sehingga didapat {bb})
A => a (agar mendapat string a sebagai lanjutannya sehingga didapat {bba})
A => bA (agar mendapat string b sebagai lanjutannya sehingga didapat {bbab})
A => a (agar mendapat string a sebagai lanjutannya sehingga didapat {bbaba})
A => a (agar mendapat string a sebagai lanjutannya sehingga didapat {bbabaa})
Pada simpul kanan (S => A) :
A => bA (agar mendapat string b sebagai lanjutannya maka kita dapat {bbabaab})
A => a (agar mendapat string a sebagai lanjutannya maka kita dapat {bbabaaba})
Pohon Penurunan untuk susunan string "bbabaaba" :
Baca variabel terminal dari kiri ke kanan, maka susunan string akan sesuai dengan susunan “bbabaaba”.
Soal Latihan 2 Parsing/Parse Tree
S → AB
A → Aa | bB
B → a | Sb
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "baabaab".
Jawab :
Langkah pengerjaan :
Pertama, buat akar dari pohon yang di dapat dari simbol awal himpunan aturan produksi pada soal yaitu S.
Kedua, memilih penurunan aturan produksi yang dapat menuju ke solusi agar mendapatkan sususan string seperti pada soal.
Pada simpul kiri (S => A) :
A => Aa (maka didapatkan string a)
A => Ab (agar mendapat string b sebagai awal sehingga didapat {b})
B => a (agar mendapat string a sebagai lanjutan sehingga didapat {baa})
Pada simpul kanan (S => B) :
B => Sb (maka didapatkan string b sebagai akhir sehingga susunannya menjadi {baa...b})
S => AB
A => bB (agar mendapat string b sebagai lanjutannya maka susunannya menjadi {baab...b})
B => a (agar mendapat string a sebagai lanjutannya maka susunannya menjadi {baaba...b})
B => a (agar mendapat string a sebagai lanjutannya maka susunannya menjadi {baabaab})
Pohon Penurunan untuk susunan string "baabaab" :
Jawab :
Langkah pengerjaan :
Pertama, buat akar dari pohon yang di dapat dari simbol awal himpunan aturan produksi pada soal yaitu S.
Kedua, memilih penurunan aturan produksi yang dapat menuju ke solusi agar mendapatkan sususan string seperti pada soal.
Pada simpul kiri (S => A) :
A => Aa (maka didapatkan string a)
A => Ab (agar mendapat string b sebagai awal sehingga didapat {b})
B => a (agar mendapat string a sebagai lanjutan sehingga didapat {baa})
Pada simpul kanan (S => B) :
B => Sb (maka didapatkan string b sebagai akhir sehingga susunannya menjadi {baa...b})
S => AB
A => bB (agar mendapat string b sebagai lanjutannya maka susunannya menjadi {baab...b})
B => a (agar mendapat string a sebagai lanjutannya maka susunannya menjadi {baaba...b})
B => a (agar mendapat string a sebagai lanjutannya maka susunannya menjadi {baabaab})
Pohon Penurunan untuk susunan string "baabaab" :
Baca variabel terminal dari kiri ke kanan, maka susunan string akan sesuai dengan susunan “baabaab”.
Soal Latihan 3 Parsing/Parse Tree
S → Ba | Ab
A → Sa | Aab | a
B → Sb | Bba | b
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "bbaaaabb".
Jawab :
Akar dari pohon dibuat dari aturan produksi S → Ab (karena ini akan membuat susunan string dari pohon akan berakhiran b.
Setelah itu gunakan produksi A → Aab agar mendapatkan string a dan b sehingga susunannya menjadi {...abb}
Setelah itu gunakan produksi A → Sa agar mendapat string a sehingga susunan stringnya menjadi {...aabb}
Setelah itu gunakan produksi S → Ba agar mendapat string a sehingga susunan stringnya menjadi {...aaabb}
Setelah itu gunakan produksi B → Bba agar mendapat string b dan a sehingga susunan stringnya menjadi {...baaaabb}
Setelah itu gunakan produksi B → b agar mendapat string b sehingga susunan stringnya menjadi {bbaaaabb], dengan demikian susunan stringnya sudah sama seperti soal diatas.
Pohon Penurunan untuk susunan string "bbaaaabb" :
Latihan Membuat Pohon Penurunan Ambiguitas Tata Bahasa Bebas Konteks
Soal Latihan 1 Ambiguitas
S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | aDd
D → bDc | bc
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "aabbccdd".
Jawab :
CFG dikatakan ambigu apabila terdapat penurunan yang dapat dikerjakan dengan dua cara sekaligus, lebih dari satu leftmost derivation dan/atau lebih dari satu rightmost derivation.
Pohon Penurunan "aabbccdd" (1)
Leftmost Derivation:
S => AB => aAbcBd => aabbccdd
Jawab :
CFG dikatakan ambigu apabila terdapat penurunan yang dapat dikerjakan dengan dua cara sekaligus, lebih dari satu leftmost derivation dan/atau lebih dari satu rightmost derivation.
Pohon Penurunan "aabbccdd" (1)
Leftmost Derivation:
S => AB => aAbcBd => aabbccdd
Baca variabel terminal dari kiri ke kanan, maka susunan string akan sesuai dengan susunan “aabbccdd”.
Pohon Penurunan "aabbccdd" (2)
Rightmost Derivation:
S => C => aCd => aaDdd => aabDcdd => aabbccdd
Baca variabel terminal dari kiri ke kanan, maka susunan string akan sesuai dengan susunan “aabbccdd”.
Dari pohon penurunan di atas dapat dilihat bahwa untuk sususan string yang sama ("aabbccdd") dapat dibuat pohon penurunan yang berbeda, maka dapat dikatakan bahwa tata bahasa bebas konteks tersebut ambigu.
Untuk lebih jelasnya mengenai soal di atas dapat melihat video di bawah ini
Sekian pembahasan latihan pohon penurunan tata bahasa bebas konteks. Semoga pembahasan latihan diatas dapat bermanfaat. Mohon maaf kalau masih ada kekurangan.
Wassalamualaikum Wr. Wb.
Daftar Pustaka:
Materi 6 Tata Bahasa Bebas Konteks (Pohon Penurunan) [pdf]. Dosen Pengampu: Garno, M.Kom. Fakultas Ilmu Komputer, Universitas Singaperbangsa Karawang.
EmoticonEmoticon