Teori Bahasa Otomata UTS

1. Finit State Automata (FSA)

FSA adalah Suatu mesin abstrak yang digunakan untuk merepresentasikan  penyelesaian suatu persoalan dari suatu sistem diskrit. Finite State Automata merupakan suatu tool yang berguna untuk merancang sistem nyata.

Gambar FSA

Finite State Automata dinyatakan oleh pasangan 5 tuple

Bentuk formal dari gambar FSA diatas adalah seperti berikut :

• M = ( Q, Σ, δ, S, F)
• Q = {q0, q1, q2, q3, q4, q5}
• Σ = {0, 1}
• S = { q0 }
• F = { q3 & q4 }

Jika dimasukan string berikut dari gambar FSA diatas tentukan apakah ditolak atau di terima !

1. adaua
2. adauu
3. addau
4. adadu
5. addaa
6. audad

Jawab

2. GRAMMAR

Secara formal Grammer dinyatakan dengan 4-tuple atau G=( V, T, P, S)

Kita tentukan bahasa formalnya.

V = { S, A, B, D}

T = { 0,1 }

P = { S => 1A|S =>1B|S => 0S|A =>1A|A =>1|B =>1B|B=>0S|B=>1D|D=>0 }

S = {S}

Buka aplikasi JFLAP kemudian pilih Grammar, seperti pada gambar di bawah ini :

Kemudian akan muncul tampilan seperti berikut, lalu input : P = { S => 1A|S =>1B|S => 0S|A =>1A|A =>1|B =>1B|B=>0S|B=>1D|D=>0 } 

Langkah selanjutnya adalah pilih convert kemudian pilih Convert-Right Linear Grammar to FA, dan setelah muncul grafiknya lalu klik tombol Show All untuk menampilkan grafik secara lengkap, sehingga akan menampilkan innformasi seperti pada gambar dibawah ini :

maka hasil UAS seperti ini