Automata Theory

Kisi kisi tba 2009
1. a,b. Finite Automata dengan Output
Kisi - kisi : Soal Teori mengenai Moore Machine
2. a,b. Regular Expression vs CFG
Kisi - kisi : Diketahui RE, ditanya NFA dan CFG
3. a,b. CFG
Kisi - kisi : Diketahui CFG, ditanya CGF no useless symbol dan CNF
4. CFG
Kisi - kisi : Diketahui CFG, ditanya GNF
5. a,b. Push Down Automata
Kisi - kisi : Diketahui PDA, ditanya ID dan bentuk umum bahasa

Contoh soal :

Grammar G = {{S,A,B,C,D},{a,b},P,S}
dengan produksi P:
S -> aA | BD C -> b | bS | aAA
A -> a | aS | bCC D -> bD | DB
B -> aB | BD
Tuliskan grammar G1 (ekuivalen G) yang tidak mengandung useless symbol.


Cari bentuk Chomsky Normal Form (CNF) untuk grammar berikut :
S -> AB | CA
A -> a
B -> BC | AB
C -> aB | b


Diketahui CFG G = ({S,A,B},{a,b},P,S)
dimana P terdiri dari :
1. S -> bA
2. S -> aB
3. A -> bAA
4. A -> aS
5. A -> a
6. B -> aBB
7. B -> bS
8. B -> b
Diminta:
Buatlah bentuk Chomsky Normal Form dari CFG di atas.


Diketahui suatu Grammar G = ({A1, A2, A3}, {a, b}, P, A1)
dimana P terdiri dari :
1. A1 -> A2 A3
2. A2 -> A3 A1 | b
3. A3 -> A1 A2 | a
Diminta:
Buatlah bentuk Greibach Normal Form dari CFG di atas.


Diketahui suatu Push Down Automata (PDA) dengan Grammar
M = ({q1, q2}, {0, 1, c}, {M, B, H}, "symbol delta", q, M, "symbol himpunan kosong") dan mekanisme kerja digambarkan dalam tabel berikut :

Buatlah Langkah-langkah PDA diatas bila diberikan string input : 0011100