Teori Bahasa dan Otomata

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)  Contoh : Berikut table transisi dan diagram transisi untuk NFA :   Dapat dilihat dari gambar di atas ada suatu state yang diberi inputan menuju ke beberapa state, yaitu S0 yang diberi inputan b bisa menuju ke S0 dan S1 Lalu dikonversi menjadi DFA, dengan cara membuat state baru berupa gabungan dari S0 dan S1. Lalu untuk state {S0,S1} jika diberi inputan a maka hasilnya adalah gabungan dari hasil S0 dan S1 yang diberi inp

"Ekuivalensi Antar Deterministic Finite Automata (DFA)" Sasaran kita di sini 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. Reduksi Jumlah State Pada FSA Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangikemampuan 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. Pasangan State dapat dikelompokkan berdasarkan : 1.       Distinguishable State (dapat dibedakan) : Dua state p dan q dari suatu DFA dikatakan indistinguishable apabila: • δ(q,w) Î F dan δ(p,w) Î F atau δ(q,w) ∉ F dan δ(p,w) ∉ F • untuk semua w Î S* 2.       Indistinguishable State (tidak dapat dibedakan) : Dua

 "Finite State Automata"           FSA (Finite State Automata) merupakan tool yang sangat bergunadalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokan karakter-karakter kedalam sebuah token, yang berupaunit terkecil seperti nama, variabel, dan keyword.            FSA dipakai untuk penganalisa leksikal dan dipakai juga dalam text editor, pemrosesan teks, dan program file-searching. FSA atau AH (Automata Hingga) didefinisikan sebagai pasangan 5 tupel → M = (Q, ∑, δ, S, F). Q : himpunan hingga state  ∑ : himpunan hingga simbol input (alfabet) δ : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input. Fungsi transisi ini biasanya diberikan dalam bentuk tabel. S : state AWAL F : himpunan state AKHIR • Mesin ini memiliki 6 state : (q0,q1,q2,q3,q4,q5).  • State awal q0, • Sedangkan q3 dan q4 adalah state akhir, dan  • Simbol input adalah (a,d,u) Contoh Finate State Automata :  •Contoh : FSA untuk mengecek parity ganjil  •Q =

  " 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 (VT) atau simbol NON-Terminal (VN)/Variabel. Simbol VN adalah simbol yang masih dapat diturunkan, biasanya identik dengan huruf besar ('A','B','C'). Simbol VT adalah simbol yang sudah tidak dapat diturunkan lagi, biasanya identik dengan huruf kecil ('a','b','c'). Dengan menera

  " Hirarki Chomsky " Apa itu Chomsky Hierarchy? Hirarki Chomsky merupakan tata Bahasa (Grammar) atau yang bisa didefinisikan secara formal sebagai kumpulan dari himpunan - himpunan variable, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan - aturan produksi. Pada tahun 1959 seorang ahli bernama Noam Chomsky melakukan pengelompokkan tingkatan bahasa menjadi empat level, yang akan dibahas di bawah ini. Regular Grammar (Level/Tipe 3 ) . Aturan : Simbol sebelah kiri harus berupa simbol variabel. Simbol sebelah kanan maksimal hanya memiliki simbol variabel dan bila ada terletak di paling kanan. Misal :  A → e (diterima) A → fgh (diterima) A → eH (diterima) C → D (diterima) A → Bc (ditolak) Context-Free (Level/Tipe 2) Aturan : Simbol sebelah kiri harus simbol variabel. Misal :  B → CDeFG (diterima) D → BcDe (diterima) a → b (ditolak) Context-Sensitive (Level/Tipe1) Aturan : Simbol pada ruas sebelah kiri harus minimal ada sebuah variabel. |a| ≤ |b| artinya ruas sebela

"Pengantar Teori Bahasa dan Otomata" 1. Pengertian  Bahasa = Bahasa bisa juga disebut sebagai rangkaian simbol-simbol yang mempunyai makna. Otomata = Otomata merupakan suatu sistem yang terdiri atas sejumlah state, di mana state menyatakan informasi mengenai input. Otomata juga dianggap sebagai mesin otomatis (bukan mesin fisik) yang merupakan suatu model matematika dari suatu sistem yang menerima input dan menghasilkan output.                     Hubungan di antara bahasa dan otomata adalah bahasa dijadikan sebagai input oleh suatu mesin otomata, selanjutnya mesin otomata akan membuat keputusan yang mengindikasikan apakah input itu diterima atau ditolak. Misalnya, kita memiliki sebuah mesin sederhana yang menerima input kata dalam bahasa Indonesia, hal ini bisa dilihat pada gambar DISAMPING :  Pada gambar di samping, bila mesin mendapat string input berikut :  1.ada : diterima  2.adu : diterima  3.add : ditolak  PENJELASAN : Sebuah string input diterima bila mencapai st