Předmět Gramatiky a automaty (MTI / GRA)

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 MTI / GRA - Gramatiky a automaty, Fakulta mechatroniky a MIS, Technická univerzita v Liberci (TUL).

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

Obsah

Přednášky:1. Přehled základních pojmů. Množiny, logika, relace, uspořádání, ekvivalence na množině, neorientované a orientované grafy.2. Slova a jazyky, monoidy. Definice konečného automatu. Jazyky rozpoznatelné automaty, pravá kongruence, příklady.3. Reprezentace konečných automatů, Nerodova věta, její důkaz. Jazyky nerozpoznatelné konečnými automaty.4. Regulární výrazy, regulární a množiny. Uspořádání a rovnost regulárních výrazů, základní operace.5. Základní algebraické vzorce, jejich odvození a užití.6. Regulární rovnice, jejich sestavování a způsoby řešení.7. Nedeterministické konečné automaty, věta o ekvivalenci nedeterministických a deterministických konečných automatů.8. Zobecněné nedeterministické konečné automaty, věta o ekvivalenci. Algoritmus konstrukce deterministického automatu.9. Uzávěrové vlastnosti automatů. Uzavřenost na sjednocení, průnik, doplněk, součin, iteraci, reverzi.10. Ekvivalence automatů, konstrukce automatů z regulárních výrazů. Uzavřenost na levý a pravý kvocient jazyka.11. Formální jazyky, přepisovací systémy, gramatiky, Chomskeho hierarchie jazyků a gramatik. Ilustrační příklady.12. Regulární jazyky a gramatiky, ekvivalence automatů a reg. gramatik.13. Bezkontextové jazyky a zásobníkové automaty, základy syntaktické analýzy. Principy analýzy shora, příklady.14. Principy analýzy zdola. Modifikované gramatiky: Programované gramatiky, stochastické gramatiky a fuzzy gramatiky.Cvičení:1. Opakování logiky, teorie množin, binární relace. Rozklad množiny na třídy ekvivalence.2. Návrhy jednoduchých deterministický konečných automatů (KA). Rozklad množiny všech slov na třídy ekvivalence.3. Nerodova věta a její aplikace. Jazyky nerozpoznatelné automaty.4. Reprezentace automatů a jejich převod do soustavy rovnic.5. Navrhování automat a řešení soustav regulárních rovnic.6. Konstrukce složitějších konečných automatů.7. Nedeterministické konstrukce automatů a jejich regulární rovnice.8. Zobecněné automaty, převod na deterministické automaty.9. Uzávěrové vlastnosti, jejich využití v konstrukci složitých automatů.10. Užití ekvivalence automatů, konstrukce KA z regulárních výrazů.11. Zápisy jazyků pomocí gramatik.12. Regulární gramatiky, jejich tvorba přes konečné automaty.13. Bezkontextové jazyky, analýza shora. Příklady.14. Analýza zdola. Příklady. Zápočet.

Získané způsobilosti

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.

Literatura

Ginzburg, A. Algebraic Theory of Automata. Academic Press, London, 1968. 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.). Melichar, B. Jazyky a překlady. Praha. Vydavatelství ČVUT, 2003. Mareš, J. Jazyky, gramatiky a automaty. Praha. Vydavatelství ČVUT, 2004. Pin, J.E. Mathematical Foundations of Automata Theory. 2014.

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

doc. Mgr. Ing. Václav Záda, CSc.

Vyučující

doc. Mgr. Ing. Václav Záda, CSc.doc. Ing. Otto Severýn, Ph.D.doc. Mgr. Ing. Václav Záda, CSc.