Cíle výuky
Přecházíme ke složitějším teoretickým modelům struktur a postupů, tedy zásobníkovým automatům, Turingovým strojům a složitějším formám gramatik.
Obsahová náplň cvičení vychází a časově sleduje obsahovou náplň přednášky.
Tento předmět je zaměřen na teoretickou informatiku, ale vždy mějte na paměti, že vše, co probíráme, má také využití v praxi (zejména při programování). Ve výuce jsou studenti u konkrétních témat upozorňováni na jejich praktické využití, také se s tématy mohou setkat v jiných předmětech. Například v předmětu Programování stavíme na strukturách konečných a zásobníkových automatů a regulárních a bezkontextových gramatik, upravujeme je a učíme se využívat je při zpracování strukturovaného textu typu zdrojového kódu programovacího jazyka, HTML (apod.) kódu webové stránky ve webovém prohlížeči, atd.
Osnova
- Opakování – konečné automaty a regulární gramatiky. Kritéria regulárnosti jazyka.
- Transformace bezkontextových gramatik. Kritéria bezkontextovosti.
- Zásobníkové automaty, varianty, typy akceptování.
- Uzávěrové vlastnosti bezkontextových jazyků.
- Deterministické bezkontextové jazyky.
- Gramatiky typu 0, Turingovy stroje.
- Gramatiky typu 1, Lineárně ohraničené automaty.
- Gramatiky a gramatické systémy neodpovídající Chomského hierarchii.