Semangat Ayo Membaca

Finite State Automata Materi yang akan kita bahasa adalah : 1. Penerapan FSA (Finite State Automata) 2. Penerapan DFA (Deterministic Finite Automata) 3. Penerapan NFA (Nonfeterministic Finite Automata) 4. Ekuivalen antar DFA 5. Reduksi Jumlah State Pembahasannya : 1. Penerapan FSA (Finite State Automata) Finite State Automata atau automata berhingga state, selanjutnya disebut sebagai FSA yaitu suatu model matematika dari suatu sistem yang menerima input dan ouput diskrit. FSA merupakan mesin automta dari bahas regular, suatu FSA memiliki state yang banyaknya berhingga dan dapat berpindah-pindah dari suatu state ke state lain. Perubahan state ini dinyatakan oleh fungsi transisi. FSA tidak memiliki tempat penyimpanan, sehingga kemampuan 'mengingatnya' terbatas, hanya bisa mengingat state yang terkini. Contoh FSA antara lain elevator, text editor, analisa leksikal, protocol komunikasi jaringan dan pencek parity. FSA berdasar pada pendefinisian kemampuan ...

Tata Bahasa Bebas Konteks (POHON PENURUNAN) Hirarky Chomsky Tata Bahasa Bebas Konteks (Context Free Grammar/CFG) Adalah suatu cara yang menunjukkan bagaimana menghasilkan untai-untai dalam sebuah bahasa. Menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis, bagian sintaksis dalam suatu kompilator kebanyakan didefinisikan dalam tata bahasa bebaas konteks. Terbagi menjadi 2 yaitu PARSING dan AMBIGUITAS 1. PARSING Pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) yang disebut akar (root) dan dari situ memiliki lintasan ke setiap simpul. Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurukan simbol-simbol variabel menjadi simbol-simbol terminal. Latihan 1 S → AB A → AAA | a | bA | Ab Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan "bbabaaba" . Jawab : Baca ...

PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS Tujuan Penyederhanaan : Untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti. Misal : Diketahui suatu tata bahasa bebas konteks :            S → AB | a           A → a Kelemahan :            Aturan produksi  S → AB tidak berarti karena B tidak memiliki penurunan Tata Bahasa Bebas Konteks dapat disederhanakan dengan melakukan cara berikut : Penghilangan Produksi Useless Penghilangan Produksi Unit Penghilangan Produksi Empty ℇ/epsilon 1. Penghilangan Produksi Useless Produksi Useless adalah aturan produksi yang tidak menghasilkan terminal-terminal simbol atau aturan produksi yang tidak pernah terjangkau dan tercapai dengan penurunan apapun dari simbol awal sehingga Redudan(berlebih)      Contoh soal...