RANGKUMAN TEORI BAHASA DAN OTOMATA

 NFA Dengan E-Move 1. Pengertian       NFA dengan E-Move (transisi E-Move), diperbolehkan merubah State tanpa membaca input. Disebut dengan E-Move karena tidak bergantung pada 1 input saat melakukan transisi. E-Move Berada Pada Transisi State apabila Sebuah transisi mempunyai input / output / E-Move dan Suatu E-Move untuk state q1 ke q2 yang tehubung dapat berpindah tanpa menghasilkan inputan apapun pada transisi nya 2. E-Closure      E-Closure adalah himpunan state yang dapat di capai dari suatu state tanpa membaca input. Pada suatu state yang tidak memiliki E-Move, maka E-Closure nya adalah state itu sendiri 3. Contoh soal  Langkah - Langkah : 1. Buat table Transisi NFA E-Move dari diagram NFA semula 2. Cari E-Closure untuk setiap NFA 1. E-Closure (q0) = {q0, q1} 2. E-Closure (q1) = {q1} 3. E-Closure (q2) = {q2} 4. E-Closure (q3) = {q3}  3. Cari setiap fungsi transisi hasil perubahan dari...

 Ekuivalensi NFA ke DFA 1. Pengertian       Dari sebuah mesin Non-Deterministic Finite Automata dapat dibuat mesin Deterministic Finite              Automata-nya yang ekuivalen (bersesuaian). Ekuivalen di sini artinya mampu menerima bahasa yang      sama. Sebagai contoh, akan dibuat DFA dari DFA sebagai berikut : Dikertahui E = {0,1} Langkah - langkah : 1. Buat Table transisi dari diagram transisi tersebut 2. Buat diagram transisi untuk Finite State Automata dari tabel transisi di atas. 3. Table Transisi Ekuivalensi NFA ke DFA 4. Diagram Transisi Ekuivalensi NFA ke DFA

 Ekuivalensi Antar Deterministic Finite Automata A. Pengertian        Untuk suatu bahasa regular,kemungkinan ada sejumlah Deterministic Finite Automata yang dapat menerimanya. Perbedaannya hanyalah jumlah state yang dimiliki otomata-otomata yang saling ekuivalen tersebut. Tentu saja, dengan alasan kepraktisan, kita memilih otomata dengan jumlah state yang lebih sedikit.   Sasaran kita di sini adalah mengurangi jumlah state dari suatu Finite State Automata, dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa. istilah baru yang perlu diketahui : 1. Distinguishable, yang berarti dapat dibedakan 2. Indistinguishable, yang berarti tidak dapat dibedakan B. 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. Hasil dari FSA yang direduksi merupak...

 Finite State Automata A. Pengertian       FSA (Finite State Automata) adalah alat atau tool yang berguna dalam merancang lexical analyzer,          yaitu bagian dari kompilator yang mengelompokan karakter-karakter ke dalam sebuah token, yang          berupa unit terkecil seperti nama, variabel, dan keyword. FSA dipakai untuk penganalisa leksikal dan     dipakai juga dalam text editor, pemrosesan teks, dan program file-searching B. Contoh Implementasi           Keterangan :      1. Mesin ini memiliki 6 state : (q0,q1,q2,q3,q4,q5).       2. State awal q0      3. Sedangkan q3 dan q4 adalah state akhir, dan       4. Simbol input adalah (a,d,u) C. Jenis FSA     1. DFA ( Deterministic)           Pada setiap input, hanya ada satu keadaan (st...

 Grammar dan Bahasa A. Pengertian  Grammar adalah sebagai kumpulan dari himpunan - himpunan variabel, simbol- simbol 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 “α → β “ (dibacanya α menghasilkan β, atau α menurunkan β. α merupakan simbol-simbol pada ruas kiri aturan produksi, sedangkan β merupakan simbolsimbol ruas kanan aturan produksi. B. Macam - macam Simbol 1. Simbol Variabel (Vn)     Adalah simbol yang masih dapat diturunkan, identik  dengan huruf besar (‘A’,’B’,’C’). 2. Simbol Terminal (Vt)     adalah simbol yang  sudah tidak dapat diturunkan lagi, biasanya identik dengan huruf kecil (‘a’,’b’,’c’) C. Grammar sebagai pasangan 4 tuple 1. VT : himpunan simbol-simbol terminal (atau himpun...

A. Pengantar Teori Bahasa dan Otomata 1. Bahasa Bahasa adalah rangkaian simbol - simbol yang mempunyai makna 2. Otomata Otomata merupakan sebuah sistem yang terbangun dari sejumlah State yang menyatakan informasi mengenai input. Otomata seringkali dianggap sebagai sebuah mesin otomatis (bukan mesin fisik) yang merupakan mpde; matematika dari sistem yang menerima input dan menghasilkan output. 3. Hubungan Bahasa dan Otomata      Bahasa Dijadikan sebagai input oleh mesin otomata, lalu mesin otomata akan membuat keputusan apakah input tersebut diterima atau ditolak   Pada gambar di samping, bila mesin mendapat string input berikut :  1.ada : diterima  2.adu : diterima  3.add : ditolak Penjelasan :  1. Sebuah string input diterima bila mencapai state akhir / final state yang pada contoh diatas digambarkan dengan lingkaran ganda.  2. Mesin ini memiliki 6 state yaitu { q0, q1, q2, q3, q4, q5 } yang merupakan himpunan state yang ada pada mesin terse...