Vyučující
|
-
Severýn Otto, doc. Ing. Ph.D.
|
Obsah předmětu
|
Přednášky: 1. Abeceda, slovo, jazyk, metody popisu jazyků. 2. Konečné deterministické automaty. 3. Konečné nedeterministické automaty. 4. Minimalizace automatů a vzájemné převody. 5. Regulární výrazy a jejich vztah ke konečným automatům. Regulární jazyky a jejich vlastnosti. 6. Gramatiky a přepisovací systémy, Chomského hierarchie. 7. Regulární a lineární gramatiky. 8. Bezkontextové gramatiky, derivační stromy. 9. Zásobníkové automaty. 10. Deterministické zásobníkové automaty, iterační lemma. 11. Kontextové gramatiky, věta o monotonii. 12. Turingův stroj, převod mezi gramatikou a strojem. 13. Algoritmicky nerozhodnutelné problémy. 14. Další vlastnosti gramatik - LL a LR gramatiky, atributové gramatiky. Cvičení: 1. Jazyk a metody jeho popisu. 2. Různé praktické konečné automaty. 3. Nedeterministické konečné automaty. 4. Regulární a bezkontextové gramatiky. 5. Zásobníkové automaty. 6. Turingův stroj. 7. Rozhodnutelné a nerozhodnutelné problémy. V režimu online probíhá výuka v Google Meet zde: https://meet.google.com/rqz-tayj-szw
|
Studijní aktivity a metody výuky
|
Monologický výklad (přednáška, prezentace, vysvětlování)
- Domácí příprava na výuku
- 21 hodin za semestr
- Příprava na zápočet
- 25 hodin za semestr
- Příprava na zkoušku
- 32 hodin za semestr
- Úč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. Úvod do teorie vyčíslitelnosti.
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
Podmínkou zápočtu je vypracování zadaných úloh a jedné komplexní úlohy, plus účast na cvičeních. Zkouška je ústní a zaměřená na probíranou teorii.
|
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.
-
Ivana Černá. Automaty a formální jazyky.
-
Molnár, Ľ., Češka, M., Melichar, B. Gramatiky a jazyky, Alfa SNTL 1987.
|