TATA BAHASA BEBAS KONTEKS (POHON PENURUNAN)

Teori Bahasa dan Automata

Tata Bahasa Bebas Konteks (Pohon Penurunan)

Tata bahasa bebas konteks adalah suatu cara yang bagaimana menunjukkan bagaimana menghasilkan untai – untai dalam sebuah bahasa.

Parsing

Pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) yang disebut akar dan dari situ memiliki lintasan ke setiap simpul. Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal. Setiap simbol variabel akan diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.

Proses penurunan atau parsing bisa dilakukan dengan cara :

1.        Penurunan terkiri (leftmost derivation): simbol variabel terkiri yang diperluas terlebih dahulu.

2.        Penurunan terkanan (right derivation): simbol variabel terkanan yang diperluas terlebuh dahulu.

Misal, aturan produksi :

S ➝ aAS | a

A ➝ SbA | ba

Untuk memperoleh untai “aabbaa” :

Simbol (⇒) dibaca menurunkan

·           Dengan penurunan terkiri :

 S ⇒ aAS ⇒ aSbAS ⇒ aabAS ⇒ aabbaS ⇒ aabbaa

·           Dengan penurunan terkanan :

 S ⇒ aAS ⇒ aAa ⇒ aSbAa ⇒ aSbbaa ⇒ aabbaa

Meskipun proses penurunan berbeda, namun akan tetap memiliki pohon penurunan yang sama.

Pohon Penurunan

Contoh 1

Buatlah pohon penurunan dari himpunan produksi dibawah ini untuk membangkitkan string dengan susunan“bbabaaba” :

S ➝ AA

A ➝ AAA | a | bA| Ab

Penyelesaian :

Untuk memperoleh untai “bbabaaba” dari tata bahasa bebas konteks diatas (simbol ‘⇒’ dibaca menurunkan) :

·           Dengan penurunan terkiri :

 S ⇒ AA ⇒ AAAA ⇒ bAAAA ⇒ bbAAAA ⇒ bbaAAA ⇒ bbabAAA ⇒ bbabaAA ⇒ bbabaaA   ⇒ bbabaabA ⇒ bbabaaba

·           Dengan penurunan terkanan :

 S ⇒ AA ⇒ AbA ⇒ Aba ⇒ AAAba ⇒ AAaba ⇒ AbAaba ⇒ Abaaba ⇒ bAbaaba ⇒ bbAbaaba ⇒ bbabaaba

Meskipun proses penurunan berbeda, namun akan tetap memiliki pohon penurunan yang sama.

Pohon Penurunan

Contoh 2

Buatlah pohon penurunan dari himpunan produksi dibawah ini untuk membangkitkan string dengan susunan “baabaab”

S ➝ AB

A ➝ Aa | bB

B ➝ a | Sb

Penyelesaian :

Untuk memperoleh untai “baabaab” dari tata bahasa bebas konteks diatas (simbol ‘=>’ dibaca menurunkan) :

·           Dengan penurunan terkiri :

 S ⇒ AB ⇒ AaB ⇒ bBaB ⇒ baaB ⇒ baaSb ⇒ baaABb ⇒ baabBBb ⇒ baabaBb ⇒ baabaab

·           Dengan penurunan terkanan :

 S ⇒ AB ⇒ ASb ⇒ AABb ⇒ AAab ⇒ AbBab ⇒ Abaab ⇒ Aabaab ⇒ bBabaab ⇒  baabaab

Meskipun proses penurunan berbeda, namun akan tetap memiliki pohon penurunan yang sama.

Pohon Penurunan

Contoh 3

Buatlah pohon penurunan dari himpunan produksi dibawah untuk membangkitkan string dengan susunan “bbaaaabb” :

S ➝ Ba | Ab

A ➝ Sa | Aab| a

B ➝ Sb| Bba| b

Penyelesaian :

Untuk memperoleh untai “bbaaaabb” dari tata bahasa bebas konteks diatas (simbol ‘=>’ dibaca menurunkan) :

·           Dengan penurunan terkiri :

 S ⇒ Ab ⇒ Aabb ⇒ Saabb ⇒ Baaabb ⇒ Bbaaaabb ⇒ bbaaaabb

·           Dengan penurunan terkanan :

 S ⇒ Ab ⇒ Aabb ⇒ Saabb ⇒ Baaabb ⇒ Bbaaaabb ⇒ bbaaaabb

Pohon Penurunan

Ambiguitas

Terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda utuk memperoleh suatu untai.

Misal terdapat tata bahasa bebas konteks :

S ➝ SbS | ScS | a

Untuk memperoleh untai ‘abaca’

Pohon Penurunan

Cara pertama :

S ⇒ SbS ⇒ SbScS ⇒ SbSca ⇒ Sbaca ⇒ abaca

Cara kedua :

S ⇒ ScS ⇒ SbScS ⇒ abScS ⇒ abacS ⇒ abaca

Contoh soal

Aturan produksi :

S ➝ AB | C

A ➝ aAb | ab

B ➝ cBd | cd

C ➝ aCd | aDd

D ➝ bDc | bc

Untuk memperoleh untai ‘aabbccdd’

Pohon Penurunan

Cara pertama :

S ⇒ AA ⇒ aAbA ⇒ aabbA ⇒ aabbcBd ⇒ aabbccdd

Cara kedua :

S ⇒ C ⇒ aCd ⇒ aaDdd ⇒ aabDcdd ⇒ aabbccdd

Berikut video penjelasan tentang Tata Bahasa Bebas Konteks (Pohon Penurunan) : 

Semoga artikel dan video ini dapat membantu dalam mengerjakan soal-soal tentang Tata Bahasa Bebas Konteks (Pohon Penurunan). Mohon maaf bila ada kesalahan dalam penulisan dan ucapan. Karena kesalahan hanya milik manusia dan kebenaran hanya milik Allah swt. Terima kasih☺️

Daftar Pustaka : 

Materi 6 Tata Bahasa Bebas Konteks (Pohon Penurunan) Dosen  pengampu Teori Bahasa dan Automata : Garno, M.Kom Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang. 

Apranolo.tif.uad.ac.id. Tata Bahasa Bebas Konteks diakses melalui 
http://apranolo.tif.uad.ac.id/wp-content/uploads/2014/12/TBA_TID_Kelompok-7_TATA-BAHASA-BEBAS-KONTEKS.pdf

Kelasqta.files.wordpress.com. Teori Bahasa dan Automata Pohon Penurunan Context Free Grammar diakses melalui https://kelasqta.files.wordpress.com/2013/01/chapter-10-tbo.pdf