IB 102 - úkol 9
Odevzdání: 7.12. 2009
Vy pracoval (a):                                                   UČO:
Skupina:
1. [2 body] Nechť A = ({qQ, qu q2, q3, &, *>}, {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.
IB 102 - úkol 9
Odevzdání: 7.12. 2009
Vy pracoval (a):                                                   UČO:
Skupina:
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.