8 0 116 KB
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…..