19 June 2017

Jawaban TBO Kelas A UAS 2017

TBO Kelas A
Soal dan Jawaban
  1.  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