Název: Gramatiky a automaty Zkratka: GA Typ: povinný pro obor IT, povinně volitelný pro obor AŘ Rozsah: 14 týdnů, týdně 2 hodiny přednášek + 2 hodiny seminárních cvičení Kredity: 5 Způsob ukončení: zkouška Katedra: katedra softwarového inženýrství FM TUL Přednášející: Doc. Mgr. Ing. Václav Záda, CSc.
Stručná anotace předmětu:Předmět seznamuje studenty ze základy teorie automatů a formálních jazyků v míře potřebné k pochopení funkce a návrhu překladačů programovacích jazyků a operačních systémů. Předmět dále umožňuje pochopení moderních monografií a článků z teorie programování a je stavěn tak, aby vyhovoval i lidem, kteří nejsou školenými matematiky.
Témata přednášek:Konečné automaty a jejich reprezentace, jazyky rozpoznatelné konečnými automaty. Nerodova věta. Kritéria pro návrh konečných automatů.
Nedeterministické konečné automaty, uzávěrové vlastnosti. Regulární jazyky a výrazy. Regulární rovnice a jejich řešení. Mooreho věta. Dvousměrné konečné automaty.
Pojem gramatiky, Chomského hierarchie. Regulární gramatiky a jazyky, automaty s jedním zásobníkem a bezkontestové jazyky, Turingovy stroje a jazyky typu 0. Redukované gramatiky, kanonické derivace, derivační stromy.
Principy analýzy shora. Zásobníkové automaty a bezkontextové jazyky. Principy analýzy zdola. Chomského normální forma. Uzávěrové vlastnosti.
Kategoriální gramatiky, makrogramatiky, různé formy modifikovaných gramatik zejména programové, indexované a řetězcové gramatiky, stochastické gramatiky a fuzzy gramatiky, gramatiky s řízeným přepisováním, L-systémy a dále LL(0), LL(1) a LL(k) gramatiky, LR(0) a LR(k) gramatiky.
Mealyho a Mooreovy automaty. Analýza a syntéza sekvenčních automatů. Minimalizace sekvenčních automatů.
Náplň cvičení:Na cvičeních bude procvičována látka vyložená na předchozích přednáškách. Jde především o návrh konečných automatů na základě zadaného jazyka, převod regulárního jazyka na regulární výraz jednak pomocí soustavy regulárních rovnic nebo pomocí grafu, konstrukce konečného automatu z regulárního výrazu, ověřování ekvivalence automatů. Návrhy gramatik, syntaktická analýza shora a zdola. Využití gramatik v úlohách rozpoznávání. Návrh sekvenčních automatů. Průběžně budou poskytovány informace o zdrojích na internetu, které se vztahují k aktuálně probírané látce.
Literatura:Chytil, M.: Automaty a gramatiky. Praha, SNTL 1984.
Hopcroft, J.E.-Ullman,J.D.: Formálne jazyky a automaty. Bratislava, Alfa 1978. (překlad z angličtiny)
Manna, Z.: Matematická teorie programů. Praha, SNTL 1981.
Mareš, J.: Teoretická kybernetika. Praha, Vydavatelství ČVUT 1997.
Melichar, B.: Gramatiky a jazyky. Praha, Ediční středisko ČVUT 1982. (Bude inovováno.)
Molnár,L. a kol.: Gramatiky a jazyky. Bratislava, Alfa 1987.
Prerekvizity: -Navazující: -
Datum poslední změny: 21. 12. 2001