Teori Bahasa & Otomata

Ekuivalensi NFA (Non-deterministic Finite Automata) ke DFA (Deterministic Finite Automata)          Dari sebuah mesin Non-deterministic Finite Automata dapat dibuat mesin DFA yang ekivalen. Ekivalen artinya mampu menerima bahasa yang sama. Simulasi NFA ke DFA Cara simulasi NFA ke DFA adalah dengan menbuat state DFA berkorespondensi dengan set state di NFA. DFA yang dibentuk mencatat semua state yang mungkin pada NFA setelah membaca input tertentu. FSA (Finite State Automata)  FSA terdiri dari : 1. DFA (Deterministic Finite Automata) 2. NFA (Non-deterministic Finite Automata) Ciri DFA dan NFA 1. Ciri DFA (Deterministic Finite Automata) 2. Ciri NFA (Non-deterministic Finite Automata) Proses Ekuivalensi NFA Ke DFA Buat tabel transisi diagram tersebut Buat diagram transisi untuk FSA diatas Setiap State dituliskan sebagai humpunan state {} Buat tabel transisi baru Buat diagram transisi ekuivalensi NFA ke DFA Contoh Lainnya :

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

Pengantar  "Teori Bahasa dan Otomata"               Ilmu komputer memiliki dua komponen utama yaitu model dan gagasan tentang komputasi dan teknik rekayasa untuk perancangan sistem komputasi (perangkat keras dan perangkat lunak). Tujuan mempelajari Teori Bahasa dan Otomata yaitu mengetahui dan mempelajari dasar-dasar teori bahasa formal dan model-model mesin matematis yang menggambarkan prinsip kerja komputer. Definisi Bahasa dan Otomata              Bahasa adalah rangkaian simbol-simbol yang mempunyai makna. Bahasa merupakan kumpulan string-string dari sumbol-simbol untuk suatu alfabet. String sendiri merupakan suatu kata (gabungan dari huruf).  Otomata dapat diartikan sebagai Mesin Abstrak dengan model matematika, dimana sistemnya menerima input dan menghasilkan output, serta terdiri dari sejumlah state (tempat).                    ...