|
Lecturer(s)
|
-
Masopust Tomáš, doc. RNDr. Ph.D., DSc.
-
Balun Jiří, Mgr.
|
|
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.
-
LAWSON. (2003). Finite Automata. Chapman & Hall/CRC.
-
Linz, P. (2016). An Introduction to Formal Languages and Automata. Jones and Bartlett Publishers, Inc.
-
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 Applications. World Scientific, Singapore.
-
Sipser M. (1997). Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA.
|