Mohammad Nurfaizy Pangestu

"Finite State Automata" Jenis State Automata : 1.Deterministic Finite Automata (DFA) Otomata berhingga yang pasti (tetap/tertentu)  Dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima  2. Non-deterministic Finite Automata (NFA)  Dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima   Otomata berhingga yang tidak pasti   Untuk NFA harus dicoba semua kemungkinan yang ada sampai terdapat satu yang mencapai state akhir.  Penerapan Finite Automata Mesin asbtrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata. FSA didefinisikan sebagai pasangan 5 Tupel → M = ( Q , ∑ , δ , S , F ). Keterangan : Q : Himpunan hingga state. ∑ (Sigma) : Himpunan hingga simbol input (alfabet). δ (Delta) : Fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol inp

"Pohon Penurunan Tata Bahasa Bebas Konteks" 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. Contoh Soal : 1.  S → AA A → AAA | a | bA | Ab Untai yang dicari : bbabaaba Jawaban : S => A A => b A A => bb A A => bba A => bba A AA => bba A AA => bbab A AA => bbaba A A => bbaba A bA => bbabaab A => bbabaaba Pohon Penurunan : 2. S → AB A → Aa | bB B → a | Sb Untai yang dicari : baabaab Jawaban : S => A B => Aa B => A aSb => b B aSb => baa S b => baa A Bb => baab BB b => baabaab Pohon Penurunan : 3. S → Ba | Ab A → Sa | Aab | a B → Sb | Bba | b Untai yang dicari : bbaaabb

"Penyederhaan Tata Bahasa Bebas Konteks" Sebuah Tata Bahasa Bebas Konteks dapat disederhanakan dengan melakukan : Penghilangan Produksi Useless Penghilangan Produksi Unit Penghilangan Produk Empty Berikut adalah penjelasan dari setiap teknik penyederhanaan : 1. Penghilangan Produksi Useless (a) Produksi Useless adalah produksi yang memuat simbol variabel yang tidak memiliki turunan ke terminal-terminal seluruhnya. (b) Produksi yang tidak akan mencapai turunan apapun dari simbol awal sehingga produksi itu disebut redundan Contoh : S  → Ab | Bcd A → BB | Adc B → Bca | b C → b Kesimpulan : a. A  → Adc tidak memiliki penurunan yang menuju terminal maka dinyatakan useless. b. B → Bca tidak memiliki penurunan yang menuju terminal maka dinyatakan useless. c. yang menyebabkan S → Bcd tidak memiliki penurunan. d. C bersifat redundan Hasil Penyederhanaan : S → Ab A → BB 2. Penghilangan Produksi Unit (a)  Produksi