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 regulární jazyky.
Gramatiky, Chomského hierarchie, regulární, bezkontextové a obecné gramatiky
Bezkontextové gramatiky, derivace, normální tvary, pumping (iterační) lemma pro bezkontextové jazyky, zásobníkové automaty.
Rekurzivně spočetné jazyky, Turingovy stroje, algoritmicky nerozhodnutelné problémy, univerzální jazyk, diagonální jazyk.
Polynomiální složitost, NP-úplnost, Cook-Levinova věta.
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).