Lehrinhalte
introduction: transition systems, words, languages; basic mathematical methods and proof patterns; finite automata and regular languages; determinism and nondeterminism, closure properties and automata constructions, Kleene Theorem, Myhill-Nerode Theorem, pumping lemma;
grammars and the Chomsky hierrachy, context-free languages, pumping lemma, CYK algorithm;
models of computation: PDA and Turing machines; decidability and recursive enumerability in the Chomsky hierarchy
Literature
Schöning: Theoretische Informatik -- kurz gefasst
\newline
Hopcroft, Motwani, Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie
\newline
Wegener: Theoretische Informatik -- eine algorithmenorientierte Einführung
\newline
Skript (elektronisch unter www.mathematik.tu-darmstadt.de/otto)
Voraussetzungen
none
introduction: transition systems, words, languages; basic mathematical methods and proof patterns; finite automata and regular languages; determinism and nondeterminism, closure properties and automata constructions, Kleene Theorem, Myhill-Nerode Theorem, pumping lemma;
grammars and the Chomsky hierrachy, context-free languages, pumping lemma, CYK algorithm;
models of computation: PDA and Turing machines; decidability and recursive enumerability in the Chomsky hierarchy
Literature
Schöning: Theoretische Informatik -- kurz gefasst
\newline
Hopcroft, Motwani, Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie
\newline
Wegener: Theoretische Informatik -- eine algorithmenorientierte Einführung
\newline
Skript (elektronisch unter www.mathematik.tu-darmstadt.de/otto)
Voraussetzungen
none
- Lehrende: Markus Anders
- Lehrende: Kord Eickmeyer
- Lehrende: Ulrich Kohlenbach
- Lehrende: Pedro Pinto
- Lehrende: Thomas Schneider
Semester: Inverno 2021/22