IB102 - úkol 9 - řešení                                       Odevzdání: 7.12. 2009
Vypracoval: James Bond                                UCO: 007
Skupina: MI6
1. [2 body] Nechť A = ({qQ, qu q2, q3, Qa, *>}, {a, b}, {Z, A}, ö, qQ, Z, {q5}) je zásobíhový automat, kde
S(q0,a,Z) = {(quAZ)} 5{q0,a,A) = {{qi,AA)} 5(qi,a,A) = {(q2,AA)} 5(q2,a,A) = {(q0,A),(q3,A)} ö(q3,b,A) = {(q4,e)} S(q3,b,Z) = {(q5,e)} 5(q4,b,A) = {(q3,A),(q3,e)} 5(q4,b,Z) = {(q5,e)}
Popište jazyk L (A), tedy jazyk akceptovaný automatem A koncovým stavem. Řešení: L(A) = {a^V \ i > 0 A2i < j < 4i}
Automat nejprve čte symboly a po trojicích, a přitom cyklicky mění svůj stav z q0 na q\, z q1 na q2 a z q2 zpátky na q0. Při čtení symbolů a přidává na zásobník symboly A, a to konkrétně tak, že na zásobník přidá jeden symbol A při čtení prvního a druhého symbolu a z každé trojice. Po přečtení 3i symbolů a je tedy na zásobníku li symbolů A.
Pokud chce automat akceptovat, musí někdy ze stavu q2 přejít do q3 místo qo. Po přechodu do stavu ^3 přečetl 3i symbolů a a na zásobníku je li symbolů A, kde i > 0, a nyní už může číst pouze symboly b. Automat při čtení symbolů b cyklicky mění svůj stav z q3 na q4 a z g4 zpátky na q3. Při přechodu ze stavu q3 vždy umaže jeden symbol A z vrcholu zásobníku a při přechodu ze stavu g4 se nedeterministicky rozhodne, zda symbol A umaže, nebo nechá zásobník beze změny. Toto pokračuje dokud jsou na zásobníku nějaké symboly A, v opačném případě přečte jeden symbol b a akceptuje.
Protože je pro akceptování nutné přečíst jeden symbol b i po vymazání všech symbolů A ze zásobníku, musí automat přečíst minimálně k + 1 symbolů b, aby mohl akceptovat, kde k je počet symbolů A na zásobníku. Naopak maximálně může přečíst 2k symbolů b, protože automat čte symboly b po dvojicích a při čtení prvního b z každé dvojice musí jedno A ze zásobníku vymazat, takže po přečtení 2k — 1 symbolů b už na zásobníku nemůže být žádné A a následující symbol b způsobí akceptování.
Automat A tedy akceptuje slova tvaru (rlb? kde i > 0 a li < j < 4i.
IB102 - úkol 9 - řešení                                       Odevzdání: 7.12. 2009
Vypracoval: James Bond                                UCO: 007
Skupina: MI6
2. [2 body] Mějme bezkontextovou gramatiku G = ({S, A, B}, {a, b, c}, P, S), kde
P = { S  —► aSa | AB \ aa, A -^bAb\ SS, B ->■ cBc\ AA }.
Zkonstruujte ekvivalentní gramatiku v Greibachove normální formě. Použijte algoritmus uvedený na přednášce. Popište svůj postup a uveďte hlavní mezivýsledky.
Řešení: Gramatika G je vlastní, takže přistoupíme rovnou k odstranění levé rekurze a vytvoříme gramatiku G2 = ({S, A, B, S'}, {a, b, c}, P2, S), kde
P2 = { S  -^ aSa I aa \ bAbB \ aSaS' \ aaS' \ bAbBS', S' -»• S BS' I SB, A -^bAb\ SS, B  ->■ cBc\ AA }.
Při odstraňování levé rekurze bylo zvoleno pořadí neterminálů B < A < S. Nyní již můžeme provést vlastní převod do Greibachove normální formy. Tím vytvoříme gramatiku G3 = {{S, A, B, S', a', b', c'}, {a, b, c}, P3, S), kde
aSa' I aa' \ b Ab'B \ aSa'S' \ aa'S' \ bAb'BS',
aSa'BS' \ aa'BS' \ bAb'BBS' \ aSa'S'BS' \ aa'S'BS' \ bAb'BS'BS' \
aSa'B I aa'B \ b Ab'B B \ aSa'S'B \ aa'S'B \ bAb'BS'B,
bAV I aSa'S \ aa'S \ bAb'BS \ aSa'S'S \ aa'S'S \ bAb'BS'S,
cBd I bAb'A I aSa'SA \ aa'S A \ bAb'BS A \ aSa'S'SA \ aa'S'S A \ bAb'BS'SA,
a,
b, c}.
ft
{S
S'
A B a' b'
Při převodu do GNF bylo zvoleno pořadí neterminálů S' < B < A < S.