|
Lecturer(s)
|
-
Severýn Otto, doc. Ing. Ph.D.
|
|
Course content
|
Finite automata, deteministic and non-deterministic FA, languages accepted by FA, Nerode theorem, Realisation of automata by a program, Minimizing of FA, principles of scanning. Regular expressions, regular languages. Pushdown automata. Grammars. The Chomsky hierarchy, Context-free languages, CFG Minimizing, CFL Pumping Theorem. Turing machine. Undecidable problems.
|
|
Learning activities and teaching methods
|
Monological explanation (lecture, presentation,briefing)
- Class attendance
- 42 hours per semester
|
|
Learning outcomes
|
Finite automata, deteministic and non-deterministic FA, languages accepted by FA, Nerode theorem, Realisation of automata by a program, Minimizing of FA, principles of scanning. Regular expressions, regular languages. Pushdown automata. Grammars. The Chomsky hierarchy, Context-free languages, CFG Minimizing, CFL Pumping Theorem. Turing machine. Undecidable problems.
The students learn basic models of computational processes and generation or accepting of formal languages.
|
|
Prerequisites
|
Unspecified
|
|
Assessment methods and criteria
|
Combined examination
|
|
Recommended literature
|
-
Hopcroft, J. E., Ullman, J. D. Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979.
-
Chytil, M. Automaty a gramatiky.. SNTL Praha, 1984.
-
Jiří Vaníček. Teoretické základy informatiky. Praha, 2007. ISBN 9788090396241.
|