X je dopredu dany neterminal.
Uloha 3
Nech G je kontextova (CS) gramatika. Slovo w je
odvodene lavym krajnym odvodenim v G, ak sa v kazdom kroku odvodenia
pouzije pravidlo, ktore prepise najlavejsi neterminal vetnej formy.
(Ak sa najlavejsi neterminal neda prepisat podla ziadneho pravidla, dane
odvodenie sa "zasekne".) Jazyk generovany lavymi krajnymi odvodeniami
gramatiky G je mnozina slov, pre ktore existuje lave krajne odvodenie
v gramatike G.
Zaradte triedu jazykov generovanych lavymi krajnymi odvodeniami kontextovych
gramatik do Chomskeho hierarchie (t.j. porovnajte ju s triedou CS, CF,
pripadne R jazykov).
Uloha 4
Zostrojte TS, ktory akceptuje jazyk L.
L = { w | w je nad {0,1,#} je platnym kodom det. Turingovho stroja}
Pouzite kodovanie TS z prednasky. Nemusite pisat delta fciu, staci dostatocne
podrobny popis (na takej urovni, aby bolo jasne, kolko stavov dany stroj
ma a na co sluzia)
Uloha 5
Zostrojte deterministicky TS, ktory pocita funkciu horna cela cast
z log2 n.
Vstup aj vystup je kodovany v unarnej sustave, t.j. kod cisla n je slovo
pozostavajuce z (n+1) znakov 1.
To, ze stroj pocita danu funkciu znamena, ze ak ma na zaciatku vypoctu
na paske vstupnu hodnotu, po konecnom case skonci v akceptacnom stave, pricom
na paske bude zapisana vystupna hodnota (falosne blanky na oboch koncoch
pasky sa ignoruju).
Uloha 6
Zostrojte TS, ktory utriedi zoznam cisel. Cisla su kodovane v unarnej
sustave (vid. predch. uloha), kazde dve naslednujuce cisla su oddelene
znakom #, zaciatok a koniec zoznamu je oznaceny ##.
Uloha 7
Dany je TS A a slovo w. Zostrojte TS A', ktory akceptuje
prazdne slovo prave vtedy, ked A akceptuje w. Uvedte vseobecny
postup (algoritmus, ktory by bolo mozne implementovat na beznom pocitaci),
nezavisly na konkretnych vlastnostiach stroja A.
Uloha 8
Dany je (nedeterministicky) TS A. Zostrojte ekvivalentny TS, ktoreho
kazdy vypocet je bud akceptujuci alebo nekonecny.