Diese Vorlesung, die eine grundlegende Einführung in die theoretische Informatik gibt, zerfällt in drei Themengebiete.
 
* Automaten: In diesem Teil geht es um formale Sprachen, insbesondere um die Klassen der regulären und der kontextfreien Sprachen. Automaten sind mathematische Objekte, die solche Sprachen erkennen, wohingegen es sich bei Grammatiken um spracherzeugende Objekte handelt.
 
* Berechenbarkeit: Wir befassen uns mit der Frage nach einer mathematischen Definition des intuitiven Begriffs der Berechenbarkeit. Welche Probleme sind prinzipiell (unabhäging von verwendeten Rechnern oder Algorithmen) lösbar oder unlösbar? Wir werden verschiedene äquivalente Beschreibungen lösbarer Probleme erhalten.
 
* Komplexität: Probleme, die in Teil 2 der Vorlesung als entscheidbar identifiziert wurden, werden in diesem Teil weiter klassifiziert nach dem Aufwand, den man zu ihrer Lösung betreiben muss. Wichtige Kriterien für diesen Aufwand sind Zeit- und Platzverbrauch.