SOAL UJIAN SISIPAN SEMESTER GENAP TA 2004/2005

SOAL UJIAN SISIPAN SEMESTER GENAP TA 2010/2011JURUSAN S1 TEKNIK INFORMATIKA STMIK AMIKOM YOGYAKARTA

MATA UJIAN : TEORI BAHASA DAN OTOMATA

WAKTU : 75 MENIT

DOSEN: DRS. JANOE HENDARTO MKOM

SIFAT

: OPEN BOOKS

TANGGAL: 10 MEI 2011

1. a. Menurut saudara apa saja manfaat kita belajar teori bahasa dan otomata dan seberapa penting peranan simbol dalam ilmu pengetahuan dan teknologi. b. Buatlah 3 produksi dari grammar bahasa pemrograman yang saudara kuasai, kemudian dari 3 produksi yang saudara buat tunjukkan apa saja simbol terminalnya dan apa saja simbol non terminalnya.

2. Diketahui grammar G(V, V, S, P) dimana :

V = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, *, / }

V = {S, A, O, T}

S ( V

P = { O ( +| - | * | / A ( 0| 1| 2| 3| 4| 5| 6| 7| 8| 9

S ( AT | A T ( OA | OS

}

a. G termasuk grammar tipe berapa? Berikan alasannya.

b. Buatlah 7 kalimat dengan panjang berbeda yang dapat diturunkan dari grammar G.

c. Tentukan ciri ciri umum kalimat dari grammar G tersebut.

3. Diketahui sebuah DFA (Q, , , S, F). dimana :

Q = {q0, q1, q2, q3, q4}, diberikan dalam tabel transisi berikut :

= {a, b, c} abc

S = q0q0q1q4q4

F = {q3}q

q1q2q1

q2q2q2q3

q3q2q2q3

q4q4q4q4

a. Gambarlah diagram transisi (graf) dari DFA di atas.

b. Buatlah 5 kalimat dengan panjang berbeda yang diterima oleh DFA di atas dan Buatlah 5 kalimat dengan panjang berbeda yang ditolak oleh DFA di atas.

c. Tentukan bahasa yang dikenali oleh otomata di atas._1030195789.unknown

_1034256146.unknown

_1030195788.unknown