TEORI BAHASA DAN AUTOMATA

Tata bahasa bebas konteks Adalah suatu cara yang menunjukkan bagaimana menghasilkan untai-untai dalam sebuah bahasa. Tidak terdapat pembatas hasil produksinya.Pada aturan produksi :a →bBatasannya hanyalah ruas kiri adalah sebuah simbol variabel. Seperti kita ketahui pada saat menurunkan suatu string simbol-simbol variabel akan me!akili bagian yang belum terturunkan. Saat penurunannya telah lengkap semua bagian yang belum terturunkan telah diganti oleh srting-string dari himpunan simbol terminal POHON PENURUNAN 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. PARSING Sebuah pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node/vertex) disebut akar (root)dan dari suatu titik m...

Latihan Penyederhanaan Tata Bahasa Bebas Konteks Penyederhanaan dengan penghilangan produksi useless Soal latihan 1 S → aB | C B → e | Ab C → bCb | adF | ab F → cFB Jawab : B → Ab (A tidak punya penurunan) C → adF (F tidak punya penurunan) F → cFB (F tidak punya penurunan yang menuju simbol terminal) Jadi, setelah disederhanakan : S → aB | C B → e C → bCb | ab Soal Latihan 2 S → Aa | B A → ab | D B → b | E C → bb E → aEa   Jawab : A → D (A tidak punya penurunan) C → bb (C → bb adalah redudant) Simbol variabel E tidak memiliki aturan produksi menuju terminal E → aEa (E tidak punya penurunan ke terminal) B → E ( E tidak punya penurunan) Jadi, setelah disederhanakan : S → Aa | B A → ab B → b Penyederhanaan dengan penghilangan produksi unit Soal Latihan 1 S   → Aa | B B→ A | bb A → a | bc | B Jawab : Penggant...