Learning objectives:
Students acquire the skills to
- develop an understanding of basic concepts, terms and relationships from the fields of automata theory and formal languages.
- develop an understanding of basic proof methods. develop the ability to carry out simple proofs independently.
- gain knowledge of the performance of different description tools and develop the ability to use the description tools independently.
- gain knowledge of the relationship between the performance and algorithmic controllability of different description methods.
- develop an understanding of non-deterministic machine models and their significance.
Course content:
- Basic concepts: Words, alphabets, relations, operations over relations
- Formal languages: The word problem, relation to general decision problems, efficient versus non-efficient solution algorithms for the word problem
- Formal languages and automata theory: deterministic and non-deterministic finite automata, application of finite automata, equivalence of deterministic and non-deterministic finite automata, minimization algorithm, deterministic and non-deterministic basement automata
- Formal languages and grammars: Chomsky hierarchy, efficiently enumerable languages and the word problem (undecidability of the word problem), context-sensitive grammars and the word problem (relation to the complexity class NP), right-linear grammars, closure properties, regular expressions (incl. (incl. use in scripting languages), termination properties, right-linear languages and the word problem (finite automata), context-sensitive grammars and the word problem, context-free grammars and the word problem (Chomsky normal form, CYK algorithm), applications of context-free languages (syntax of programming languages, XML-based languages and languages for describing communication protocols), context-free languages and non-deterministic basement automata, deterministic basement automata
