Předmět Vybrané kapitoly z teorie automatů (IA006)

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 IA006 - Vybrané kapitoly z teorie automatů, Fakulta informatiky, Masarykova univerzita (MU).

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

Cíl

Cílem je seznámit studenty s pokročilejšími partiemi teorie automatů, ato jak aplikacemi klasické teorie automatů a gramatik (metodysyntaktické analýzy deterministických bezkontextových jazyků), problematikoupoužití automatů pro specifikaci procesů(bisimulační ekvivalence, vztah automatů a MSO logiky), tak i s automaty nad nekonečnými slovy a jejichpoužitím.Na konci tohoto kurzu bude student schopen předkládat odůvodněná rozhodnutí o modelech relevatních pro danou oblast a porozumět metodám a technikám jejich použití.

Osnova

Deterministické bezkontextové jazyky (DCFL) a jejich syntaktickáanalýza.LL(k) gramatiky a jazyky; vlastnosti a analyzátory.LR(k) gramatiky a jazyky; vlastnosti a analyzátory.Vztahy mezi LL, LR a DCFL.(Ne)rozhodnutelné problémy z oblasti DCFL.Nekonečně stavové přechodové systémy a nedeterminismus - mopdelováníé procesů, bisimulace, vybranérozhodnutelné problémy se vztahem k verifikaci procesů.Konečné automaty a MSO logika (monadická logika 2. řádu)Automaty nad nekonečnými slovy: nekonečná slova,regulární (racionální) množiny nekonečných slov.Automaty: deterministické a nedeterministické Buchiho automaty, MullerovyRabinovy a Streetovy automaty. McNaughtonova věta. Vzájemné vztahy.

Literatura

CHYTIL, Michal. Automaty a gramatiky. 1. vyd. Praha: SNTL - Nakladatelství technické literatury, 1984. 331 s. infoKOZEN, Dexter C. Automata and computability. New York: Springer, 1997. xiii, 400. ISBN 0-387-94907-0. infoHandbook of formal languages. Vol. 1, Word, language, grammar. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997. xvii, 873. ISBN 3-540-60620-0-. infoHandbook of formal languages. Vol. 3, Beyond words. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997. xiv, 625 s. ISBN 3-540-60649-1-. infoSIPPU, Seppo a Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990. 417 s. ISBN 0-387-51732-4. infodalší odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Požadavky

Znalost problematiky v rozsahu předmětuIB005 - Formální jazyky a automaty aIB107 - Vyčíslitelnost a složitost

Garant

prof. RNDr. Mojmír Křetínský, CSc.

Vyučující

prof. RNDr. Mojmír Křetínský, CSc.doc. RNDr. Jiří Barnat, Ph.D.doc. RNDr. Jan Strejček, Ph.D.RNDr. Vojtěch Řehák, Ph.D.Mgr. Ľuboš KorenčiakRNDr. František BlahoudekMgr. Bc. Tomáš JaníkMgr. Karolína Malá