Sylabus přednášky

• Motivace - problém specifikace (nekonečných, regulárních) jazyků; základní operace nad jazyky.
• Konečné automaty a regulární gramatiky; Pumping lemma, Nerodova věta, minimalizace. Nedeterministické konečné automaty, vztah k regulárním gramatikám.
• Vlastnosti regulárních jazyků; uzávěrové vlastnosti, regulární výrazy, Kleeneho věta, konečnost.
• Bezkontextové gramatiky a jazyky; transformace bezkontextových gramatik, vybrané normální formy, pumping lemma, uzávěrové vlastnosti.
• Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám; nedeterministická syntaktická analýza shora dolů a zdola nahoru.
• Deterministické zásobníkové automaty a deterministická analýza.