Teori Bahasa Dan Automata - Tata Bahasa Bebas Konteks (Latihan Parsing)

Dibuat Oleh pada
Assalamualaikum Wr. Wb.

Pada postingan ini saya akan membagikan sebuah materi penyederhanaan tata bahasa bebas konteks. Tujuan saya membuat postingan ini adalah untuk memenuhi Tugas Materi 6 pada Mata Perkuliahan TEORI BAHASA DAN AUTOMATA.

 Pada postingan sebelumnya, saya membagikan materi tentang pohon penurunan. Kali ini saya akan mencoba membahas soal latihannya

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


Diketahui:
S mempunyai satu buah derivasi, yaitu AA

A mempunyai empat buah derivasi, yaitu AAA, a, Ba, Ab



Kita harus memilih simpul mana yang harus diselesaikan terlebih dahulu, bisa dimulai dari kiri atau dari kanan tapi harus memilih derivasi yang tepat dengan string pembangkit yang diinginkan



Jika simpul sudah merupakan variabel terminal, maka simpul tersebut sudah tidak dapat dilakukan derivasi/penurunan lagi



Langkah pengerjaan:
Pohon Penurunan 1.1

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":
Pohon Penurunan 1.2

Pohon penurunan ini menggunakan leftmost derivation (simbol variabel terkiri yang diperluas terlebih dulu)

Sehingga jika dibaca 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

Diketahui:
S mempunyai satu buah derivasi, yaitu AB
A mempunyai dua buah derivasi, yaitu Aa dan bB
B mempunyai dua buah derivasi, yaitu a dan Sb

Kita harus memilih simpul mana yang harus diselesaikan terlebih dahulu, bisa dimulai dari kiri atau dari kanan tapi harus memilih derivasi yang tepat dengan string pembangkit yang diinginkan

Jika simpul sudah merupakan variabel terminal, maka simpul tersebut sudah tidak dapat dilakukan derivasi/penurunan lagi

Langkah pengerjaan:
Pohon Penurunan 2.1
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":
Pohon Penurunan 2.2
Sehingga jika dibaca 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

Diketahui:
S mempunyai dua buah derivasi, yaitu Ba dan Ab
A mempunyai tiga buah derivasi, yaitu Sa, Aab dan a
B mempunyai tiga buah derivasi, yaitu Sb, Bba dan b

Kita harus memilih simpul mana yang harus diselesaikan terlebih dahulu, bisa dimulai dari kiri atau dari kanan tapi harus memilih derivasi yang tepat dengan string pembangkit yang diinginkan

Jika simpul sudah merupakan variabel terminal, maka simpul tersebut sudah tidak dapat dilakukan derivasi/penurunan lagi

Langkah pengerjaan:
Pohon Penurunan 3.1
Pada simpul kanan (S => b):
     S => b (maka didapatkan string b sebagai akhir sehingga susunannya menjadi {_____b})

Pada simpul kiri (S => A):
     A => Aab (maka didapatkan string {___abb})
     A => Sa (maka didapat string {___aabb})
     S => Ba (maka didapat string {___aaabb})
     B => Bba (maka didapat string {___baaaabb})
     B => b (agar mendapatkan string b sebagai string paling kiri sehingga didapat {bbaaaabb})

Pohon Penurunan untuk susunan string "bbaaaabb":
Pohon Penurunan 3.2

Sehingga jika dibaca dari kiri ke kanan ataupun dari kanan ke kiri, maka susunan string akan sesuai dengan susunan “bbaaaabb”.

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)
Pohon Penurunan 4.1
Sehingga jika dibaca dari kiri ke kanan, maka susunan string akan sesuai dengan susunan “aabbccdd”

Pohon Penurunan "aabbccdd" (2)
Pohon Penurunan 4.2
Sehingga jika dibaca dari kiri ke kanan, maka susunan string akan sesuai dengan susunan “aabbccdd”.

Dari kedua 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.

Video Pembahasan:


Video juga bisa ditonton di Youtube

Sekian materi yang saya posting di blog ini. Mohon maaf apabila ada kekurangan dan kesalahan dalam penulisan. Semoga dapat bermanfaat bagi kita semua

Terima Kasih

Wassalamualaikum Wr. Wb.
-----------------------------------------------------------------------------------------------------------------------------------------------
DAFTAR PUSTAKA

  • Materi Persentasi "Materi 6 Tata Bahasa Bebas Konteks (Pohon Penurunan)" Dosen pengampu Teori Bahasa Automata: Garno, M.Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang
  • Materi Persentasi "Materi 6 Tata Bahasa Bebas Konteks Latihan Parsing" Dosen pengampu Teori Bahasa Automata: Garno, M.Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang
  • Media online: https://www.academia.edu/37758551/Pohon_Penurunan
  • Media online: http://mshang.ca/syntree/  (digunakan untuk membuat pohon penurunan)

Komentar

Posting Komentar