Course: Formal Languages and Automata

« Back
Course title Formal Languages and Automata
Course code KMI/FJ
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, Compulsory-optional
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
Lecturer(s)
  • Vychodil Vilém, doc. RNDr. Ph.D.
  • Kühr Tomáš, Mgr. 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
Lecture, Demonstration
  • Preparation for the Course Credit - 10 hours per semester
  • Preparation for the Exam - 35 hours per semester
Learning outcomes
The students become familiar with basic concepts of formal languages.
1. Knowledge Describe basic generative and analytical formalisms for languages.
Prerequisites
unspecified

Assessment methods and criteria
Oral exam, Written exam

Active participation in class. Completion of assigned homeworks. Passing the oral (or written) exam.
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
Faculty of Science Computer Science for Education (1) Informatics courses 2 Summer
Faculty of Science Bioinformatics (1) Informatics courses 2 Summer
Faculty of Science Computer Science (1) Informatics courses 2 Summer
Faculty of Science Computer Physics (1) Physics courses 2 Summer
Faculty of Science Applied Computer Science (1) Informatics courses 2 Summer