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)
- Preparation for classes
- 60 hours per semester
- Preparation for credit
- 20 hours per semester
- Semestral paper
- 20 hours per semester
- Class attendance
- 48 hours per semester
|
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
|
-
DEMLOVÁ, M. a V. KOUBEK. Algebraická teorie automatů. Praha, 1990.
-
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.
-
CHYTIL,M. Automaty a gramatiky. Praha, 1984.
-
MAREŠ, Martin a Tomáš VALLA. Průvodce labyrintem algoritmů. Praha: CZ.NIC, z.s.p.o., 2017. ISBN 978-80-88168-19-5.
-
Nýdl a kol. Jazyky a automaty. 2016.
|