Soal dan Jawaban TBO - UAS 2018

Soal dan Jawaban Ujian Akhir Semester Genap

STIKOM Artha Buana Kupang

Mata Kuliah : Teori Bahasa dan Otomata

1.      Diketahui DFSA A = (Q, S, d, q₀, F), dimana,

    Q = {q_0, q_1, q_2, q₃}

    ∑ = { 0, 1 }

    S = q₀

    F = { q₀ }

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. 110110
b. 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 :

                            (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 !

Untuk 00101000100, parsingnya adalah :

S à0AS

à0S1AS

à001AS

à001S1AS

à00101AS

à00101SSS

à0010100S

à00101000AS

à0010100010S

à00101000100