Diagram Finite State Automata (DFSA) _TugasTeori Bahasa Otomata

Posted by : Lenny Bubun Rabu, 12 Maret 2014

Diagram Finite State Automata (DFSA)

Hi ... Postingan kali ini kita membahas tentang Diagram Finite State Automata (DFSA) yang merupakan bagian dari FSA yang dalam pengertiannya dipahami sebagi sebuah mesin yang diakali untuk membaca string, sehinggah maksud mesin disini bukan secara fisik tetapi bersifat abstrack. kita langsung saja ke point permasalahnnya :

1. Ada sebuah mesin dengan dengan tabel transisi seperti gambar dibawah!! Mesin tersebut diberi saja nama M sehinngah :
M = {Q, ∑, ∂,S,F}
Q = {Q0, Q1, Q2}
∑ = {X,Y}
S= Q0
F = Q1

Tabel Transisi

δ	X	Y
Q0	Q0	Q1
Q1	Q2	Q0
Q2	Q1	Q2

- Kondisi Diagram (state Diagram) yang terjadi dimana masih identik dengan tabel transisi diatas sebagi berikut :

Berdasarkan Tabel Transisi maupun stste diagram disamping, bila diberi input string xxxyyxy maka :

(Q₀,xxxyyxy) ├_M (Q₀,xxyyxy)

├_M (Q₀,xyyxy)

├_M (Q0,yyxy)

├_M (Q₁,yxy)

├_M (Q₀,xy)

├_M (Q₀,y)

├_M (Q₁,e)

Karena (Q₀,xxxyyxy) ├*_M (Q₁,e), jadi string xxxyyxy diterima oleh mesin M

2. Diketahui sebuah mesin M memiliki Q = {Q0, Q1, Q2}, ∑ = {0,1}, S = {Q0}, F = { Q1} dan diberi input string 101010 dan 110011 serta mempunyai tabel transisi seperti gambar berikut! maka :

- Untuk Inputan string 101010 :
oleh karena start di Q0 maka :

(Q₀,101010) ├_M (Q₁,01010)

├_M (Q₃,1010)

├_M (Q2,010)

├_M (Q₀,10)

├_M (Q₁,1)

├_M (Q₀,e)

Karena (Q₀,101010) ├*_M (Q₀,e), maka string 101010 ditolak oleh mesin M disebabkan Finish tidak sesuai, dimana yang seharusnya berhenti di Q1

- Untuk Inputan string 110011 : oleh karena start di Q0 maka :

(Q₀,110011) ├_M (Q₁,10011)

├_M (Q₀,0011)

├_M (Q2,011)