Soal UTS TI TEORI KOMPUTASI [PDF]

Citation preview

UNIVERSITAS MUHAMMADIYAH PURWOKERTO FAKULTAS TEKNIK DAN SAINS Alamat : Jl Raya Dukuhwaluh PO Box 202 Purwokerto 53182 Telp. (0281) 636751, Pesawat 130 Fax. (0281) 637239



UJIAN TENGAH SEMESTER GASAL TAHUN AKADEMIK 2020/2021 Mata Kuliah Program Studi/Smt/Kls Hari/Tgl Waktu Dosen Sifat



: Teori Komputasi : Teknik Informatika /V/ A/B : Rabu, 18 November 2020 : 15.15 – 17.15 : Arief Kelik Nugroho, M.Cs : Buka Buku



1. Diketahui sebuah NFA (Q, ∑, δ, S, F). dimana : Q = {q0, q1, q2, q3}, ∑= {0, 1}, S = q0 , F = { q0, q1} δ diberikan dalam tabel transisi berikut : 



0



1



q0



{ q0, q2}



{q3}



q1



{q2,q3}



{q2}



q2



{q3}



{q1}



q3



{0}



{q3}



a. Gambarlah diagram transisi (graf) di atas. b. Buatlah 3 kalimat/string dengan panjang berbeda yang diterima oleh dan 3 kalimat/string dengan panjang berbeda yang ditolak oleh di atas.



2. Diketahui NFA berikut:



……4kn…..