Sylabus
Konečné automaty a regulární jazyky, Nerodova věta, ekvivalence a redukce automatů, nedeterminismus.
Uzávěrové vlastnosti, regulární výrazy, Kleeneova věta, pumping (iterační) lemma pro regurální jazyky.
Gramatiky, Chomského hierarchie, regulární, bezkontextové a kontextové gramatiky
Bezkontextové gramatiky, derivace, redukce, normální tvary, pumping (iterační) lemma pro bezkontextové jazyky, uzávěrové vlastnosti, deterministické a nedeterministické zásobníkové automaty.
Rekurzivně spočetné jazyky, Turingovy stroje, algoritmicky nerozhodnutelné problémy, univerzální jazyk, diagonální jazyk.
Anotace
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).