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 dokázať správnosť svojej konštrukcie. V zadaní úlohy, ktorú chcete odovzdať ako "veľkú" prezentáciu si slovo zdôvodnite nahraďte slovom dokážte.

Odovzdávacie úlohy je potrebné odovzdať do utorka 26.2.2002 23:59 do krabice pre sekretariátom KI!

1. Zostrojte LBA, ktorý bude akceptovať jazyk:
   L = { ww | w patrí do {a,b}⁺ }
   Zdôvodnite správnosť svojej konštrukcie.
2. Odovzdávacia. Zostrojte LBA, ktorý bude akceptovať jazyk:
   L = { a^{n^2} | n>0 }
   Zdôvodnite správnosť svojej konštrukcie.
3. Zostrojte LBA, ktorý bude akceptovať jazyk:
   L = { a^{2^n} | n>0 }
   Zdôvodnite správnosť svojej konštrukcie.
4. Zostrojte LBA, ktorý bude akceptovať jazyk:
   L = { a^mbⁿc^m.n | m,n>0 }
   Zdôvodnite správnosť svojej konštrukcie.
5. Dokážte, že trieda L_LBA je uzavretá na zreťazenie.
6. Odovzdávacia. Dokážte, že ak L patrí do L_LBA, tak aj L_a patrí do L_LBA, kde:
   L_a = { w | w patrí do {a,b}⁺, aw patrí do L }
   Zdôvodnite správnosť svojej konštrukcie.
7. Dokážte, že LBA, pre ktoré platí:
   pre všetky q_f z F, pre všetky a z Gama platí |delta(q_f,a)|=0
   sú normálnym tvarom lineárne ohraničených automatov.
8. Zostrojte LBA, ktorý keď dostane na začiatku na páske slovo uvw, kde u,w patria do {a,b}⁺ a v patrí do c⁺, prepíše toto slovo na slovo uwv a akceptuje. (Nie je dôležité, ako sa tento LBA bude správať na iných slovách.)
9. Urobte detailne tú časť konštrukcie LBA k danej gramatike, v ktorej sa simuluje spätná aplikácia pravidla pri práci s vetnou formou s "dierami" (t.j. za predpokladu, že nerobíme "upratovanie" pásky.)