Siti Amalia Latipah

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 ): simbo...

Teori Bahasa dan Automata Penyederhanaan Tata Bahasa Bebas Kontek Tujuan Penyederhanaan : Tujuan dari penyederhanaan adalah melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau memotong aturan produksi yang tidak perlu. Contoh : S  --> AB | a A  --> a Kelemahannya : aturan produksi AB menjadi tidak berarti karena B tidak memiliki penurunan. Suatu tata bahasa bebas konteks dapat disederhanakan dengan melakukan cara berikut ini : 1. Penghilangan Produksi Useless 2. Penghilangan Produksi Unit 3. Penghilangan Produksi Empty / ( ε )  Epsilon 1. Penghilangan Produksi Useless Produksi Useless adalah : - Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal - terminal seluruhnya (masih ada simbol variabel yang tersisa). - Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal sehingga produksi itu redu...