Soal-Soal TBO Tentang DFA dan Tabel Transis

Hay blogers,, hari ini saya akan menguji pemahaman saya mengenai DFA dan tabel transis yang berkaitan pada mata kuliah Teori Bahasa Otomata.
Moga aja gak ada yang salah ya,,,.......:D


1.  ({Q0, Q1} {A,B} S,F)

Tabel Transis:

Q	A	B
Q0	Q0	Q1
Q1	Q1	Q0

Q= {Q0,Q1}

∑={A,B}

S=Q0,

F={Q0}

 

Jika M diberi input BBBAABB dengan start awal (Q0 BBBAABB) maka:

(Q0, BBBAABB)=

M (Q1, BBABB)

M (Q0, BAABB)

M (Q1, AABB)

M (Q1, ABB)

M (Q1, BB)

M (Q0, B)

M (Q1, E)

Jadi BBBAABB ditolak oleh M karena bernilai Q1.

  2. a. 1011010

b. 110011

Q= {Q0,Q1,Q2}

S= Q0

F= {Q2}

Jawab:

a.       String= 1011010

(Q0, 1011010)=

M (Q0, 011010)

M (Q0, 11010)

M (Q0, 1010)

M (Q0, 010)

M (Q0, 10)

M (Q0, 0)

M (Q0, E)

Jadi, 1011010 tidak diterima oleh M.

b.      String= 110011

(Q0, 110011)=

M (Q0, 10011)

M (Q0, 0011)

M (Q0, 010)

M (Q0, 11)

M (Q0, 1)

M (Q0, E)

Jadi, 110011 tidak diterima oleh M.

   3.  DFA-nya:

Q= {Q0,Q1,Q2,Q3}

∑= {A,B}

S= Q0

F= {Q2}

Tabel Transis:

Q	A	B
Q0	Q3	Q1
Q1	Q2	Q0
Q2	Q2	Q3
Q3	Q0	Q1

 

String = ABABBA

(Q0, ABABBA)=

M (Q3, BABBA)

M (Q1, ABBA)

M (Q2, BBA)

M (Q3, BA)

M (Q1, A)

M (Q2,E)

Jadi, ABABBA diterima oleh M.

Sekian postingan saya, moga bermanfaat,,,.....
Until Next Time,,,....:)