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. Nerovnosť značíme !=.

1. Definujme jazyk L nasledovne:
   L={a^p | p je prvočíslo}
   Zostrojte frázovú gramatiku G takú, že L(G)=L. Neformálne zdôvodnite jej správnosť.
2. Definujme jazyk L nasledovne:
   L={a^z | z je zložené číslo}
   Zostrojte frázovú gramatiku G takú, že L(G)=L. Formálne dokážte jej správnosť.
3. Definujme jazyk L nasledovne:
   L={w | w patrí do {a,b}^* a zároveň neplatí že #_a(w)=#_b(w)}
   Zostrojte zásobníkový automat A taký, že L(A)=L. Formálne dokážte jeho správnosť.
4. Definujme jazyk L nasledovne:
   L={w | w patrí do {a,b}^*, w=w^R}
   Zostrojte zásobníkový automat A taký, že L(A)=L. Formálne dokážte jeho správnosť.
5. Definujme jazyk L nasledovne:
   L={w | w patrí do {a,b}^*, w!=w^R}
   Zostrojte zásobníkový automat A taký, že L(A)=L. Formálne dokážte jeho správnosť.
6. Daný je zásobníkový automat A, ktorý akceptuje akceptačným stavom. Daný je konečný automat A_K. Zostrojte zásobníkový automat A', pre ktorý platí:
   L(A')=L(A) ^ L(A_K)
   

   Vaša konštrukcia má byť všeobecná, t.j. má fungovať pre ľubovoľné automaty A a A_K. Súčasťou riešenia má byť formálny dôkaz správnosti vašej konštrukcie.

7. Dané sú zásobníkové automaty A₁, A₂, ktoré akceptujú akceptačným stavom. Zostrojte zásobníkový automat A', pre ktorý platí:
   L(A')=L(A₁) u L(A₂)
   

   Vaša konštrukcia má byť všeobecná, t.j. má fungovať pre ľubovoľné automaty A₁ a A₂. Súčasťou riešenia má byť formálny dôkaz správnosti vašej konštrukcie.

8. Daný je zásobníkový automat A, ktorý akceptuje akceptačným stavom. Daný je homomorfizmus h. Zostrojte zásobníkový automat A', pre ktorý platí:
   L(A')=h(L(A))
   

   Vaša konštrukcia má byť všeobecná, t.j. má fungovať pre ľubovoľný automat A a ľubovoľný homomorfizmus h. Súčasťou riešenia má byť formálny dôkaz správnosti vašej konštrukcie.

9. Daný je zásobníkový automat A, ktorý akceptuje akceptačným stavom. Daný je homomorfizmus h. Zostrojte zásobníkový automat A', pre ktorý platí:
   L(A')=h^-1(L(A))
   

   Vaša konštrukcia má byť všeobecná, t.j. má fungovať pre ľubovoľný automat A a ľubovoľný homomorfizmus h. Súčasťou riešenia má byť formálny dôkaz správnosti vašej konštrukcie.

10. Definujme jazyk L nasledovne:
    L={w | w patrí do {a,b}^*, #_a(w)=#_b(w)}
    Dokážte, že jazyk L nie je regulárny. (Hint: použite pumpovaciu lemu.)
11. Definujme jazyk L nasledovne:
    L={a²ⁿ | n>=0, n je celé číslo}
    Dokážte, že jazyk L nie je regulárny. (Hint: použite pumpovaciu lemu.)