|
Instructors: Prof. Dr. phil. nat. Ulrich Kohlenbach; M.Sc. Jendrik Brachter; Dr. Pedro Pinto
Event type:
Lecture & Exercise
Org-unit: Dept. 04 - Mathematics
Displayed in timetable as:
FGdI I
Subject:
Crediting for:
Hours per week:
3
Language of instruction:
German
Min. | Max. participants:
- | -
Course Contents:
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)
Preconditions:
none
|
