Soal Ujian Teori Bahasa dan Otomata

SOAL UJIAN AKHIR SEMESTER GASAL TAHUN AKADEMIK 2009/2010

FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH MAGELANG

MAGELANG

 

Mata Kuliah       :    Teori Bahasa dan Otomata

Smt / Prodi         :    VI/ S1 Teknik Informatika

Hari / Tanggal     :    Senin / 9 Mei 2011

Waktu                :    75 menit

Dosen                :    Auliya Burhanuddin, S.Si

Sifat                   :    Buku Terbuka, tidak saling pinajm buku, Close Laptop

 

Petunjuk :

a.       Baca soal dengan teliti sebelum mengerjakan. Jangan lupa berdoa.

b.      Tidak ada toleransi bagi siapa saja yang namanya tercatat dalam berita acara ujian dengan alasan apapun.

1.      Dalam Finite State Automata ada berapa pasangan state, sebutkan dan jelaskan maksud tiap symbol nya !

2.      Jika diketahui F = ( { P₀,P₁,P₂,P₃ },{ 0,1 },δ,P₂ , P₃ ).

Dan tabel fungsi transisi :

δ	0	1
P0	P1	P2
P1	P3	P0
P2	{ }	P2
P3	P1, P2	P2

Buatlah diagram transisinya !

3.      Jika diketahui diagram transisi :

Maka buatlah tabel dan tuliskan himpunan FSA nya yang terdiri dari 5 tupel !

4.      Ubahlah NFA berikut menjadi DFA jika diketahui :

A = ( { P₀,P₁,P₂ },{ 0,1 },δ,{P₀} , {P₁} ).

δ	A	b
P0	P1 , P2	P2
P1	P1	P2
P2	{ }	P0 , P2

SELAMAT MENGERJAKAN