Pokiaľ nie je povedané ináč, všetky jazyky, gramatiky a automaty v zadaniach sú všeobecné (t.j. môžu byť ľubovoľné). Pokiaľ bola odprednášaná štandardná konštrukcia, používajte ju! V opačnom prípade musíte zdôvodniť správnosť svojej konštrukcie. V zadaní úlohy, ktorú chcete odovzdať ako "veľkú" prezentáciu si prípadné slovo zdôvodnite nahraďte slovom dokážte.

Odovzdávacie úlohy je potrebné odovzdať do piatku 3.5.2002 12:00 do krabice pre sekretariátom KI!

Znakom C označujeme cent a znakom S dolár.

1. Odovzdávacia úloha: Definujte a-prekladač so zásobníkovou pamäťou (vrátane definície zobrazenia jazyka takýmto prekladačom). Je trieda bezkontextových jazykov uzavretá na takéto zobrazenie?
2. Odovzdávacia úloha: Dokážte, že jazyk
   L={wcw   |   w patrí do {a,b}^*}
   patrí do DTIME(2n).
3. Dokážte, že pre každú inštanciu Postovho Korešpondenčného Problému <X,Y> sú jazyky L_X a L_XY deterministické bezkontextové jazyky.
4. Predveďte konštrukciu pre zrýchľovanie TS na prípade m=2, teda zostrojte TS, ktorý bude spôsobom z prednášky pracovať na páske obsahujúcej dva symboly pôvodného stroja v jednom políčku. Súčasťou vytváraného TS má byť aj kompresia pásky na začiatku výpočtu.
5. Nech G je bezkontextová gramatika v Chomského normálnom tvare s k pravidlami očíslovanými 1,2,...,k. Nech
   L={wu   |   w patrí do L(G) a u je postupnosť čísel pravidiel použitých v ľavom krajnom odvodení w v G}
   Dokážte, že L patrí do DSPACE(n^2).
6. Nech G je bezkontextová gramatika v Chomského normálnom tvare s k pravidlami očíslovanými 1,2,...,k. Nech
   L={wu   |   w patrí do L(G) a u je postupnosť čísel pravidiel použitých v ľavom krajnom odvodení w v G}
   Dokážte, že L patrí do DTIME(n^3).
7. Nech G je bezkontextová gramatika v Greibachovej normálnom tvare s k pravidlami očíslovanými 1,2,...,k. Nech
   L={wu   |   w patrí do L(G) a u je postupnosť čísel pravidiel použitých v ľavom krajnom odvodení w v G}
   Dokážte, že L patrí do NTIME(c*n) pre vhodnú konštantu c.
8. Nájdite algoritmus, ktorý pre danú bezkontextovú gramatiku G a symboly a,b zistí, či existuje vetná forma tvaru uabvx v nejakom pravom krajom odvodení, kde bv je "handle" (t.j. najľavejší výskyt pravej strany pravidla).