Teori Bahasa dan Otomata

 Ekuivalensi dari NFA ke DFA     Ekuivalen artinya sama, pada bahasan materi ini artinya dapat menerima string yang sama baik itu menggunakan mesin Non-Deterministc Finite Automata (NFA) maupun Deterministc Finite Automata (DFA). Sebuah mesin Non-Deterministc Finite Automata (NFA) dapat dibuat menjadi mesin Deterministic Finite Automata(DFA) yang dapat menerima string yang sama. Ada beberapa tahap yang dapat ditempuh untuk melakukan ekuivalensi Non-Deterministc Finite Automata (NFA) ke Deterministc Finite Automata (DFA) :  Buat tabel transisi dari Non-Deterministc Finite Automata (NFA)  Telusuri state berikutnya dengan memanfaatkan tabel transisi ditambah dengan state { }  Tentukan finish baru jika ada, dengan melihat seluruh state yang mengandung finish awal.  Contoh kasus diberikan gambar Non-Deterministc Finite Automata (NFA) berikut :  Diketahui :  Q = {qo,q1}  Σ = {0,1}  S = q0  F = {q1} Buatlah Deterministic Finite Automa...

 Ekuivalensi Antar Deterministic Finite Autamata      Ekuivalensi Antar Deterministic Finite Automata adalah mengurangi jumlah state dari suatu Finite State Automata, dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa. Ada dua buah istilah baru yang perlu kita ketahui yaitu :  • Distinguishable yang berarti dapat dibedakan.  • Indistinguishable yang berarti tidak dapat dibedakan. Contoh Ekuivalensi antar DFA:     Berdasarkan gambar diatas dapat diambil kesimpulan bahwa walaupun kedua gambar DFA diatas bebeda tetapi hasil output yang diterimanya tetap sama yaitu hanya dapat menerima inputan yang mengandung a.           Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu bahasa seperti semula (efisiensi). State pada FSA dapat direduksi apabila terdapat  useless state  Hasil dari FSA yang direduksi merupakan ekivalensi dari FSA semula. P...

 Finite State Automatic     Finite State Automata atau yang dikenal dengan istilah FSA merupakan suatu model mesin otomata dari bahasa reguler. Suatu Finite State Automata dapat memiliki state banyak berhingga yang dapat berpindah-pindah dari suatu state ke state lainnya. Jenis otomata ini tidak memiliki tempat penyimpanan, sehingga kemampuan mengingatnya terbatas.  FSA dipakai untuk penganalisa leksikal dan dipakai juga dalam text editor, pemrosesan teks, dan program file-searching.      Beberapa hal yang harus diketahui berkenaan dengan symbol gambar sebelum memulai materi FSA (Finite State Automata) adalah :  Lingkaran menyatakan state/kedudukan Label pada lingkaran merupakan nama state Busur menyatakan transisi, yaitu perpindahan state/kedudukan Label pada busur merupakan simbol input Lingkaran diawali sebuah busur tanpa label yang artinya state awal Lingkaran ganda menyatakan state akhir/final state FSA atau AH (Automata Hingga) didefinisikan...

 Non Deterministic (NFA)      Non-Deterministic Finite Automata merupakan bagian dari FSA. Non-Deterministic Finite Automata/NFA maksudnya Dari suatu state bisa terdapat 0, 1 atau lebih busur keluar (transisi) berlabel simbol input yang sama. Contohnya : Q = {q0,q2}  ∑ = {a,b}  S = q0  F = {q2}

 Deterministic (DFA)     Deterministic   Finite   Automata   merupakan   bagian   dari   FSA.   Deterministic   Finite   Automata/DFA maksudnya dari suatu state ada tepat satu state berikutnya untuk setiap   simbol   masukan   yang diterima.  DFA, terdiri atas 5 tuple, yaitu : A = ( Q, ∑, δ, S, F ). Notasi Lain DFA : 1. Diagram Transisi / State Diagram  • Tiap keadaan merupakan simpul  • Tiap keadaan q  ∈  Q dan tiap simbol a  ∈   ∑ , dituliskan sebagai  δ (q,a) = p.  Artinya, diagram transisi memiliki panah dari q ke p, yang berlabel a.  • Keadaan awal (q0 ) ditandai dengan adanya panah tanpa sumber.  • Simpul yang menjadi keadaan final ditandai dengan lingkaran bergaris tepi ganda  2. Tabel Transisi  • Representasi daftar dari suatu fungsi  • Baris menunjukkan keadaan dan kolom menunjukkan input.  • Isi dari baris menunjukkan keadaa...

 Grammar dan Bahasa Grammar adalah sebagai kumpulan dari himpunanhimpunan variabel, simbolsimbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi.  Aturan produksi merupakan pusat dari grammar yang menspesifikasikan bagaimana suatu grammar melakukan transformasi suatu string atau karakter ke bentuk lainnya.     Semua aturan produksi dinyatakan dalam bentuk “α → β “ (bisa dibaca α menghasilkan β, atau dibaca α menurunkan β). α merupakan simbol-simbol pada ruas kiri aturan produksi, sedangkan β merupakan simbolsimbol ruas kanan aturan produksi.  Grammar (G) didefinisikan sebagai pasangan 4 tuple :  VT , VN , S, dan Q, dan dituliskan sebagai G(VT , VN , S, Q), dimana :  VT : himpunan simbol-simbol terminal (atau himpunan token-token, atau alfabet)  VN : himpunan simbol-simbol non terminal  S : simbol awal (atau simbol start)  Q : himpunan produks Analisa Penentuan Type Grammar Grammar G1 dengan Q1 = {S → aB, B → bB...