Teoretická informatika 1

1. Úvod, organizace předmětu, význam a aplikace teorie formalních jazyků, příklady jazyků a jejich specifikace.
2. Formální jazyky, pojmy abeceda, řetězec, zřetězení, operace nad jazyky, algebra jazyků jako polookruh.
3. Reprezentace jazyků, problém reprezentace, způsoby reprezentace formálních jazyků.
4. Gramatiky, definice gramatiky, relace derivace, větná forma a jazyk generovaný gramatikou, Chomského klasifikace gramatik a formálních jazyků, ilustrační příklady.
5. Jazyky přijímané konečnými automaty, definice konečného nedeterministického automatu, konfigurace automatu, relace přechodu, jazyk přijímaný konečným automatem, vztah deterministických a nedeterministických konečných automatů, vztah jazyků typu 3 a jazyků přijímaných konečnými automaty, ilustrační příklady.
6. Regulární množiny a regulární výrazy, definice, algebra regulárních výrazů (identity), rovnice nad regulárními výrazy, vztah regulárních množin a jazyků typu 3, ilustrační příklady. Rozšířený konečný automat, převod regulárního výrazu na ekvivalentní deterministický konečný automat, ilustrační příklady.
7. Minimalizace konečného automatu, relace nerozlišitelnosti stavů, konstrukce redukovaného konečného automatu ilustrační příklady.
8. Vlastnosti regulárních jazyků, strukturální vlastnosti, Pumping theorem pro regulární jazyky, uzávěrové vlastnosti, rozhodnutelné problémy regulárních jazyků, ilustrační příklady a příklady k samostatnému řešení.
9. Bezkontextové gramatiky, definice, levá a pravá derivace, víceznačnost gramatik, rekurze, problém syntaktické analýzy, klasifikace syntaktických analyzátorů, ilustrační příklady a příklady k samostatnému řešení.
10. Transformace bezkontextových gramatik, ekvivalence bezkontextových gramatik, odstranění zbytečných symbolů, odstranění e-pravidel, odstranění jednoduchých pravidel, převod na vlastní gramatiku, odstranění levé rekurze, ilustrační příklady.
11. Zásobníkové automaty, definice, varianty, ekvivalence jazyků typu 2 a jazyků přijímaných zásobníkovými automaty, deterministické zásobníkové automaty a deterministické bezkontextové jazyky, ilustrační příklady.
12. Vlastnosti bezkontextových jazyků, normální tvary bezkontextových gramatik, Greibachové a Chomského normální forma, pumping theorem pro bezkontextové jazyky, uzávěrové vlastnosti bezkontextových jazyků, rozhodnutelné a nerozhodnutelné problémy bezkontextových jazyků, ilustrační příklady.
13. Petriho sítě, definice, stavový prostor a přechodová funkce Petriho sítě, lineární algebraická reprezenatce Petriho sítě, ilustrační příklady.

1. Operace nad jazyky, gramatiky, jejich klasifikace.
2. Vzájemné převody mezi gramatikami typu 3, konečnými automaty a regulárními výrazy.
3. Minimalizace konečných automatů, vlastnosti regulárních jazyků.
4. Konstrukce bezkontextových gramatik, derivační stromy.
5. Transformace bezkontextových gramatik.
6. Konstrukce zásobníkových automatů, vlastnosti bezkontextových jazyků.

1. Petri net tool PESIM.

1. Aho A.V.,Ullmann J.D.: The Theory of Parsing, Translation and Compiling, Prentice-Hall, 1972
2. Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 1991.
3. Češka M.: Petriho sítě, Akad.nakl. CERM, Brno 1994

1. Melichar B. a kol.: Gramatiky a jazyky SNTL, 1987
2. Češka M.,Rábová Z. Gramatiky a jazyky Nakl. VUT Brno, 1992
3. Češka M.a kol.: Vyčíslitelnost a složitost, Nakl. VUT Brno, 1993
4. Češka M.: Petriho sítě, Akad.nakl. CERM, 1994