TBO Kelas A
Soal dan Jawaban
- Diketahui
sebuah mesin otomata DFSA sebagai berikut :
M=(Q,Sδ,s,F), dimana :
Q={q0, q1, q2, q3}
S={0, 1}
S = {q1}
F={q0}
Bila Tabel transisinya sebagai berikut :
Tabel Transisi
|
||
δ
|
0
|
1
|
q0
|
q0
|
q1
|
q1
|
q2
|
q3
|
q2
|
q0
|
q1
|
q3
|
q1
|
q3
|
a. Buatlah Diagram State-nya
b. Ujilah string mana yang bisa habis dibaca dan mana yang tidak habis dibaca , bila diberikan input string berikut ini :
i.
101110
ii.
00 000 100
iii.
0100
Jawaban :
a. Diagram State-nya adalah
sebagai berikut :
b. Untuk string :
i.
101110 akan dibaca oleh mesin dengan urutan sebagai berikut :
(q1,101110) à (q3,01110)
(q1,1110)
(q3,110)
(q3,10)
(q3,0)
(q1,e)
à artinya tidak finish di q0, maka string tersebut
tidak bisa dibaca habis oleh mesin
ii.
00 000 100 akan dibaca oleh mesin dengan urutan sebagai berikut :
(q1, 00000100) à (q2,0000100)
(q0,000100)
(q0,00100)
(q0,0100)
(q0,100)
(q1,00)
(q2,0)
(q0,e)
à artinya finish ditempat yang telah ditentukan, maka
dikatakan bahwa string tersebut bisa habis dibaca oleh mesin.
iii.
0100 akan dibaca oleh mesin dengan urutan sebagai berikut :
(q1, 0100) à (q0,0100)
(q0,100)
(q1,00)
(q2,0)
(q0,e)
à artinya finish ditempat yang telah ditentukan, maka
dikatakan bahwa string tersebut bisa habis dibaca oleh mesin.
2. Diketahui
Expresi Reguler
r = (aa)* (bb)*
b
maka berikan contoh bahasa yang bisa diciptakannya ?
Jawaban :
Untuk bahasa yang diciptakannya mempunyai aturan
bahwa :
r = (aa)* (bb)* b
aa bisa diulang-ulang dengan jumlah pengulangan
terserah
bb bisa diulang-ulang dengan jumlah pengulangan terserah
bisa sama atau tidak dengan aa
Dan diakhir harus diakhiri dengan b
Contoh :
aa bb b
aa aa bb b
aa bb bb b
aa aa bb bb b
aa aa aa bb bb b
Dan seterusnya
No comments:
Post a Comment