Tugas 9 - Ndfa E-Move [PDF]

Citation preview

TUGAS 9 MATERI NON-DETERMINISTIC FINITE AUTOMATA DENGAN 𝜺-MOVE 1. Buatlah NFA tanpa 𝜀-move yang ekuivalen dengan NFA 𝜀-move pada gambar berikut : (∑= {0, 1, 2}) 0



1



𝜀



q0



2



𝜀



q1



q2



2. Buatlah NFA tanpa 𝜀-move yang ekuivalen dengan NFA 𝜀-move pada gambar berikut : (∑= {0, 1}) 0



𝜀



q0



q1



1



3. Bila diketahui L(M1) adalah Bahasa yang diterima oleh M1 pada gambar A, dan L(M2) daalah Bahasa yang diterima oleh M2 pda gambar B. diketahui L(M3) = L(M1) + L(M2), serta diketahui L(M4) = L(M1)L(M2). Gambarkan : a. Mesin M3 yang menerima Bahasa diketahui L(M3) b. Mesin M4 yang menerima Bahasa diketahui L(M4) GAMBAR A (Mesin M1):



0



1



q0



q1



0,1



GAMBAR B (Mesin M2):



0 0 1



q0



q1



q2



1



1



0



4. Bila diketahui L(M1) adalah Bahasa yang diterima oleh M1 pada gambar C, dan L(M2) daalah Bahasa yang diterima oleh M2 pda gambar D. diketahui L(M3) = L(M1) + L(M2), serta diketahui L(M4) = L(M1)L(M2). Gambarkan : a. Mesin M3 yang menerima Bahasa diketahui L(M3) b. Mesin M4 yang menerima Bahasa diketahui L(M4) GAMBAR C (Mesin M1): b



a a



q0



q1



b



a



b



q2



a



GAMBAR D (Mesin M2) : a



q0



q1



b a



5. Buatlah NFA tanpa 𝜀-move yang ekuivalen dengan NFA 𝜀-move pada gambar berikut : (∑= {a, b}) a q0



b



𝜀



q1



b



q2



𝜀