Teori Bahasa dan Automata

-

Tata Bahasa Bebas Konteks(Pohon Penurunan)

(derivation tree/parse tree) berguna untuk menggambarkan simbol-simbol variabel menjadi simbol-simbol terminal setiap simbol variabel akan di turunkan menjadi terminal sampai tidak ada yang belum tergantikan.

Terbagi menjadi 2 yaitu PARSING & AMBIGUITAS :

1. 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.

Latihan 1
S à AA
A à AAA | a | bA | Ab
Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan “bbabaaba”.
Jawab :


 Baca variabel terminal dari 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 (root). Dengan demikian akar  dari parse tree memakai produksi S à Ab.

Dengan demikian susunan simpul sudah sesuai dengan susunan string “bbaaaabb”.

2. AMBIGUITAS
Terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda utuk memperoleh suatu untai.
 
Latihan 1      
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.
Leftmost Derivation
S => AB => aAbcBd => aabbccdd
Pohon 1 :

Rightmost Derivation
S => C => aCd => aaDdd => aabDcdd =>aabbccdd
Pohon 2 :
Untuk Melihat Video Penjelasannya
Membuat Pohon Penurunan Parsing/Parse Tree 
Tata Bahasa Bebas Kontek 
Ada Dibawah Sini..

Daftar Pustaka :
http://eywatsauroty.blogspot.com/2014/09/tata-bahasa-bebas-konteks.html
http://teoribahasa.blogspot.com/2014/01/teori-bahasa-automata.html
http://apranolo.tif.uad.ac.id/wp-content/uploads/2014/12/TBA_TID_Kelompok-7_TATA-BAHASA-BEBAS-KONTEKS.pdf
https://socs.binus.ac.id/2019/12/30/cara-membuat-parse-tree/

Komentar

Posting Komentar

Postingan populer dari blog ini

Teori Bahasa dan Automata "Penerapan FSA, DFA(Deterministik Finite Automata), NFA(non deterministik Finite Automata), Ekuivalen antar DFA, Reduksi Jumalh State."

-
Gambar
Finite State Automata (FSA) Finite State Automata (FSA) merupakan tool yang sangat berguna untuk mengenal dan menangkap pola dalam data. 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 FSA didefinisikan sebagai pasangan 5 tupel : (Q, ∑, δ, S, F). Q : himpunan hingga state ∑ : himpunan hingga simbol input (alfabet) δ : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input. (Fungsi transisi ini biasanya diberikan dalam bentuk tabel.) S : state AWAL (Start) F : himpunan state AKHIR (Final) Karakteristik Finite Automata : 1.Setiap Finite Automata memiliki keadaan dan transisi yang terbatas. 2.Transisi dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau non-deterministik. 3.Setiap Finite Automata selalu memiliki keadaan awal. ...
Baca selengkapnya

Teknik-teknik Penyederhanaan Produksi Empty, Unit, dan Useless

-
Gambar
 Tugas Materi 5  Teknik-teknik Penyederhanaan Produksi Empty, Unit, dan Useless 1. Produksi Empty Produksi ε adalah produksi dalam bentuk a → ε atau bisa dianggap sebagai produksi kosong (empty). Penghilangan produksi e dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju produksi e, atau biasa disebut nullable. Prinsip penggantiannya bisa dilihat kasus berikut: S → bcAd A → ε A nullable serta A → ε satu-satunya produksi dari A, maka variabel A bisa Contoh : terdapat tata bahasa bebas konteks sebagai berikut : S -> aB | Cd A -> d C -> ε Variable yang nullable adalah variable C, karena penurunan C -> ε merupakan penurunan satu-satunya dari C. maka kita ganti S -> Cd menjadi S -> d. kemudian produksi C -> ε kita hapus. Hasil penyederhanaannya adalah : S -> aB | d A -> d 2. Produksi Unit Produksi Unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa...
Baca selengkapnya

Sistem Komputer Secara Arsitektur dan Organisasi

-
Gambar
Pengertian : Arsitektur Komputer mempelajari atribut ‑ atribut sistem komputer yang terkait dengan seorang programmer. contoh: set instruksi, aritmetilka yang digunakan, teknik pengalamatan, mekanisme I/0. Organisasi Komputer mempelajari bagian yang terkait dengan unit‑unit operasional computer dan hubungan antara komponen sistem komputer. contoh: sinyal kontrol, interface, teknologi memori. Perbedaan : Arsitektur Komputer   Adalah konsep perencanaan dan struktur pengoperasian dasar dari suatu sistem komputer. Arsitektur komputer ini merupakan rencana cetak-biru dan deskripsi fungsional dari kebutuhan bagian perangkat keras yang didesain (kecepatan proses dan sistem interkoneksinya). Dalam hal ini, implementasi perencanaan dari masing–masing bagian akan lebih difokuskan terutama, mengenai bagaimana CPU akan bekerja, dan mengenai cara pengaksesan data dan alamat dari dan ke memori cache, RAM, ROM, cakram keras, dll). Beberapa contoh dari arsitek...
Baca selengkapnya