Tieto úlohy má každý z vás vyriešiť a riešenie odovzdať v písomnej forme do krabice pred sekretariátom KI (pavilón M, 2. poschodie) DO PONDELKA 2. 12. 2002 8:05. Každá z nich bude hodnotená 3 bodmi. Riešenie každej úlohy píšte na samostatný papier!
Opravenú úlohu č. 10. môžete odovzdať DO PIATKU 6. 12. 2002 13:00.
Zjednotenie značíme u, prienik ^, doplnok C.
Je daný zásobníkový automat A, ktorý akceptuje prázdnou pamäťou. Zostrojte k nemu Turingov stroj M, taký, že L(M)=L(A).
Vaša konštrukcia má byť všeobecná, t.j. má fungovať pre ľubovoľný PDA A. Zdôvodnite správnosť svojej konštrukcie.
Definujme jazyk L nasledovne:
L={anba2n | n>=1}
Zostrojte TS A, pre ktorý bude platiť L(A)=L. Zdôvodnite jeho správnosť.