Předmět Formální jazyky a automaty (KMI / FJAI)
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 / FJAI - 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, 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.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ělen při dosažení potřebného skóre v testu.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.