| INFB Formal Languages / Automata Theory | Course | INF | |
|---|---|---|---|
| Lecturers : |
Prof. Dr. Matthias Homeister
eMail
|
Term | 2 |
| Course Classification : | Bachelor Informatik | CH | 4 |
| Language : | Deutsch/Englisch | Type | VÜ |
| Type of examination : | PL | Credits | 5 |
| Method of evaluation : | written examination 120 min | ||
| Requirements : |
Computer Science and Logic
Mathematics I | ||
| Cross References : | |||
| Previous knowledges : | Mathematics I Programming I | ||
| Aids and special features : | Mode of assessment Additional assessments during the semester may be included in the final grading. | ||
| Teaching aims : | The students are familiar with the main ideas and techniques of theoretical computer science (abstraction, rigour and logical reasoning). They are able to formulate issues in different representations (e.g. graph and table representations of automata) and transform them from one representation into the other. They are able to construct, analyse and apply deterministic and nondeterministic finite automata. They are able to construct, analyse and apply regular expressions They are able to apply transformations on and between automata (minimization, NFA into DFA, regular expression into NFA) and to prove whether a language is regular or not. They are able to construct, analyse and apply context-free grammars. They can convert CFGs into Chomsky normal form and understand the CYK-algorithm. They can determine whether a language is context-free or not. They understand the relationship between automata and grammars, they know context-sensitive grammars and are able to classify formal languages with respect to the Chomsky hierarchy. They understand the role of formal languages, automata and grammars in the context of compiler construction. | ||
| Contents : | Regular languages: deterministic and nondeterministic finite automata, transformations (minimal DFAs, NFA into DFA, regular expression into NFA), regular expressions, lexical analysis, pumping lemma. | ||
| Literature : | Sipser: Introduction to the Theory of Computation, Cengage Learning, 3rd edition, 2013 Socher R.: Theoretische Grundlagen der Informatik. 3. Aufl. München: Hanser Verlag 2008 Wagenknecht, Hielscher: Formale Sprachen, abstrakte Automaten und Compiler. 2. Auflage, Wiesbaden, Springer-Vieweg, 2015 Vossen G., Witt K.-U.: Grundkurs theoretische Informatik. 6. Aufl. Wiesbaden: Springer-Vieweg, 2016 Böckenhauer, Hromkovic.: Formale Sprachen. Wiesbaden, Springer-Vieweg, 2012 | ||