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. Dokážte, že ku každej regulárnej gramatike G existuje ekvivalentná regulána gramatika G' taká, že P_G' je podmnožinou ( N x ( TN u T u N u { epsilon } ). (Slovo ekvivalentná znamená, že L(G)=L(G').)
2. Majme bezkontextovú gramatiku G a vetné formy u, v také, že u =>^* v (t.j. v G sa dá z u na niekoľko krokov odvodiť v). Nech A je ľubovoľný neterminál vetnej formy u. Dokážte, že potom v G existuje odvodenie vetnej formy v z u také, že v prvom kroku sa prepíše práve neterminál A. (Uvedomte si, že toto tvrdenie vlastne hovorí, že nezáleží na poradí, v akom pri odvodení v bezkontextovej gramatike prepisujeme neterminály.)
3. Popíšte jazyk, generovaný gramatikou s pravidlami: S -> aSS | b.
4. Zostrojte bezkontextovú gramatiku, generujúcu jazyk: L = { w | w patrí do {a,b}^* a #_a(w) = #_b(w) }. Dokážte správnosť svojej konštrukcie.
5. Zostrojte bezkontextovú gramatiku, generujúcu jazyk: L = { aⁱ b^2i+j c w w^R c^j-2 | w patrí do {a,b}^* a i>=0, j>=2 }. Dokážte správnosť svojej konštrukcie.
6. Zostrojte bezkontextovú gramatiku, generujúcu jazyk: L = { uvwxy | existujú i,j také, že uy = aⁱbⁱ, vx = (vx)^R a w = a^jb^j }. Dokážte správnosť svojej konštrukcie.
7. Použitím štandardnej konštrukcie (z prednášky) upravte nasledovnú gramatiku na ekvivalentnú, ktorá nebude obsahovať zbytočné neterminály, t.j. každý neterminál bude dosiahnuteľný a z každého neterminálu sa bude dať odvodiť terminálne slovo.
   G = ( N, T, P, S )
   N = { S, A, B, C, D, E, F }, T = { a, b }
   P = {
     S -> aA | ASA | bb
     A -> AC | AAC | SFC
     B -> Da
     C -> ab | CaC
     D -> BB | Sa
     E -> ab | EC
     F -> aAbF | AA | F
   }
8. Nech f(G) je gramatika, ktorú dostaneme z G odstránením nedosiahnuteľných neterminálov, nech g(G) je gramatika, ktorú dostaneme z G odstránením terminálov, z ktorých sa nedá odvodiť terminálne slovo. Nájdite čo najjednoduchšiu (čo najmenej pravidiel) bezkontextovú gramatiku G takú, aby f(g(G))!=g(f(G)). Aký je vzťah medzi gramatikami f(g(G)) a g(f(G))? (Musí niektorá z nich byť "podmnožinou" druhej? Prečo?)