Sylabus

Automaty a gramatiky

 

Úvod | Sylabus | Zdroje | Přednáška | Cvičení | Zkoušky

 

Označení: TIN013
Rozsah: 2/2 Z, Zk - letní semestr
Vyučující: Roman Barták

Konečné automaty, definice, způsoby zadání, jazyky rozpoznávané automaty, kongruence, Nerodova věta, ekvivalence, redukce a normalizace, nedeterminismus a podmožinová konstrukce.

Uzávěrové vlastnosti, regulární výrazy, Kleeneova věta, dvoucestné automaty, pumping (iterační) lemma.

Gramatiky, Chomského hierarchie, nevypouštějící gramatiky, regulární gramatiky a ekvivalence s KA, lineární gramatiky.

Bezkontextové gramatiky, derivace, derivační stromy, jednoznačnost/víceznačnost, redukce, zásobníkové automaty (přijímání koncovým stavem a prázdným zásobníkem), deterministické a bezprefixové jazyky, ekvivalence s bezkontextovými gramatikami, Chomského a Greibachové normální tvary, pumping (iterační) lemma, uzávěrové vlastnosti.

Kontextové gramatiky, separované a monotónní gramatiky.

Rekurzivně spočetné jazyky, Turingovy stroje, lineárně omezené automaty, algoritmicky nerozhodnutelné problémy

© 2001 Roman Barták

Automaty a gramatiky