Mathematische Grundlagen: Mengen, Relationen und Funktionen, Äquivalenzrelationen, Ordnungsrelationen, Komposition von Relationen

Grundbegriffe der Graphentheorie: gerichtete und ungerichtete Graphen, Adjazenzmatrix und Adjazenzlisten, Wege, Zyklen, Zusammenhang, Bäume, Spannbäume, gewurzelte Bäume, Traversierung von Bäumen

Formale Sprachen: Wörter, Sprachen, Konkatenation, Kleene'sche Hülle

Deterministische endliche Automaten (DEA): akzeptierte Sprache, Implementierung von DEAs, Äquivalenz von Automaten, Minimierung von DEAs

Nichtdeterministische endliche Automaten (NEA): Transformation von NEAs in DEAs, praktische Anwendung endlicher Automaten

Reguläre Ausdrücke: Syntax und Semantik reg. Ausdrücke, Strukturelle Induktion, epsilon-NEAs, Umwandlung reg. Ausdrücke in epsilon-NEAs, Transformation von epsilon-NEAs in DEAs, Konstruktion eines reg. Ausdrucks zu einem endl. Automaten, reguläre Sprachen, Abschlusseigenschaften, Pumping-Lemma, Anwendung: Scanner-Generatoren

Kontextfreie Grammatiken: Ableitungen, Ableitungsbäume, erzeugte Sprache, Mehrdeutigkeit, Äquivalenz, BNF, EBNF, Syntaxdiagramme

Kellerautomaten: nichtdet. Kellerautomat, Konfigurationen, Sprache eines Automaten, Zusammenhang zw. kontextfreien Grammatik und nichtdet. Kellerautomaten, deterministische Kellerautomaten

Top-Down-Syntaxanalyse: First- und Follow-Mengen, Bestimmung der Vorausschautabelle, LL(1) und LL(k)-Grammatiken, tabellengesteuerter Top-Down-Parser, Umformung von Grammatiken (Elimination von Mehrdeutigkeiten und Linksrekursion, Linksfaktorisierung), rekursiver Abstieg, Ausblick: Parser-Generatoren.

Chomsky-Hierarchie: Typ-0-, Typ-1-, Typ-2- und Typ-3-Grammatiken, Entscheidbarkeit des Wortproblems, Earley-Parser für Typ-2-Grammatiken

Einführung in Berechenbarkeit und Entscheidbarkeit: Berechenbarkeitsmodelle, Turing-Berechenbarkeit, These von Church, Entscheidbarkeit, Halteproblem