| 11. 5. 2012 | Ako už bolo avizované, termín veľkej písomky je v pondelok 21.5. o 10:00
v miestnosti F109. Podobne ako v zimnom semestri, veľká písomka trvá 120 minút.
Bude na nej mierna podmnožina náplne všetkých prednášok a cvičení. Presnejšie,
naučte sa nasledovné tematické okruhy:
- Myhill-Nerodeova veta a jej použitie
- Uzavretosť bezkontextových jazykov na homomorfizmus a inverzný homomorfizmus
- A-prekladače, ich konštrukcia, vlastnosti a normálne tvary
- Operácia substitúcie a pravého/ľavého kvocientu
- Trieda kontextových jazykov, jej uzáverové vlastnosti, Szelepczényiho veta
- Lineárne ohraničené automaty a ich ekvivalencia z kontextovými gramatikami
- PKP, jeho variácie a nerozhodnuteľnosť
- (Ne)rozhodnuteľnosť základných otázok o rôznych triedach jazykov
- Riceove vety a ich použitie
- Jednoduché prekladové schémy
- Shift-reduce algoritmus, LR-elementy a iné základné definície
- LR(0) gramatiky, konštrukcia položkového automatu a deterministické shift-reduce parsovanie
- Algoritmus CYK
- Deterministické zásobníkové automaty, rozdiel medzi akceptáciou prázdnou pamäťou a stavom
- Uzáverové vlastnosti deterministických bezkontextových jazykov
- Ogdenova lema
- Časová a pásková konštruovateľnosť funkcií
- Zložitosť konečných automatov. Model automatu s dvojsmerným pohybom hlavy (netreba rotujúci
ani sweeping), vzťahy zložitosti k jednosmerným modelom.
|
|---|