• Berechenbarkeit auf der Basis von LOOP/WHILE-Programmen, partiell-rekursiven Funktionen, Registermaschinen, Turingmaschinen; 
• Äquivalenz der Berechenbarkeitsbegriffe; 
• Existenz von durch Algorithmen nicht berechenbarer Funktionen und unentscheidbarer Probleme;
• Beispiele unentscheidbarer Probleme;
• formale Grammatiken und die von ihnen erzeugten Sprachen; 
• rekursiv-aufzählbare, kontextabhängige, kontextfreie und reguläre Sprachen; 
• Normalformen; 
• Chomsky-Hierarchie

• U. Schöning: Theoretische Informatik kurz gefasst. B.I.-Wissenschaftsverlag, 1992.
• K. Wagner: Einführung in die Theoretische Informatik. Springer-Verlag, 2003.
• I. Wegener: Theoretische Informatik. Teubner-Verlag, 1993.
• J.E. Hopcroft, J.D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2. Aufl., Addison-Wesley, 1990.
• G. Vossen, K.-U. Witt: Grundlagen der Theoretischen Informatik mit Anwendungen.
• Vieweg-Verlag, Braunschweig, 2000.
• A. Asteroth, Ch. Baier: Theoretische Informatik. Pearson Studium, 2002.

Die Leistungsbewertung erfolgt durch eine abschließende Klausur.

Zulassungsvoraussetzung für die Klausur ist die erfolgreiche Teilnahme an den Übungen.

Die Teilnahme an den Übungen ist für Studierende erfolgreich, wenn er oder sie durch Votierungen für mindestens zwei Drittel aller Übungsaufgaben erklärt, dass er oder sie die Lösung der jeweiligen Übungsaufgaben präsentieren kann und dies auf Aufforderung nachweist.

Für Studierende, die zum wiederholten Mal teilnehmen und die oben genannte Teilleistung bereits erbracht haben, gilt: die Prüfungsnebenleistung muss nicht erneut erbracht werden