Předmět Automaty a formální jazyky (NTI / AFJ)
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 - Automaty a formální jazyky, Fakulta mechatroniky a MIS, Technická univerzita v Liberci (TUL).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
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.
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á