Siti Amalia Latipah

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

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