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. Nájdite jazyk L taký, aby L² mal presne 99 slov a L mal najmenší možný počet slov.
2. Nech L = { a } je jazyk nad abecedou Sigma = { a }, nech h je homomorfizmus zo Sigma^* do Sigma^* taký, že h(a)=epsilon. Zistite, koľko slov majú nasledovné jazyky:
   
   • L₁ = ( h^-1( h(L) ) )^*
   • L₂ = L² . ( h(L) )^*
   • L₃ = L . h^-1(L)
3. Zistite a dokážte, aký jazyk generuje nasledujúca gramatika:
   G = ( N, T, P, S )
   N = { S }, T = { a, b }
   P = { S -> aS | Sb | bSa | epsilon }
4. Zistite a dokážte, aký jazyk generuje nasledujúca gramatika:
   G = ( N, T, P, S )
   N = { S, A, B, C, D, E }, T = { a, b, c }
   P = {
     S -> AC | CC | CSD | bb
     A -> BcA | DD | aBD | AC
     B -> D | DDD | AB | aB
     C -> bb | SC | ABCD
     D -> AC | CA | Ac | cA
     E -> ab | EC
   }
5. Zostrojte bezkontextovú gramatiku, generujúcu jazyk:
   L = { w | w patrí do {a,b}^* a w = w^R }
   Dokážte správnosť svojej konštrukcie (t.j. že gramatika generuje všetky slová tohoto jazyka a žiadne iné).
6. Pomocou konečného počtu homomorfizmu jazykov, inverzného homomorfizmu jazykov, zreťazenia, zjednotenia a prieniku zostrojte z jazyka L₁ = { w | w patrí do {a,b}^* a #_a(w) = #_b(w) } jazyk L₂ = { aⁱ bⁱ | i >= 0 }
7. Zostrojte frázovú gramatiku, generujúcu jazyk:
   L = { w#w | w patrí do {a,b}^* }
   Správnosť konštrukcie nemusíte dokazovať, stačí neformálne zdôvodniť, ako vaša gramatika vygeneruje všetky slová jazyka a prečo nevygeneruje žiadne iné.
8. (pre fajnšmekrov) Nech x, y sú ľubovoľné slová. Dokážte, že xy = yx práve vtedy, keď existuje také slovo z, že x = zⁱ a y = z^j (pre vhodné i, j).