|
Lecturer(s)
|
-
Barilla Jiří, doc. Ing. Mgr. CSc.
-
Škvor Jiří, RNDr. Ph.D.
|
|
Course content
|
1. Finite Automata (KA): representations, languages recognizable by finite automata 2. Reduction and implementation of finite automata 3. Non-deterministic finite automata 4. Grammars: Chomsky's distribution of grammars, regular grammars 5. Regular languages: closure properties, relation to KA 6. Applications of regular languages and automata: regular expressions and their types 7. Context-free grammars 8. Pushdown automata 9. Applications of context-free languages and stack automata: LR/LL syntactic parser, ANTLR 10. Turing machines: models and their properties 11. Undecidability: Church-Turing thesis, the Post correspondence problem 12. Equivalent representations of Turing machines: RASP 13. Practical applications
|
|
Learning activities and teaching methods
|
|
unspecified
|
|
Learning outcomes
|
In this course, students will learn the theoretical foundations of finite automata, grammars and pushdown automata. Emphasis is placed on bridging mathematical theory with its practical implementation and on applying this theory to contemporary technologies.
|
|
Prerequisites
|
unspecified
|
|
Assessment methods and criteria
|
unspecified
|
|
Recommended literature
|
-
Hopocroft J., Ulman J. Formálne jazyky a automaty. ALFA Bratislava, 1978.
-
Hopocroft J., Ulman J. Introduction to Automata Theory, Languages and Computation. Addison Wesley, 1979.
-
Chytil M. Automaty a gramatiky. SNTL, Praha, 1984.
-
Chytil M. Teorie automatů a formálních jazyků. (Skripta), SPN Praha, 1978.
-
Kolář J., Štěpánková O., Chytil M. Logika, algebry a grafy. SNTL Praha, 1989.
-
Meduna A. Automata and Languages. Springer, 2000.
|