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 11. 11. 2002 8:05. Každá z nich bude hodnotená 3 bodmi. Riešenie každej úlohy píšte na samostatný papier!
Zjednotenie značíme u, prienik ^, doplnok C.
Je daný zásobníkový automat A, ktorý akceptuje prázdnou pamäťou. Zostrojte k nemu zásobníkový automat A', ktorý bude akceptovať akceptačným stavom a pre ktorý bude platiť N(A)=L(A').
Vaša konštrukcia má byť všeobecná, t.j. má fungovať pre ľubovoľný PDA A. Súčasťou riešenia má byť aj formálny dôkaz správnosti konštrukcie.
Definujme jazyk L nasledovne:
L={w | w patrí do {a,b}*, #a(w)=2#b(w)}
Zostrojte PDA A (akceptujúci akc. stavom),
pre ktorý bude platiť L(A)=L. Formálne dokážte jeho správnosť.