Soal
dan Jawaban Ujian Akhir Semester Genap
STIKOM
Artha Buana Kupang
Mata
Kuliah : Teori Bahasa dan Otomata
1.
Diketahui DFSA A = (Q, S, d, q0,
F), dimana,
Q = {q0, q1, q2, q3}
∑ =
{ 0, 1 }
S =
q0
F =
{ q0 }
Tabel
Transisi
d
|
1
|
0
|
q0
|
q1
|
q2
|
q1
|
q0
|
q3
|
q2
|
q3
|
q0
|
q3
|
q2
|
q1
|
Buatlah
Diagram State-nya !
Bila
diberikan string :
a. 110110b. 100010
Ujilah string pada point a dan b tersebut, apakah bisa habis dibaca oleh grammar sampai dengan selesai ?
Jawaban :
a. String 110110, apakah diterima atau ditolak oleh mesin grammar di atas ?
Jawaban :
(q0,
110110) ®m(q1, 10110)
®m(q0, 0110)
®m(q2, 110)
®m(q3, 10)
®m((q2, 0)
®m(q0, e)
Dari
penelusuran di atas, maka disimpulkan bahwa string 110110 dapat dibaca dan diterima
oleh mesin tersebut.
b. 100010, apakah diterima
atau ditolak oleh mesin grammar di atas ?
Jawaban :
Jawaban :
(q0,
100010) ®m(q1,
00010)
®m(q3,
0010)
®m(q1,
010)
®m(q3, 10)
®m((q2, 0)
®m(q0, e)
Dari penelusuran di atas, maka disimpulkan bahwa string 110110 dapat dibaca dan diterima oleh mesin tersebut
2. Diketahui sebuah Grammar G=(V, ∑, R, S), dimana V, ∑ dan R
adalah sebagai berikut :
V =
{S, A}
∑ =
{0, 1 }
R = { S à 0AS
S à 0
A à S1A
A à SS
A à 10}.
Buktikan
bahwa string : 00101000100
bisa
diselesaikan oleh grammer tersebut !
Gambarkan
Derivation Tree-nya !
S à0AS
à0S1AS
à001AS
à001S1AS
à00101AS
à00101SSS
à0010100S
à00101000AS
à0010100010S
à00101000100