Stvrta sada domacich uloh

Spolupraca pri rieseni odovzdavacich domacich uloh

O rieseni odovzdavacich domacich ulohach samozrejme mozete diskutovat so spoluziakmi (napr. cestou na obed), avsak len v hrubych rysoch na urovni idei. Napisat riesenie ulohy vsak musi kazdy sam, bez akejkolvek cudzej pomoci alebo spoluprace a specialne bez toho, aby videl riesenie kohokolvek ineho.

Vo vasom rieseni uvedte mena vsetkych ludi, s ktorymi ste sa bavili o rieseniach odovzdavanych uloh.

Ulohy 2 a 7 su urcene na odovzdavanie a nie je mozne ich prezentovat. Odovzdavajte ich do stredy 8. 3. rana (t.j. 8:10) do skatule na chodbe pred sekretariatom katedry informatiky.

Uloha 1

V dokaze ekvivalencie kontextovych gramatik a linearne ohranicenych automatov z prednasky doplnte do gramatiky simulujucej LBA pravidla pre manipulaciu s prvym a poslednym patposchodovym symbolom.
V ulohach 2 - 4 zadefinujte prislusny modifikovany Turingov stroj a dokazte jeho ekvivalenciu s Turingovym strojom z prednasky.

Uloha 2

(*odovzdavacia uloha)
Turingov stroj s jednosmerne nekonecnou paskou. (Paska ma na lavej strane symbol cent, ktory nie je mozne prekrocit.) K standardnemu Turingovmu stroju s obojsmernou paskou zostrojte ekvivalentny TS s jednosmernou paskou, vratane detailnej delta funkcie a dokazte, ze tieto dva stroje akceptuju rovnaky jazyk.

Uloha 3

Turingov stroj s viacerymi pracovnymi paskami. Vstupne slovo je na zaciatku vypoctu napisane na prvej paske.

Uloha 4

Turingov stroj s viacerymi hlavami na jednej pracovnej paske.

Uloha 5

Dokazte, ze trieda kontextovych jazykov je uzavreta na inverzny homomorfizmus.

Uloha 6

Nech L je kontextovy jazyk a h je nevymazavajuci homomorfizmus. Dokazte, ze aj h(L) je kontextovy jazyk. Nevymazavajuci homomorfizmus je taky, ze h(w)=epsilon len ak w=epsilon.
Otazka nad ramec: je predpoklad, ze h je nevymazavajuci, potrebny?

Uloha 7

(*odovzdavacia uloha)
Zostrojte linearne ohraniceny automat (vratane delta funkcie) akceptujuci jazyk 
 L = { u#v | (u)2 = (v)3 > 0 }
t.j. u a v su zapisy rovnakeho kladneho celeho cisla, pricom u je jeho zapis v dvojkovej a v v trojkovej sustave.
L je nad abecedou {0,1,2,#}.

Poznamka: Vasou ulohou je nielen automat zostrojit, ale aj presvedcit citatela o tom, ze naozaj funguje. V tejto cinnosti vydatne pomaha popis jednotlivych casti delta funkcie, pripadne popis obsahu pasky v jednotlivych fazach vypoctu. Riesenia, ktore nebude opravujuci schopny pochopit do 10 minut sa vystavuju riziku velmi nizkeho bodoveho hodnotenia.

Uloha 8

Dokazte, ze gramatika s pravidlami tvaru 
 uAv -> uxv
kde u,x,v su slova zlozene z terminalov a neterminalov, A je neterminal a |x| >= 1, je normalnym tvarom kontextovej gramatiky.