Course: Automata Theory

« Back
Course title Automata Theory
Course code KIN/TEA
Organizational form of instruction Lecture + Lesson
Level of course Master
Year of study 1
Semester Summer
Number of ECTS credits 4
Language of instruction Czech
Status of course Compulsory
Form of instruction unspecified
Work placements unspecified
Recommended optional programme components None
Lecturer(s)
  • Beránek Ladislav, doc. Ing. CSc.
Course content
1. Word algebra over a given alphabet. 2. Deterministic finite automaton. 3. Moore a Mealy automata. 4. Nondeterministic finite automaton. 5. Deterministic finite automaton with epsilon-transitions. 6. Automata constructions. 7. Pumping lemma. 8. Regular expressions - the theory. 9. Regular expressions - the practice. 10. Automata and grammars. 11. Push-down automaton. 12. Parsing trees. 13. Turing machine.

Learning activities and teaching methods
Dialogic (discussion, interview, brainstorming)
Learning outcomes
It is an introductory course of the theory of finite automata and formal languages with the emphasis on the algebraic theory of finite automata. The basic concepts, relations, and constructions of the theory are performed.
Student is able to explain how the different models of finite automata work and understands basic logical relations in the theory. He/she performs some examples of a deterministic, a nondeterministic, a push-down automaton, and a Turing machine and gives an analysis of their behavior.
Prerequisites
KIN/DIM1

Assessment methods and criteria
Student performance assessment

Active attendance at seminars (100 %). Elaboration of all short-dated homework (from week to week) Passing the credited test - minimum 55% of the points.
Recommended literature
  • Demlová, M., Koubek, V. Algebraická teorie automatů.. Praha: SNTL, 1990.
  • Černá, O., Křetínský, M., Kučera, A. Automaty a formální jazyky I. [online]. [cit. 1. 4. 2008].
  • Hopcroft, J. F. et all. Introduction to Automata Theory, Languages, and Computations, 2nd ed.. New York: Addison-Wesley, 2001.


Study plans that include the course
Faculty Study plan (Version) Category of Branch/Specialization Recommended year of study Recommended semester
Faculty: Faculty of Education Study plan (Version): Teacher training in information technology (2) Category: Pedagogy, teacher training and social care 1 Recommended year of study:1, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Teacher training in information technology (2) Category: Pedagogy, teacher training and social care 1 Recommended year of study:1, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): information technology and e-learning (2) Category: Pedagogy, teacher training and social care - Recommended year of study:-, Recommended semester: Summer