|
Vyučující
|
-
Severýn Otto, doc. Ing. Ph.D.
|
|
Obsah předmětu
|
Konečné automaty deterministické a nedeterministické a jazyky jimi rozpoznatelné, Nerodova věta, programová realizace automatů, redukce konečného automatu, lexikální analýza. Regulární výrazy, regulární jazyky. Zásobníkové automaty. Gramatiky, Chomského hierarchie, Bezkontextové jazyky, redukce gramatiky, Pumping Lemma. Turingův stroj. Algoritmicky nerozhodnutelné problémy.
|
|
Studijní aktivity a metody výuky
|
Monologický výklad (přednáška, prezentace, vysvětlování)
- Účast na výuce
- 42 hodin za semestr
|
|
Výstupy z učení
|
Konečné automaty deterministické a nedeterministické a jazyky jimi rozpoznatelné, Nerodova věta, programová realizace automatů, redukce konečného automatu, lexikální analýza. Regulární výrazy, regulární jazyky. Zásobníkové automaty. Gramatiky, Chomského hierarchie, Bezkontextové jazyky, redukce gramatiky, Pumping Lemma. Turingův stroj. Algoritmicky nerozhodnutelné problémy.
Studenti se seznámí se základními modely výpočetních procesů a generování či rozpoznávání formálních jazyků.
|
|
Předpoklady
|
Nespecifikováno
|
|
Hodnoticí metody a kritéria
|
Kombinovaná zkouška
|
|
Doporučená literatura
|
-
Hopcroft, J. E., Ullman, J. D. Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979.
-
Chytil, M. Automaty a gramatiky.. SNTL Praha, 1984.
-
Jiří Vaníček. Teoretické základy informatiky. Praha, 2007. ISBN 9788090396241.
|