Tugas 6 : Latihan Pohon Penurunan Tata Bahasa Bebas Konteks
Halo...
Pada kesempatan kali ini saya akan membahas latihan dari tugas 6 pohon penurunan tata bahasa bebas konteks.
Soal Latihan 1 Parsing/Parse Tree
S → AA
Jawab :
Pertama, membuat akar dari pohon. Akarnya didapat dari simbol pertama dari soal yaitu S lalu kita turunkan menjadi AA.
Kedua, memilih penurunan aturan produksi yang dapat menuju ke solusi agar mendapatkan sususan string sesuai dengan 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 :
Pertama, membuat akar dari pohon. Akarnya didapat dari simbol pertama dari soal yaitu S lalu kita turunkan menjadi AB.
Kedua, memilih penurunan aturan produksi yang dapat menuju ke solusi agar mendapatkan sususan string sesuai dengan 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" :
S → Ba | AbA → Sa | Aab | aB → 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]
Pohon Penurunan untuk susunan string "bbaaaabb" :
Jawab :
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".
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "bbabaaba".
Jawab :
Pertama, membuat akar dari pohon. Akarnya didapat dari simbol pertama dari soal yaitu S lalu kita turunkan menjadi AA.
Kedua, memilih penurunan aturan produksi yang dapat menuju ke solusi agar mendapatkan sususan string sesuai dengan 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" :
Maka, string yang dihasilkan sudah sesuai dengan soal.
Soal Latihan 2 Parsing/Parse Tree
S → ABA → Aa | bBB → a | Sb
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "baabaab".
S → ABA → Aa | bBB → a | Sb
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "baabaab".
Jawab :
Pertama, membuat akar dari pohon. Akarnya didapat dari simbol pertama dari soal yaitu S lalu kita turunkan menjadi AB.
Kedua, memilih penurunan aturan produksi yang dapat menuju ke solusi agar mendapatkan sususan string sesuai dengan 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" :
Maka, string yang dihasilkan sudah sesuai dengan soal.
Soal Latihan 3 Parsing/Parse Tree
S → Ba | AbA → Sa | Aab | aB → Sb | Bba | b
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "bbaaaabb".
Jawab :
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]
Pohon Penurunan untuk susunan string "bbaaaabb" :
Maka, string yang dihasilkan sudah sesuai dengan soal.
Latihan Membuat Pohon Penurunan Ambiguitas Tata Bahasa Bebas Konteks
Soal Latihan 1 Ambiguitas
S → AB | CA → aAb | abB → cBd | cdC → aCd | aDdD → bDc | bc
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "aabbccdd".
Soal Latihan 1 Ambiguitas
S → AB | CA → aAb | abB → cBd | cdC → aCd | aDdD → bDc | bc
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "aabbccdd".
Jawab :
Pohon Penurunan "aabbccdd" (1)
Leftmost Derivation:
S => AB => aAbcBd => aabbccdd
Leftmost Derivation:
S => AB => aAbcBd => aabbccdd
S => AB
S => aAbcBd
S => aabbccdd
Maka, string yang dihasilkan sudah sesuai dengan soal.
Pohon Penurunan "aabbccdd" (2)
Rightmost Derivation:
S => C => aCd => aaDdd => aabDcdd => aabbccdd
S => C
S=> aCd
S = > aaDdd
S => aabDcdd
S => aabbccdd
Maka, string yang dihasilkan sudah sesuai dengan soal.
Untuk lebih jelasnya mengenai latihan pohon penurunan tata bahasa bebas konteks dapat melihat video dibawah ini
Comments
Post a Comment