TATA BAHASA BEBAS KONTEKS (POHON PENURUNAN)



Teori Bahasa dan Automata
Tata Bahasa Bebas Konteks
Pohon Penurunan


Teori Bahasa Bebas Konteks
adalah suatu cara yang menunjukkan bagaimana menghasilkan untai - untai dalam sebuah bahasa.

Teori bahasa bebas konteks pohon penurunan, terbagi menjadi 2 yaitu : Parsing dan Ambiguitas.


1. Parsing
  •     Sebuah pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) / vertex yang disebut akan atau root dan dari root 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.

Proses penurunan atau parsing bisa dilakukan dengan cara: 
  •      Penurunan terkiri (leftmost derivation): simbol variabel terkiri yang diperluas terlebih dahulu. 
  •      Penurunan terkanan (right derivation): simbol variabel terkanan yang diperluas terlebuh dahulu.


Latihan 1 

S à AA 
A à AAA | a | bA | Ab
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "bbabaaba".

Jawab :



Baca variabel terminal dari bagian kiri ke kanan, maka susunan string akan sesuai dengan susunan "bbabaaba".

Latihan 2

S à AB
A à Aa | bB
B à a | Sb
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "baabaab".

Jawab :



Dengan demikian, susunan simpul sudah sesuai dengan susunan string "baabaab".

Latihan 3

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 :

Pada soal ini, kita bisa menyelesaikan dengan dua metode yaitu leftmost derivation dan/atau rightmost derivation. Namun, karena produksi S à Ba (leftmost derivation) akan menyebabkan susunan string berakhiran "...a", sementara string bbaaaabb" berakhiran b, maka produksi S à Ba tidak valid dijadikan sebagai akar atau root. Dengan demikian akar terdiri dari parse tree memakai produksi S à Ab.



Dengan demikian, susunan simpul sudah sesuai dengan susunan string "bbaaaabb".

2. Ambiguitas

Ambiguitas atau ke-dwi terjadi bila tedapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai.

Latihan 1

S à AB | C
A à aAB | cd
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 lebih dari satu penurunan yang dapat dikerjakan sekaligus. Lebih dari satu leftmost derivation dan/atau lebih dari satu rightmost derivation.

Leftmost Derivation 
S → AB → aAbcBd → aabbccdd

Pohon 1



Rightmost Derivation
S → C → aCd → aaDdd → aabDcdd → aabbccdd

Pohon 2



Video Penjelasan Latihan 
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 :


Comments

Post a Comment

Popular posts from this blog

Image
BILANGAN BINER,  OKTAL, DESIMAL DAN HEKSADESIMAL A.     Macam – Macam Bilangan 1.      Bilangan Desimal Sistem bilangan desimal atau persepuluhan merupakan sistem bilangan dengan 10 macam angka, mulai dari  0, 1, 2, 3, 4, 5, 6, 7, 8 dan 9 . Setelah angka 9, angka yang selanjutnya adalah 1 0, 1 1 dan seterusnya. Sistem bilangan desimal ini biasa dikenal sebagai sistem bilangan basis 10, karena setiap angka desimal menggunakan basis 10. Contoh penulisan :  3₍₁₀₎ 2.      Bilangan Biner Sistem bilangan biner atau sistem bilangan basis 2 merupakan sistem penulisan angka dengan hanya menggunakan 2 simbol saja, yakni  0 dan 1 . Sistem bilangan biner menjadi salah satu sistem bilangan dasar dari semua sistem bilangan yang berbasis digital. Dari sistem bilangan biner inilah, kita mampu melakukan konversi ke sistem bilangan oktal dan heksadesimal. Sistem ini juga bisa disebut d...
Read more

FINITE STATE AUTOMATA & NON FINITE STATE AUTOMATA

Image
Teori Bahasa dan Automata Finite State Automata &  Non Finite State Automata Pembahasan : Penerapan FSA DFA NDFA/NFA Ekuivalen antar DFA Reduksi Jumlah State pada FSA 1. Penerapan (FSA)      Finite state automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.   Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.      FSH atau AH (Automata Hingga) didefinisikan sebagai pasangan 5  Finite State Automata dinyatakan oleh pasangan 5 tuple, yaitu: M = (Q , Σ , δ , S , F ) Q : himpunan stat...
Read more