Předmět Automaty a gramatiky (NTIN071)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NTIN071 - Automaty a gramatiky, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Naučit základy teorie automatů a gramatik, zejména o regulárních a bezkontextových jazycích
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. Gramatiky, Chomského hierarchie, regulární, bezkontextové a kontextové gramatiky Bezkontextové gramatiky, derivace, redukce, normální tvary, pumping (iterační) lemma, uzávěrové vlastnosti, deterministické a nedeterministické zásobníkové automaty. Rekurzivně spočetné jazyky, Turingovy stroje, algoritmicky nerozhodnutelné problémy
Literatura
M. Chytil: Automaty a gramatiky, SNTL Praha, 1984 V. Koubek: Automaty a gramatiky, elektronický text (http://kti.mff.cuni.cz/downloads/Automstr_ps.zip), 1996 M. Chytil: Teorie automatů a formálních jazyků, skripta MFF UK, 1978 M. Chytil: Sbírka řešených příkladů z teorie automatů a formálních jazyků, skripta MFF UK, 1987 M. Demlová, V. Koubek: Algebraická teorie automatů, SNTL Praha, 1990 J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979
Garant
prof. RNDr. Roman Barták, Ph.D.RNDr. Pavel Surynek, Ph.D.