(Letzte Änderung: 12.August 2002)
Laut Lehrplan sollen vermittelt werden:
Zeichenketten, Alphabete, formale Sprachen (Backus-Naur)
Induktionsbeweise (nicht nur für natürl. Zahlen)
Endliche Automaten und reguläre Sprachen
Kellerautomaten und kontextfreie Sprachen
Turingmaschinen, Registermaschinen und rekursive Funktionen
Unentscheidbare Probleme
Anfänge der Komplexitätstheorie