Zjednotenie značíme u, prienik ^, doplnok ^C, a reverz ^R. Reverz jazyka L je definovaný nasledovne: L^R = { w^R | w patrí do L }

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. Rozhodnite, či je trieda regulárnych jazykov uzavretá na zreťazenie (t.j. či pre ľubovoľné regulárne gramatiky G₁ a G₂ existuje regulárna gramatika G taká, že L(G)=L(G₁) . L(G₂) ). Svoje tvrdenie dokážte.
2. Zostrojte deterministický konečný automat akceptujúci jazyk L = { u.ababba.v | u,v patria do {a,b}^*} (. je zreťazenie). Dokážte správnosť svojej konštrukcie.
3. Zostrojte deterministický konečný automat akceptujúci jazyk L = { w | #_aw mod 2 = #_b w mod 2 } a dokážte správnosť svojej konštrukcie.
4. Daná je regulárna gramatika G = (N, T, P, S). Zostrojte regulárnu gramatiku G' = ( N', T, P', S') takú, aby pre jazyk L(G') platilo L(G') = [L(G)]^R. Dokážte správnosť svojej konštrukcie. (Inými slovami, dokážte uzavretosť regulárnych jazykov na reverz.)
5. Daná je bezkontextová gramatika G = ( N, T, P, S ). Zostrojte bezkontextovú gramatiku G' = ( N', T, P', S') takú, aby pre jazyk L(G') platilo L(G') = [L(G)]^R. Dokážte správnosť svojej konštrukcie. (Inými slovami, dokážte uzavretosť bezkontextových jazykov na reverz.)
6. Majme kontextovú gramatiku G = ( N, T, P, S ) , kde
   N = { A, B, C, D },
   T = { a, b, c },
   P = {
   S -> abcD | epsilon
   D -> ABCD | epsilon
   cA -> Ac
   bA -> Ab
   aA -> aa
   cB -> Bc
   bB -> bb
   cC -> cc }.
   

   Definujme homomorfizmus h:(N u T)^* -> (N u T)^* nasledovne:
   h(x)=epsilon, ak x patrí do N
   h(x)=x, ak x patrí do T

   Dokážte (formálne!), že pre všetky vetné formy u gramatiky G platí nasledujúce tvrdenie:
   

   • #_au+#_Au = #_bu+#_Bu = #_cu+#_Cu
   • h(u) patrí do {aⁱb^jc^k | i,j,k>=0 }
7. Zostrojte deterministický konečný automat akceptujúci jazyk L = { u.abaabab | u patrí do {a,b}^* } (. je zreťazenie). Dokážte správnosť svojej konštrukcie.
8. Zostrojte deterministický konečný automat akceptujúci jazyk L = { w | w patrí do {a,b,c}^*, medzi posledným a v slove w a koncom slova w sa nachádzajú aspon 3 symboly c a medzi posledným b v slove w a koncom slova w sa nachádza aspoň 5 symbolov c }. Dokážte správnosť svojej konštrukcie.