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 |