Vo všetkých úlohách predpokladajte (pokiaľ nie je uvedené ináč), že L, L1, L2 atď. sú ľubovoľné jazyky a h je ľubovoľný homomorfizmus. Zjednotenie značíme u, prienik ^, doplnok C, a reverz R. Nerovnosť značíme !=. L_PDA značí triedu jazykov akceptovaných zásobníkovými automatmi.

1. Dokážte (pomocou PDA), že L_PDA je uzavretá na reverz.
2. Sú dané dva zasobníkové automaty A₁, A₂ akceptujúce prázdnou pamäťou. Zostrojte zasobníkový automat A (akceptujúci prázdnou pamäťou alebo akceptačným stavom) taký, že L(A) = { w | w=uvz, uz je z N(A₁) , v je z N(A₂) } a dokážte správnosť svojej konštrukcie.
3. Dokážte, že ku každému zásobníkovému automatu A existuje zásobníkový automat A', ktorý nemá prechody na epsilon (t.j. v každom kroku číta 1 písmeno vstupu) a platí L(A) = L(A').
4. Rozhodnite, či je jazyk L = { ww | w je z {a,b}* } bezkontextový. Ak áno, zostrojte zásobníkový automat akceptujúci L, ak nie dokážte.
5. Rozhodnite, či je jazyk L = { aⁱb^jcⁱd^j | i,j>0 } bezkontextový. Ak áno, zostrojte zásobníkový automat akceptujúci L, ak nie dokážte.
6. Dokážte, že jazyk L = {aⁿbⁿcⁿd²| n>=0 } u {aⁿbⁿcⁱd^j | n>=0, i,j>=3} nie je bezkontextový.
7. Nájdite taký jazyk L, ktorý nie je bezkontextový, ale dá sa pumpovať podľa pumpovacej lemy pre bezkontextové jazyky.
8. Nech A je zasobníkový automat. Zostrojte zasobníkový automat A' taký, že L'(A)= L(A) ^ { w | w je zo Sigma* , |w| = 2k, k>=0 }. Dokážte správnosť svojej konštrukcie.
9. Nech A je zasobníkový automat. Zostrojte zasobníkový automat A' taký, že L'(A)= L(A) ^ { uabbav | u,v je zo Sigma* }. Dokážte správnosť svojej konštrukcie.