Tugas Matakuliah

  NFA dengan e-move diperbolehkan merubah state tanpa membaca input. disebut dengan e-move karena tidak bergantung pada 1 input saat melakukan transisi. suatu e-move untuk state q1 ke q2 yang terhubung dapat berpindah tanpa menghasilkan inputan apapun. contoh : tanpa membaca inputan : q0 dapat berpindah ke q1 q1 dapat berpindah ke q2 q4 dapat berpindah ke q1 e-closure adalah himpunan state yang dapat di capai dari suatu state tanpa membaca input. e-closure (q0) adalah himpunan state yang dapat dicapai dari state 0 transisi awal : menentukan e-closure : e-closure (q0) = {q0,q1,q2} e-closure (q1) = {q1,q2} e-closure (q2) = {q2} e-closure (q3) = {q3} e-closure (q4) = {q4,q1,q2}

  sasaran kita disini 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 dua state p dan q dari suatu DFA dikatakan indistinguishable apabila : -  indistinguishable , yang berarti tidak dapat dibedakan dua state p dan q dari suatu DFA dikatakan distinguishable jika ada string : reduksi jumlah state pada FSA 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. pasangan 2 buah state memiliki salah satu kemungkinan : distinguishable atau indistinguishable tetapi tidak kedua - duanya, dalam hal ini terdapat sebuah relasi : jika p dan q indistinguishable, dan q dan r indistinguishable, ma...

FSA atau Finite State Automata   adalah tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokkan 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. FSA atau AH (Automata Hingga) didefinisikan sebagai pasangan 5 tupel : 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. mesin ini memiliki 6 state : (q0, q1, q2, q3, q4, q5). state awal q0 sedangkan q3 dan a4 adalah state akhir, dan simbol input adalah (a,d,u). Contoh Finite State Automata diagram transisi : contoh : FSA untuk mengecek parity ganjil Q = {gnp, gjl} ∑ = {0,1} S = gnp F = gjl Definisi Formal FSA M = (Q, ∑, δ, S, F) dimana : Q = himpunan s...

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 "a->b" (bisa dibaca a menghasilkan b, atau dibaca a menurunkan b) a merupakan simbol - simbol pada ruas kiri aturan produksi, sedangkan b merupakan simbol ruas kanan aturan produksi. simbol - simbol tersebut berupa simbol 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 menerapkan aturan produksi, suatu grammar bisa menghasilkan sejumlah stri...