Die Studierenden sollen einen der Grundpfeiler der Informatik als Wissenschaft, nämlich die theoretische Modellierung von Berechenbarkeit durch verschiedene Algroithmenmodelle, verstehen lernen. Dies umfasst das Verstehen und Anwenden von Formalisierungen, das Umsetzen sowie sichere Umgehen mit mathematischen Arbeitsweisen in der theoretischen Informatik und das Erkennen der Stärken und der Begrenzungen der wichtigsten Maschinenmodelle. Folgende Themen werden in der Vorlesung behandelt:

- 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

Alexander Asteroth, Christel Baier: Theoretische Informatik: eine Einführung in die Berechenbarkeit, Komplexität und formale Sprachen, Pearson Studium 2002.

Peter Bachmann: Grundlagen der Theoretischen Informatik, bookboon.com, 2015.

Katrin Erk, Lutz Priese: Theoretische Informatik - eine umfassende einführung, eXamen.press, 2008.

Dirk W. Hoffmann: Theoretische Informatik, Hanser, 2009.

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in Automatentheorie, Formale Sprachen und Bechenbarkeit, 3. aktualisierte Auflage, Pearson Studium 2011.

Juraj Hromkovic: Theoretische Informatik Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunkation und Kryptographie, Teubner, 2007.

Dexter C. Kozen: Automata and Computability, Springer 2007.

Harry R. Lewis, Chistos H. Papdimitriou: Elements of the Theory of Computation, Prentice Hall, 1981.

John E. Savage: Models of computation: Exploring the Power of Computing, Addison-Wesley 1998.

Michael Sipser: Inrofuction to the Theory of Computation, 3rd Edition, Cenpage Learning 2013.