Pohon Penurunan - Tata Bahasa Bebas Konteks

Selamat Datang Kembali di Dunia Ilmu .......

• Parsing

Apakah itu Pohon Penurunan...? Pohon penurunan atau parse tree/ derivation tree digunakan untuk menggambarkan penurunan simbol-simbol non terminal untuk memperoleh suatu string (untai). Setiap simbol variabel akan diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.

Sebuah pohon (tree) adalah suatu graph  terhubung tidak sirkuler, yang memiliki suatu simpul (node) / vartex yang disebut akar (root) dan dari root memiliki lintasan ke setiap simpul.

Contoh 1 :

Misalkan Terdapat tata bahasa konteks dengan himpunan produksi sebagai berikut :

Dari himpunan produksi tersebut buatlah pohon penurunan untuk membangkitkan string dengan susunan "bbabaaba".

Pohon penurunan yang didapatkan dari himpunan produksi tersebut ialah :

Contoh 2 : 

Misal terdapat himpunan produksi sebagai berikut :

Dari himpunan produksi tersebut buatlah pohon penurunan yang membangkitkan string dengan susunan "baabaab"

Pohon penurunan yang didapatkan dari himpunan produksi ini ialah 

Contoh 3 : 

Misalkan terdapat himpunan produksi sebagi berikut :

Dari himpunan produksi tersebut buatlah pohon penurana yang membangkitkan string dengan susunan "bbaaaabb"

Pohon penurunan yang didapatkan dari hmpunan produksi tersebut ialah

• Ambiguitas

Ambiguitas terjadi apabila terdapat lebih dari satu pohon penurunana yang berbeda untuk memperoleh suatu untai.

Contoh :

Misalkan terdapat tata bahasa bebas konteks himpunan produksi sebagai berikut :

Buatlah pohon penurunan dari himpunan produksi tersebut untuk menghasilkan string dengan susunan "aabbccdd"

Pohon penurunan yang didapatkan terdapat 2 cara yaitu 

Cara 1 :

Cara 2 :

Video Pembahasan :

Semoga Bermanfaat , Terimakasih .......

Destaria Wilandini (18048) - 4G