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.

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

Odovzdávacie úlohy je potrebné odovzdať do stredy 13.3.2002 8:00 do krabice pre sekretariátom KI!

1. Odovzdávacia. Dokážte, že trieda L_DLBA je uzavretá na komplement. (L_DLBA tvoria práve tie jazyky L, pre ktoré existuje deterministický lineárne ohraničený automat A taký, že L=L(A).)
2. Odovzdávacia. Daný je homomorfizmus h:Sigma₁^*->Sigma₂^*. Zostrojte Turingov stroj A_h taký, že keď dostane na začiatku na páske slovo w (nad abecedou Sigma₁), skončí v akceptačnom stave a na páske bude mať zapísané h(w), t.j. obraz vstupného slova daným homomorfizmom. Toto slovo musí byť na páske zapísané po písmenkách (na každom políčku je najviac jeden symbol (z abecedy Sigma₂), políčka s písmenami h(w) tvoria súvislý úsek).
3. Nech A₁, A₂ sú deterministické Turingove stroje. Zostrojte deterministický TS A tak, aby
   L(A)=L(A₁) U L(A₂)
4. Zadefinujte nedeterministický TS (štand. 4 definície) s k páskami. Každá páska má samostatnú hlavu. Vstupné slovo je napísané na prvej páske. Stav automatu je spoločný pre všetky hlavy. Poriadne dokážte, že takýto TS je ekvivalentný so štandardným NTS.
5. Dokážte pomocou deterministických TS, ktoré vždy zastavia, že trieda L_REC je uzavretá na kladnú iteráciu (+). Fungovalo by vaše riešenie aj pre L_RE? Ak nie, dá sa nejako upraviť, aby fungovalo? (Odpovede na otázky stačí neformálne zdôvodniť.)
6. Dokážte, že ku každej frázovej gramatike existuje ekvivalentná, ktorá obsahuje iba kontextové pravidlá (t.j. pravidlá, ktorých pravá strana je aspoň tak dlhá, ako ľavá) a navyše pravidlo Alfa->epsilon, kde Alfa je jeden konkrétny neterminál novej gramatiky.
7. Daný je deterministický LBA A. Zostrojte LBA A', ktorý dostane na vstupe slovo w#j, kde w je slovo nad abecedou LBA A a j je číslo zapísané v dvojkovej sústave. Pre takýto vstup má A' na niektorej stope pásky postupne generovať konfigurácie automatu A počas prvých j krokov.
8. Daný je LBA A. Zostrojte LBA A' taký, že
   L(A')={ u | existuje v také, že |u|=|v| a uv patrí do L(A) }