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. Nerovnosť značíme !=.

1. Je daná bezkontextová gramatika G=({A,B,C,D,S},{a,b},P,S), kde P je:
   S -> AB | BASa
   A -> aDA | DaDa | BbB
   B -> BACa | SA | aBBa | ab
   C -> ab | AaB | DASA | D
   D -> aAaB | SADa
   

   Zostrojte PDA A taký, že N(A)=L(G).

2. Daná je časť delta funkcie zásobníkového automatu A=( {q,q1,q2}, {a,b}, {A,B,C,Z}, d, q, Z, {q2} ). Podľa konštrukcie z prednášky k nej zostrojte príslušnú časť ekvivalentnej bezkontextovej gramatiky.

   d(q,a,A)=(q1,B)      d(q1,a,C)=(q2,BBC)   d(q1,b,B)=(q1,epsilon)
   d(q,a,B)=(q1,BA)     d(q,a,Z)=(q1,ZB)     d(q,b,A)=(q2,epsilon)
   

   ---

   V nasledujúcich úlohách zadefinujte modifikáciu zásobníkového automatu (štandardné 4 definície). Porovnajte triedu jazykov akceptovaných modifikovaným PDA s triedou bezkontextových jazykov. Dokážte vaše tvrdenie.

3. Zásobníkový automat s pružnou hlavou v zásobníku. Automat s pružnou hlavou v zásobníku môže na jeden krok výpočtu prečítať viacero symbolov zo zásobníka.
4. Automat, ktorého zásobníková abeceda obsahuje nanajvýš 2 rôzne symboly. (|Gamma|<=2)
5. Automat, ktorý môže na jeden krok výpočtu zvýšiť výšku zásobníka najviac o jeden symbol.
   (delta: K x (Sigma u {epsilon}) -> 2^K x (Gamma⁰ u Gamma¹ u Gamma²))

   ---

6. K-ohraničený PDA je taký PDA, pre ktorý existuje celé číslo k také, že A používa pri ľubovoľnom akceptačnom výpočte zásobník výšky najviac k. Porovnajte triedu jazykov akceptovaných k-ohraničenými automatmi s triedou regulárnych a bezkontextových jazykov.
7. Zostrojte PDA A taký, že:
   L(A)={aⁱb^jc^k | i,j,k>=0, neplatí, že i=j=k}
8. Zostrojte PDA A taký, že:
   L(A)={wa^2k+1b^3k+2w^R | w patrí do {a,b}^*, k>=0}
9. Zostrojte PDA A taký, že:
   L(A)={w | w patrí do { (,),[,] }^* a zároveň w je postupnosťou zátvoriek nejakého dobre uzátvorkovaného výrazu}
10. Dané sú PDA A₁, A₂. Zostrojte PDA A taký, že:
    L(A)=L(A₁) L(A₂)
    Detailne dokážte správnosť vašej konštrukcie.