Theoretische Informatik
Studiengänge
Informatik Bachelor 3. Semester
Mathematik Bachelor 3. Semester
Informations- und Medientechnik Master
Modul 12215 Theoretische Informatik
Lehrinhalt:

- Reguläre Sprachen; deterministische und nicht-deterministische endliche Automaten; Minimalisierung; Abschlusseigenschaften regulärer Sprachen;
- Push-Down Automaten und kontextfreie Grammatiken; Normalformen; algorithmische Fragestellungen zu kontextfreien Sprachen; Abschlusseigenschaften;
- Turing-Maschine; Berechenbarkeit von Wortfunktionen; Entscheidungsprobleme; rekursive Aufzählbarkeit und Entscheidbarkeit; Halteproblem für Turing-Maschinen; Satz von Rice; Reduktion; allgemeine Grammatiken;
- linear-beschränkte Turing-Maschinen; Chomsky-Hierarchie;
- Simulation von Automaten durch Grammatiken und umgekehrt;
- Primitiv-rekursive und μ–rekursive Funktionen



Literatur:

- Hopcroft, Motwani, Ullmann: Introduction to Automata Theory, Languages
and Computation, Addison & Wesley
- Lewis, Papadimitriou: Elements of the Theory of Computation, Prentice Hall
- Savage: Models of Computation, Addison & Wesley

Lehrstuhl Theoretische Informatik
Institut für Informatik, Informations- und Medientechnik