Latihan Soal Tbo

  • Published on
    03-Jul-2015

  • View
    1.000

  • Download
    22

Embed Size (px)

Transcript

TEORI BAHASA OTOMATA CONTOH SOAL (fradika Indrawan)

Latihan Soal TBO 1. Diketahui Q = {q0, q1, q2, q3} , = {a,b}, S= q0, F= q2, dengan tabel transisi sebagai berikut : a b q0 q1 q2 q3 a. Buat graf trans isinya b. Konversikan ke NFA tanpa 2. Diketahui sebuah NFA (Q, , d , S, F). dimana : Q = {q d diberikan dalam tabel transisi berikut : F = {q 4 }, 0 1 q0 q1 q2 q3 q4 {q3} {q2} - {q3} {q3,q4} {q1,q4} - 0

q3 q1 q0 q1 - q2 - - q2 - q3 q2

, q 1 , q 2 , q 3 , q 4 }, = {0, 1}, S = q

0

,

a. Gambarlah diagram transis i (graf) dari NFA di atas. b. Konversi graf NFA diatas ke DFA, tentukan 2 string yang diterima dan ditolak 3. Dik etahui sebuah mesin M1 sebagai berik ut :

0

q0

1 0,1

q1 q2

q2

Dan M2 sebagai berikut :

a. Gambarkan mesin M3 yang menerima bahasa L (M3) sebagai gabungan M1 dengan M2. b. Gambarkan mesin M4 yang dapat menerima bahasa M1 dan atau M2.

TEORI BAHASA OTOMATA CONTOH SOAL (fradika Indrawan)

JAWABAN SOAL

LATIHAN

1. A. Graf Transisi

B. Konversi NFA

e ke NFA a b closur q0 q3 q1 q0 q1 q1 - q1,q2 q2 - - q2 q3 - q3 q2,q3 e

d (q0,a) = cl= cl= cl= q2,q3 d (q1,a) = cl= cl= cl= q1,q2 d (q2,a) = cl= cl= cl= d (q3,a) = cl= cl= cl=

e(d(cl - e (q0),a)) e(d(q0,a)) e(q3) e(d(cl - e (q1),a)) e(d(q1,q2,a)) e(q1) e(d(cl - e (q2),a)) e(d(q2,a)) e() e(d (cl- e (q3),a)) e(d(q2,q3,a)) e()

d (q0,b) = cl= cl= cl= q1,q2 d (q1,b) = cl= cl= cl= d (q2,b) = cl= cl= cl= d (q3,b) = cl= cl= cl= q2,q3

e(d(cl - e (q0),b)) e(d(q0, b)) e(q1) e(d(cl - e (q1),b)) e(d(q1,q2,b)) e( ) e(d(cl - e (q2),b)) e(d(q2,b)) e() e(d(cl - e (q3),b)) e(d(q2,q3,b)) e(q3)

Table transisi yang baru a b q0 q2,q3 q1,q2 q1 q1,q2 q2 - q3 - q2,q3

TEORI BAHASA OTOMATA CONTOH SOAL (fradika Indrawan)

e yang mengandung unsure State akhir dr graf NB : state akhir ditentukan dari Closur sebelumnya (state akhir q2, qo closur e-nya q0, q1 closur e-nya {q1, q2}, q2 closur e-nya q2, q3 closur e-nya {q2,q3}) brrti s tate ak hirnya q1,q2,q3 2. A. Gambar Graf Transisi NFA

B. Konversi ke DFA Table transisi yang baru 0 1 q0 q1 q2 q1 q3 q2 q3,q4 q3 q1,q4 q4 q3,q4 q1,q4 q1,q4 q3

TEORI BAHASA OTOMATA CONTOH SOAL (fradika Indrawan)

Graf Transisi DFA hasil konversi dari NFA

q01

0 0,1 0 null 1 0,1

q11

1

q30 0

1

q1, q4

q2

0

1 0

q4 q3, q4

Penggabungan dan Penyambungan Mesin M3(Penggabungan)

0

q0e/ qs

1 0,1

q1

q22

e/

qF e/ e/ a a q1 q2 q0 q3 e/ e/

Mesin M4(Penyambungan)

0

e/

q0 e/

1 0,1

q1

q22

a a q1 q2 q0 q3

e/