Teori Bahasa & Otomata

 Ekuivalensi Antar Deterministic Finite Automata (DFA)            Tujuan kita adalah mengurangi jumlah state dari suatu finite state automata, dengan tidak mengurangi kamampuannya semula untuk menerima suatu bahasa.  Ada 2 istilah yang perlu kita ketahui yaitu : Distinguishable : dapat dibedakan Indistinguishable : tidak dapat dibedakan Reduksi Jumlah State Pada FSA           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 . Useless State yaitu bukan state awal, tidak menerima nilai input dari state lain tetapi memberikan nilai input ke state lain. Hasil dari FSA yang direduksi merupakan ekuivalensi dari FSA semula. Pasangan State dapat dikelompokkan berdasarkan :  Distinguishable State (dapat dibedakan) Indistingushbale (tidak dapat dibedakan) Reduksi Jumlah State...

 FSA (Finite State Automata) &  DFA (Deterministic Finite Automata) Definisi Formal FSA  M = (Q, Σ, 8, S, F)  dimana :  Q = himpunan state Σ = abjad, himpunan simbol input/masukan 8 = fungsi transisi, 8 = Q * Σ -> Q S = state awal / initial state F = himpunan state akhir / final state Jenis DFA Deterministik (DFSA/DFA) Pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini. Non - Deterministik (NFSA/NFA) Pada setiap input terdapat lebih dari satu keadaan tujuan dari keadaan saat ini. Contoh DFA  Contoh DFA yang dapat menerima string berakhiran 01  A = ({q0, q1, q2}, {0, 1}, 8, q0, {q2}) dengan fungsi transisi 8 diberikan dalam bentuk table : Contoh Lainnya :

  " Derivasi Kalimat & Penentuan Bahasa " Grammar dan Bahasa      Grammar adalah sebagai kumpulan himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, dibatasi oleh 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 " alpa -> beta " (bisa dibaca alpa menghasilkan beta , atau dibaca alpa menurunkan beta ). Alpa merupakan simbol-simbol pada ruas kiri aturan produksi, sedangkan beta merupakan simbol-simbol ruas kanan aturan produksi.       Simbol-simbol tersebut dapat berupa imbol terminal (V T ) atau simbol NON-Terminal (V N )/Variabel. Simbol V N adalah simbol yang masih dapat diturunkan, biasanya identik dengan huruf besar ('A','B','C'). Simbol V T  adalah simbol yang sudah tidak dapat diturunkan lagi, biasanya identik dengan hur...