UJIAN TENGAH SEMESTER GENAP 2014/2015
TEORI BAHASA DAN OTOMATA (TIF 2412)
1. (Materi : Ekivalensi NFA ke DFA, bobot 20%)
Desainlah sebuah NFA (dengan 4 state) yang dapat menerima inputan {ab, ba}
dan gunakanlah mesin tersebut untuk menemukan sebuah DFA yang dapat \
menerima inputan yang sama.
2. (Materi : Ekivalensi NFA ke DFA, bobot 20%)
Tentukanlah DFA (Deterministic Finite Automata) yang ekivalen dari NFA (Non-
Deterministic Finite Automata) berikut ini!
3. (Materi : NFA dengan e-move, bobot 10%)
Apa yang dimaksud -move dan -closure? Berikan penjelasanmu!
4. (Materi : Ekspresi Reguler, bobot 20%)
a. Tentukan (2 bentuk) ekspresi regular dengan input = {a,b} pada bahasa
{ : 0} 1
L = a b m > m m
b. Tentukan ekspresi regular dengan input = {a} pada bahasa
{ : 0} 2 1
1
= >
+ L a n n
c. Tentukan ekspresi regular dengan input = {a,b} pada bahasa
{ : , 0} 2 2 1
1
= ³
+ L a b n m n m
d. Tentukan semua string yang dapat dibangkitkan dari ekspresi
L((a+b)*b(a+ab)*) dengan panjang string kurang dari 4 karakter
5. (Materi : Aturan Produksi FSA, bobot 20%)
Buatlah finite otomata dari kumpulan aturan produksi pada tata bahasa regular,
berikut : (symbol awal adalah A, = {0,1})
A 0B|1D|0
B 0D|1C
C 0B|1D|0
D 0D|0
6. (Materi : FSA dengan Output, bobot 10%)
Jelaskan mengapa final state dari mesin moore dan mealy dihilangkan? Berikan
analisamu!
QUIZ 1 SEMESTER GENAP 2014/2015
TEORI BAHASA DAN OTOMATA (TIF 2412)
Buatlah resume dari setiap judul presentasi kelompok, yaitu :
1. FSA
2. Ekivalensi NFA ke DFA
3. NFA dengan e-move
4. Ekpresi regular
5. Aturan Produksi FSA
6. FSA dengan output
