|
Vyučující
|
-
Kolář Milan, doc. Ing. CSc.
|
|
Obsah předmětu
|
<u>Získané kompetence:</u> Student získá schopnosti v navrhování, zjednodušování a úpravách konečných automatů, včetně ověřování správnosti návrhu a to i ve velmi komplikovaných případech. Dále bude umět navrhnout a verifikovat nejrůznější typy gramatik, provádět syntaktickou analýzu a aplikovat naučené metody na konkrétní technické úlohy, od zpracování jazyka až po rozpoznávání obrazů. <u>Témata přednášek:</u> 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 bezkontextové 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ů. <u>Náplň cvičení:</u> Procvičována látka bude předem vyložená na 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, 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.
|
|
Studijní aktivity a metody výuky
|
Monologický výklad (přednáška, prezentace, vysvětlování)
- Účast na výuce
- 56 hodin za semestr
|
|
Výstupy z učení
|
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 teoretické i praktické informatiky a je stavěn tak, aby jej mohli absolvovat lidé, kteří nejsou školenými matematiky.
Student získá schopnosti v navrhování, zjednodušování a úpravách konečných automatů, včetně ověřování správnosti návrhu a to i ve velmi komplikovaných případech. Dále bude umět navrhnout a verifikovat nejrůznější typy gramatik, provádět syntaktickou analýzu.
|
|
Předpoklady
|
Podmínka registrace: není stanovena
|
|
Hodnoticí metody a kritéria
|
Kombinovaná zkouška
Regulární výrazy a rovnice, konečné automaty, Turingovy stroje, Postovy stroje, stroje se zásobníky, Chomského hierarchie, regulární gramatiky, modifikované a stochastické gramatiky, syntaktická analýza, LL a LR gramatiky. Základy kombinatoriky a teorie grafů.
|
|
Doporučená literatura
|
-
Ginzburg, A. Algebraic Theory of Automata. Academic Press, London, 1968.
-
Hopcroft, J.E. - Ullman, J.D. Formálne jazyky a automaty. Bratislava, Alfa 1978. (Překlad z angličtiny.).
-
Chytil, M. Automaty a gramatiky. Praha, SNTL 1984.
-
Mareš, J. Jazyky, gramatiky a automaty. Praha. Vydavatelství ČVUT, 2004.
-
Melichar, B. Jazyky a překlady. Praha. Vydavatelství ČVUT, 2003.
-
Pin, J.E. Mathematical Foundations of Automata Theory. 2014.
|