Předmět: Gramatiky a automaty

« Zpět
Název předmětu Gramatiky a automaty
Kód předmětu MTI/GRA
Organizační forma výuky Přednáška + Cvičení
Úroveň předmětu Magisterský
Rok studia nespecifikován
Semestr Zimní
Počet ECTS kreditů 5
Vyučovací jazyk Čeština
Statut předmětu Povinný, Povinně-volitelný
Způsob výuky Kontaktní
Studijní praxe Nejedná se o pracovní stáž
Doporučené volitelné součásti programu Není
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.


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
Fakulta: Fakulta mechatroniky, informatiky a mezioborových studií Studijní plán (Verze): Automatické řízení a inženýrská informatika (2016) Kategorie: Speciální a interdisciplinární obory 2 Doporučený ročník:2, Doporučený semestr: Zimní
Fakulta: Fakulta mechatroniky, informatiky a mezioborových studií Studijní plán (Verze): Informační technologie (2013) Kategorie: Informatické obory 1 Doporučený ročník:1, Doporučený semestr: Zimní