Zkouška 17.6. 2009

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
beny
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 31. 1. 2008 12:51
Typ studia: Informatika Bc.

Zkouška 17.6. 2009

Příspěvek od beny »

Ahoj!
Kdyz dnes pred zkouskou docent Bartak rikal, at davame pozor na detaily, rikal jsem si, ze uz snad v testu nic neprehlednu, ale mylil jsem se :) Clovek to fakt musi cist do mrte. Malou ukazkou me nepozornosti budiz kvizova otazka:
Jazyk L+ je roven:
a)neco spatne
b)neco spatne
c)neco spatne
d) sjednoceni Li od 0 dale.
Ted to mozna nevypada jako neco, co by clovek opravdu znaly prehledl, ale ten index a cislo pod sjednotitkem je tak mrnavy :) Navic se tahle otazka lisila od jedne uz zname jen tou nulou misto jednicky...

Jako priklad jsem dostal napsat gramatiku pro jazyk L = {aibjck | i<=j<=k}, tedy vcelku lehky priklad. Pak jsem mel urcit, do jake nejmensi skupiny jazyku patri a dokazat to (pumping lemma pro BKJ). Gramatika byla kontextova. Dale jsem mel definovat monotonni a kontextovou gramatiku a dokazat tvrzeni, ze k libovolne monotonni se da najit ekvivalentni kontextova gramatika. Nakonec se me jeste zeptal na zneni pumping lemmatu pro BKJ.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“