haidaroh blog: Soal dan Jawab TBO

19 June 2014

Soal dan Jawab TBO - UAS Genap 2013-2014

Soal dan Jawaban Ujian Akhir Semester Genap
STIKOM Artha Buana Kupang
Mata Kuliah : Teori Bahasa dan Otomata

1. Diketahui sebuah Grammar G=(V, ∑, R, E), dimana V, ∑ dan R adalah sebagai berikut :
V = {x, 1, 2, +, *, (, ), T, F, E}
∑ = {x, 1, 2, +, *, (, ) }
R = { E ==> E + T, R1
E ==> T,   R2
T ==> T * F, R3
T ==> F,   R4
F ==> (E), R5
F ==> x1, R6
F ==> x2}. R7

Buktikan bahwa string ini (x1*x2+x1)*(x1+x2) bisa dibaca oleh Grammar tersebut !
Gambarkan Derivation Tree-nya !

Jawaban
E => T 1   RULE 2

=>T*F 2   RULE 3
=>T*(E) 3   RULE 5
=>T*(E+T)   4   RULE 1
=>T*(T+T)   5   RULE 2
=>T*(F+T)   6   RULE 4
=>T*(x1+T) 7   RULE 6
=>T*(x1+F) 8   RULE 4
=>T*(x1+x2) 9   RULE 7
=>F*(x1+x2) 10 RULE 4
=>(E)*(x1+x2) 11 RULE 5
=>(E+T)*(x1+x2) 12 RULE 1
=>(E+F)*(x1+x2) 13 RULE 4
=>(E+x1)*(x1+x2) 14 RULE 6
=>(T+x1)*(x1+x2) 15 RULE 2
=>(T*F+x1)*(x1+x2) 16 RULE 3
=>(F*F+x1)*(x1+x2) 17 RULE 4
=>(F*x2+x1)*(x1+x2) 18 RULE 7
=>(x1*x2+x1)*(x1+x2) 19 RULE 6

2. Diketahui DFSA A = (Q, ∑, d, S, F), dimana,
Q = {q0, q1, q2, q3}
∑ = { a, b }
S = q0
F = { q0 }
Tabel Transisi :

Buatlah Diagram State-nya !
Bila diberikan string bbabba, apakah mesin tersebut bisa menerima atau ditolak ?

Jawaban :
String bbabba, apakah diterima atau ditolak oleh mesin di atas ?
(q0, bbabba) =>m(q1, babba)

Gambar 2. Diagram State

  =>m(q0, abba)
  =>m(q2, bba)
  =>m(q3, ba)
  =>m((q2, a)
  =>m(q0, e)

Dari penelusuran di atas, maka disimpulkan bahwa string bbabba dapat dibaca dan diterima oleh mesin tersebut.

3. Diektahui sebuah Grammar G=(V, ∑, R, S), dimana V, ∑ dan R adalah sebagai berikut :
V = {S, A}
∑ = {a, b }
R = { S => aAS
S => a
A => SbA
A => SS
A => ba}.

Buktikan bahwa string ini (x1*x2+x1)*(x1+x2) bisa dibaca oleh Grammar tersebut ! Ralat : String yang diberikan adalah : aababaaabaa dan aaaaabbaa
Gambarkan Derivation Tree-nya !

Untuk aababaaabaa, parsingnya adalah :
S =>aAS