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. Pomocou štandardnej konštrukcie (z prednášky) zostrojte k danej bezkontextovej gramatike G ekvivalentnú bezkontextovú gramatiku G', ktorá nebude obsahovať tzv. "chain rules", t.j. pravidlá tvaru X -> Y, kde X,Y sú neterminály.
   G = ( N, T, P, S )
   N = { S, A, B, C, D }, T = { a, b }
   P = {
     S -> b | bS | A
     A -> bCa | A | BB | C
     B -> C | abSa | bB | A | D
     C -> epsilon | A | B
     D -> aaC | bA
   }
2. Pomocou štandardnej konštrukcie (z prednášky) zostrojte k danej bezkontextovej gramatike G ekvivalentnú bezkontextovú gramatiku G', ktorá bude v Chomského normálnom tvare, t.j. jej pravidlá budú podmnožinou N x ( NN u T u { epsilon } ). G = ( N, T, P, S )
   N = { S, A, B, C, D }, T = { a, b }
   P = {
     S -> b | bS | SABC
     A -> bCa | BB | C
     B -> C | abSa | bB | AD
     C -> epsilon | A | B
     D -> aaC | bA | bb
   }
3. Upravte konštrukciu Chomského normálneho tvaru z prednášky tak, aby vo výslednej gramatike neboli ani pravidlá tvaru X -> epsilon, kde X je neterminál iný ako S. Dokážte správnosť vašej konštrukcie.
4. Zostrojte frázovú gramatiku, ktorá bude generovať jazyk L = { a^{2^n} | n>=1 }. Stačí neformálne popísať, ako by sa dala dokázať jej správnosť. (Dala by sa pre jazyk L zostrojiť kontextová gramatika? Ako / Prečo?)
5. Nech G₁ = (N₁,T₁,P₁,S₁), G₂ = (N₂,T₂,P₂,S₂) sú dané bezkontextové gramatiky. Zostrojte bezkontextovú gramatiku pre jazyk: ( L(G₁) . L(G₂) )^*. Formálne dokážte správnosť svojej konštrukcie. Vaša konštrukcia by mala byť všeobecná, t.j. mala by fungovať pre ľubovoľné dve bezkontextové gramatiky.
6. Nech G je ľubovoľná bezkontextová gramatika a w nech je slovo z L(G). Aké najkratšie a aké najdlhšie (čo do počtu krokov) mohlo byť odvodenie slova w? Aký hlboký mohol byť strom odvodenia? Ako sa tieto hodnoty zmenia, ak je G v Chomského normálnom tvare?
7. Ak to ide, zostrojte bezkontextovú gramatiku pre jazyk L = { w | w patrí do {a,b}^* a #_a(w) sa nerovná #_b(w) }. Ak nie, pokúste sa zdôvodniť, prečo tento jazyk nie je bezkontextový.
8. (pre samovrahov) Dané je prirodzené číslo k. Rozhodnite, či je jazyk L = { w | w patrí do {a,b}^* a #_a(w) = k.#_b(w) } bezkontextový.