Lecturer(s)
|
-
Klán Petr, doc. Mgr. Ing. CSc.
|
Course content
|
The Lectures: 1. Word algebra over an alphabet, a language, language operations. 2. Deterministic finite automaton., Moore and Mealy automaton. 3. Nondeterministic finite automaton. 4. Automata constructions. 5. Regular languages, regular expressions. 6. Automata and grammars. 7. Pushdown automaton.. 8. Context-free grammars. 9. The construction of parse trees. 10. Applications of context-free grammars. 11. Context-sensitive grammars. 12. Turing machines. 13. Summary - Chomski hierarchy of formal languages.
|
Learning activities and teaching methods
|
Monologic (reading, lecture, briefing), Dialogic (discussion, interview, brainstorming)
|
Learning outcomes
|
The course is an introduction of the theory of finite automata and formal languages. Algebraic approach to the theory is emphasized.
The student actively understands and utilises the basic concepts and constructions of the finite automata theory and shows a good orientation in Chomski hierarchy of formal languages. He/she communicates in English.
|
Prerequisites
|
Basic concepts of discrete mathematics.
|
Assessment methods and criteria
|
Student performance assessment, Combined exam
The student works weekly in the Moodle LMS system, he/she hands in 12 HWs.. The final credit test requires at least 55% points for correct answers.
|
Recommended literature
|
-
HOPCROFT, J. F. et al. Introduction to Automata Theory, Languages and Computations. New York, 2001.
-
CHAKRABORTY, S. Formal Languages and Automata Theory - Regular Expressions and Finite Automata. Zurich, 2003.
-
Nýdl et al. Languages and Automata. 2016.
|