|
Lecturer(s)
|
-
Severýn Otto, doc. Ing. Ph.D.
|
|
Course content
|
Lecture: 1. Alphabet, word, language, finite state machine. 2. Reachability and equivalency of states, reduction of finite state machines. 3. Nondeterministic finite state machine. 4. Closure features of the class of regular languages. 5. Regular languages and their relationship to finite state machines. 6. Grammars and rewriting systems, Chomsky hierarchy. 7. Regular and linear grammars. 8. Context-free grammars, derivation trees. 9. Pushdown automata. 10. Deterministic pushdown automata, iteration lemma. 11. Context-sensitive grammars, monotony theorem. 12. Turing machine, conversion between grammar and machine. 13. Decidable problems. 14. Other grammar features - LL and LR grammars, attribute grammars. Practice: 1. Finite state machines. 2. Reduction and equivalency of finite state machines. 3. Nondeterministic finite state machines. 4. Regular and context-free grammars. 5. Pushdown automata. 6. Turing machine. 7. Computable and non-computable function.
|
|
Learning activities and teaching methods
|
Monological explanation (lecture, presentation,briefing)
- Home preparation for classes
- 21 hours per semester
- Preparation for credit
- 25 hours per semester
- Preparation for exam
- 32 hours per semester
- Class attendance
- 42 hours per semester
|
|
Learning outcomes
|
Finite state machines (deterministic and nondeterministic) and recognised languages. Nerode theorem, software implementation of FSM, FSM reduction, lexical analysis. Regular expressions, regular languages. Pushdown automaton. Grammars, Chomsky hierarchy, context-free languages, grammar reduction, Pumping lemma. Turing machine. Introduction to computability theory.
The students learn basic models of computational processes and generation or accepting of formal languages.
|
|
Prerequisites
|
Unspecified
|
|
Assessment methods and criteria
|
Combined examination
Requirements for getting a credit is sucessful filling of all the given tasks and one complex task, also the presence at practical lessons is mandatory. Examination is of the oral form with focus to the theoretical sessions.
|
|
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.
-
Ivana Černá. Automaty a formální jazyky.
-
Molnár, Ľ., Češka, M., Melichar, B. Gramatiky a jazyky, Alfa SNTL 1987.
|