Tugas 6 : Latihan Pohon Penurunan Tata Bahasa Bebas Konteks

Halo...

Saya Aditya Wijaya (1810631170083) dari kelas 4G,

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 → AB

A → Aa | bB

B → 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 | 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]

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

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.

Daftar Pustaka:

Materi 6 Tata Bahasa Bebas Konteks (Pohon Penurunan) dari Dosen Pengampu: Garno, M.Kom. Fakultas Ilmu Komputer, Universitas Singaperbangsa Karawang.

https://www.scribd.com/doc/314979281/Pohon-penurunan

http://lerykapressy.blogspot.com/2018/04/hirarki-chomsky.html

https://fairuzelsaid.wordpress.com/2011/06/16/tbo-context-free-grammar-cfg/