Course: Languages and Automata

« Back
Course title Languages and Automata
Course code KMI/YLA
Organizational form of instruction Lecture + Lesson
Level of course Master
Year of study not specified
Semester Summer
Number of ECTS credits 6
Language of instruction English
Status of course unspecified
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
Course availability The course is available to visiting students
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.


Study plans that include the course
Faculty Study plan (Version) Category of Branch/Specialization Recommended year of study Recommended semester