Předmět Formální jazyky a automaty (KMI / FJAA)
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 KMI / FJAA - Formální jazyky a automaty, Přírodovědecká fakulta, Univerzita Palackého v Olomouci (UP).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
Základní pojmy: formální jazyky, hierarchie gramatik a jazyků.Konečné automaty: konečné deterministické a nedeterministické automaty, jejich rozšíření, varianty a aplikace.Regulární gramatiky a jazyky: vztah ke konečným automatům, uzávěrové vlastnosti regulárních jazyků, kritéria regularity, minimalizace konečných automatů.Regulární výrazy a jejich aplikace: standardní regulární výrazy, rozšířené regulární výrazy, aplikace pro vyhledávání v textu, vybrané problémy.Bezkontextové jazyky: popis a vlastnosti, derivační stromy, vlastnosti bezkontextových jazyků a vztah k regulárním jazykům.Zásobníkové automaty: varianty, vztah k bezkontextovým jazykům, syntaktická analýza shora-dolů a zdola-nahoru, deterministické zásobníkové automaty.
Získané způsobilosti
1. ZnalostPopiš základní generativní a analytické formalismy pro jazyky.
Literatura
Kozen, D. C. Automata and Computability. Springer, New York, 1997. ISBN 0387949070.Kozen D. C. Automata and Computability. Springer, 1997. ISBN 0-387-94907-0.LAWSON M. V. Finite Automata. Chapman & Hall/CRC, 2003. ISBN 978-1584882558.Hopcroft J. E., Motwani R., Ullman J. D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston, 2006. ISBN 978-0321462251.Sipser M. Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA, 1997. ISBN 0-534-94728-X.Sipser, M. Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA, 1997. ISBN 0-534-94728-X.Melichar, B. Jazyky a překlady. Skriptum, přepracované 2. vydání. Vydavatelství ČVUT, Praha, 2003. ISBN 80-01-02776-7.Simovici D. A., Tenney R. L. Theory of Formal Languages with ApplicationsM. Simon. World Scientific, Singapore, 1999.
Požadavky
Zápočet je udělován na základě písemných testů probíhajících na cvičení.Zkouška je udělována na základě písemného a ústního zkoušení.
Garant
doc. RNDr. Vilém Vychodil, Ph.D.
Vyučující
doc. RNDr. Vilém Vychodil, Ph.D.Mgr. Tomáš Kühr, Ph.D.