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. 

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 :

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".

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 :

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" :

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".

Jawab :

Pohon Penurunan "aabbccdd" (1)

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

Daftar Pustaka : Materi 6 Tata Bahasa Bebas Konteks (Pohon Penurunan) [pdf]. Dosen Pengampu: Garno, M.Kom. Fakultas Ilmu Komputer, Universitas Singaperbangsa Karawang. https://socs.binus.ac.id/2019/12/30/cara-membuat-parse-tree/ http://mshang.ca/syntree/ (untuk membuat gambar pohon penurunan)