Vo všetkých úlohách predpokladajte (pokiaľ nie je uvedené ináč), že L, L₁, L₂ atď. sú ľubovoľné jazyky a h je ľubovoľný homomorfizmus. Zjednotenie značíme u, prienik ^, doplnok ^C, a reverz ^R. Počiatočný symbol gramatiky označujeme S. Ak nie je povedané ináč, malé písmená označujú terminály, veľké písmená neterminály. Používame skrátenú formu zápisu pravidiel, t. j. S->A | bb sú dve pravidlá: S->A a S->bb.

1. Nech L je jazyk všetkých slov nad abecedou {a,b}, ktoré neobsahujú slovo abaabb ako svoje podslovo.
   • a) Zostrojte nedeterministický konečný automat A taký, že L(A) = L.
   • b) Zostrojte deterministický konečný automat A taký, že L(A) = L.
2. Zostrojte (deterministický alebo nedeterministický) konečný automat pre jazyk
   L = {w | w patrí do {a,b}^*, #_a(w) mod 2=1, #_b(w) mod 3=2}
3. Je daný nedeterministický automat A = (K,Sigma,delta,q₁,F) nasledovne:
   K = {q₁, q₂, q₃, q₄}
   Sigma = {a,b}
   F = {q₂, q₃}
   delta(q₁, a)={q₂}
   delta(q₁, b)={q₃}
   delta(q₂, a)={q₁,q₄}
   delta(q₂, b)={}
   delta(q₃, a)={}
   delta(q₃, b)={q₃,q₄}
   delta(q₄, a)={}
   delta(q₄, b)={q₁}
   

   Zostrojte k nemu štandardnou konštrukciou ekvivalentný deterministický konečný automat.

4. Konečný automat s pružnou hlavou šírky k je modifikáciou nedeterministického konečného automatu. V jednom kroku výpočtu dokáže prečítať viacero (najviac k) symbolov vstupného slova (na "šípke" teda môže byť zapísané slovo dĺžky najviac k).

   Formálne definujte automat s pružnou hlavou šírky k (uveďte štandardné 4 definície). Dokážte jeho ekvivalenciu s konečnými automatmi (t.j. že pre každý automat s pružnou hlavou existuje (nedeterministický) konečný automat akceptujúci ten istý jazyk a naopak.)

5. Je daný nedeterministický konečný automat A = (K,Sigma,delta,q₀,F). Popíšte všeobecnú konštrukciu nedeterministického automatu s jediným akceptačným stavom A'=(K',Sigma,delta',q'₀,F' = {q'_f}) takého, že L(A) = L(A'). Dokážte správnosť svojej konštrukcie.
6. Zostrojte (deterministický alebo nedeterministický) konečný automat akceptujúci jazyk
   L = {w| w patrí do {a,b}^*, #_a(w) mod 2=1, w obsahuje podslovo ababbab}
7. Je daný nedeterministický automat A = (K,Sigma,delta,q₀,F). Popíšte všeobecnú konštrukciu (deterministického alebo nedeterministického) automatu A' takého, že L(A') = [L(A)]^R. Dokážte správnosť svojej konštrukcie.