Deterministik Finite State Automata (DFSA)

DFSA

Membuat sebuah State Diagram dari Deterministik Finite State Automata (DFSA) dan diberi input “xxxyyxy”, apakah diterima atau ditolak oleh mesin (M).

M = (Q, S, d, s, F), dimana :

Q = {q₀, q₁, q₂},

S = {x,y},

s = q₀,

F = {q₁} 

Tabel Transisi
d	x	y
q0	q0	q1
q1	q2	q0
q2	q1	q2

State Diagram 

 

Jika M diberi input “xxxyyxy”, dengan state awal (q₀, xxxyyxy), maka :

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

                 ├_M (q₀, xyyxy)

                 ├_M (q₀, yyxy)

                 ├_M (q₁, yxy)

                 ├_M (q₀, xy)

                 ├_M (q₀, y)

                 ├_M (q₁, e)

Karena (q₀, xxxyyxy) ├*_M (q₁,e), jadi “xxxyyxy” diterima oleh M 

Selanjutnya....

     Berdasarkan sebuah State Diagram dari Deterministik Finite State Automata (DFSA),  berikanlah input “101010” dan “110011”  apakah diterima atau ditolak oleh mesin (M).

DFSAnya adalah sebagai berikut :

Q = {q0 , q1 , q2 , q3 }

S = {0,1}

S = q0

F = { q0}

 

Tabel Transisi
d	0	1
q0	q2	q1
q1	q3	q0
q2	q0	q3
q3	q1	q2

a.       Jika M diberi input “101010”, dengan state awal (q₀, 101010), maka :

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

                 ├_M (q₃, 1010)

                 ├_M (q₂,010)

                 ├_M (q₀, 10)

                 ├_M (q₁, 0)

                 ├_M (q₃, e)

Karena (q₀, 101010) ├*_M (q₃,e), jadi “101010” ditolak oleh M

b.      Jika M diberi input “110011”, dengan state awal (q₀, 110011), maka :

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

                 ├_M (q₀, 0011)

                 ├_M (q₂, 011)

                 ├_M (q₀, 11)

                 ├_M (q₁, 1)

                 ├_M (q₀, e)

Karena (q₀, 110011) ├*_M (q₀,e), jadi “110011” diterima oleh M