Předmět Automaty a formální jazyky (NTI / AFJ-P)

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 NTI / AFJ-P - Automaty a formální jazyky, Fakulta mechatroniky a MIS, Technická univerzita v Liberci (TUL).

Materiál	Typ	Datum	Počet stažení

Obsah

Přednášky:1. Abeceda, slovo, jazyk, konečný automat.2. Dosažitelnost a ekvivalence stavů, redukce konečného automatu.3. Nedeterministické konečné automaty.4. Uzávěrové vlastnosti třídy regulárních jazyků.5. Regulární výrazy a jejich vztah ke konečným automatům.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. Konečné automaty.2. Redukce a ekvivalence konečných automatů.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.----Rozsah přímé výuky pro kombinované studium:přednášky: 8 hodin/semestrcvičení: 4 hodiny/semestrkonzultace: 3 hodiny/semestr

Získané způsobilosti

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ů.

Literatura

Chytil, M. Automaty a gramatiky. SNTL Praha, 1984. Molnár, Ľ., Češka, M., Melichar, B. Gramatiky a jazyky, Alfa SNTL 1987. Hopcroft, J. E., Ullman, J. D. Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979.

Požadavky

Podmínkou zápočtu je aktivní účast na cvičeních, úspěšné absolvování testů. Zkouška je písemná a ústní.

Garant

Ing. Lenka Kosková - Třísková

Vyučující

Ing. Lenka Kosková - TřískováIng. Lenka Kosková - Třísková