Automaty a gramatiky

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).