Předmět: Automaty a formální jazyky

» Seznam fakult » FP » NTI
Název předmětu Automaty a formální jazyky
Kód předmětu NTI/AFJ-P
Organizační forma výuky Přednáška + Cvičení
Úroveň předmětu Bakalářský
Rok studia nespecifikován
Semestr Letní
Počet ECTS kreditů 4
Vyučovací jazyk Čeština
Statut předmětu Povinný
Způsob výuky Kontaktní
Studijní praxe Nejedná se o pracovní stáž
Doporučené volitelné součásti programu Není
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.


Studijní plány, ve kterých se předmět nachází
Fakulta Studijní plán (Verze) Kategorie studijního oboru/specializace Doporučený ročník Doporučený semestr