TUGAS MATERI 6
Latihan Membuat Pohon Penurunan Parsing/Parse Tree Tata Bahasa Bebas kontek
Latihan 1
S à AA
A à AAA | a | bA | Ab
Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan “bbabaaba”.
Jawab:
A => AAA
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})
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})
S => bA (agar mendapat string b sebagai awal sehingga didapat {b})
Pohon penurunan untuk susunan string "aabbaaba"
Latihan 2
S à AB
A à Aa | bB
B à a | Sb
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “baabaab”
Jawab:
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" :
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" :
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:
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" :
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" :
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".
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:
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.
Leftmost Derivation
S => AB => aAbcBd => aabbccdd
S =>aAbcBd
S => aabbccdd
Rightmost Derivation
S => C => aCd => aaDdd => aabDcdd => aabbccdd
Parse Tree
S => C
S => aCd
S => aaDdd
S => aabbccdd
Video penjelasan
thanks to http://mshang.ca/syntree/ for easier draw the parse tree pattern.
Komentar
Posting Komentar