Course: Formal Languages and Automata

« Back
Course title Formal Languages and Automata
Course code KMI/FJAA
Organizational form of instruction Lecture + Exercise
Level of course Bachelor
Year of study not specified
Semester Summer
Number of ECTS credits 6
Language of instruction Czech
Status of course Compulsory
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
Lecturer(s)
  • Kühr Tomáš, Mgr. Ph.D.
  • Vychodil Vilém, doc. RNDr. Ph.D.
Course content
Basic notions: formal language, hierarchy of grammars and languages. Finite automata: deterministic and nondeterministic finite automata, their extension, mutual relationship, and applications. Regular grammars and languages: relationship to finite automata, closure properties of regular languages, criteria of regularity, minimization of automata. Regular expressions and their applications: standard and extended regular expressions, application for text processing, selected topics. Context-free languages: definition and properties, derivation trees, properties of context-free languages and their relationship to regular languages Pushdown automata: variants, relationship to context-free languages, top-down syntactic analysis, bottom-up syntactic analysis, deterministic pushdown automata.

Learning activities and teaching methods
Laboratory Work
  • Preparation for the Course Credit - 10 hours per semester
  • Preparation for the Exam - 35 hours per semester
Learning outcomes
This is an introduction course to formal languages, grammars, and automata theory and their applications in computer science. The main emphasis is put on regular and context-free languages. The course introduces essential background which is needed to study topics in further courses including computability theory, complexity analysis, algorithm design for text searching, compiler constructions, etc., which are relevant for computer science applications.
1. Knowledge Describe basic generative and analytical formalisms for languages.
Prerequisites
Basic notions of discrete and algorithmic mathematics (sets, relations).

Assessment methods and criteria
Oral exam, Written exam, Student performance

Credit: students have to pass a written test and implement a simple program code Exam: students have to pass a written exam test
Recommended literature
  • Hopcroft J. E., Motwani R., Ullman J. D. (2006). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston.
  • Kozen, D. C. (1997). Automata and Computability. Springer, New York.
  • Kozen D. C. (1997). Automata and Computability. Springer.
  • LAWSON M. V. (2003). Finite Automata. Chapman & Hall/CRC.
  • Melichar, B. (2003). Jazyky a překlady. Skriptum, přepracované 2. vydání. Vydavatelství ČVUT, Praha.
  • Simovici D. A., Tenney R. L. (1999). Theory of Formal Languages with ApplicationsM. Simon. World Scientific, Singapore.
  • Sipser, M. (1997). Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA.
  • Sipser M. (1997). Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA.


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