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 28. 10. 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.

Úloha #5

Je daný nedeterministický konečný automat A=(K,Sigma,delta,q₁,F) nasledovne: K={q₁, q₂, q₃, q₄, q₅, q₆, q₇}
Sigma={a,b}
F={q₅}
delta(q₁,epsilon)={q₂}
delta(q₁,a)={q₃}
delta(q₁,b)={}
delta(q₂,epsilon)={q₅, q₆}
delta(q₂,a)={q₃, q₄}
delta(q₂,b)={}
delta(q₃,epsilon)={q₄}
delta(q₃,a)={}
delta(q₃,b)={q₂}
delta(q₄,epsilon)={q₇}
delta(q₄,a)={q₅}
delta(q₄,b)={q₆}
delta(q₅,epsilon)={}
delta(q₅,a)={}
delta(q₅,b)={q₃}
delta(q₆,epsilon)={}
delta(q₆,a)={q₇}
delta(q₆,b)={}
delta(q₇,epsilon)={q₅}
delta(q₇,a)={}
delta(q₇,b)={}

Štandardnou konštrukciou k nemu zostrojte ekvivalentný nedeterministický konečný automat bez prechodov na epsilon.

Úloha #6