Dieses Übungsheft für den Informatikunterricht der Oberstufe bietet eine fundierte, systematische und anschauliche Einführung in die theoretische Informatik. Das Material verknüpft abstrakte mathematische Konzepte mit praxisnahen Beispielen und führt die Lernenden Schritt für Schritt von den Grundlagen formaler Sprachen bis hin zu den theoretischen Grenzen regulärer Ausdrücke.

Inhaltliche Schwerpunkte:

• Formale Grundlagen:Einführung in Alphabete, Wörter und die präzise Definition von formalen Sprachen.

• Endliche Automaten:Aufbau, Funktionsweise und Konstruktion von deterministischen (DEA) und nichtdeterministischen endlichen Automaten (NEA) sowie deren Umwandlung (Potenzmengen-Konstruktion).

• Reguläre Ausdrücke:Formulierung von Mustern (Regex), Anwendung in der Praxis mit Python (re-Modul) und die theoretische Verknüpfung durch den Satz von Kleene.

• Grenzen der Regularität:Methodische Anwendung des Pumping-Lemmas zum mathematischen Beweis, dass bestimmte Sprachen nicht regulär sind.

Aufbau und didaktische Struktur:

• Theorie und Anwendung:Jedes Kapitel kombiniert kompakte, leicht verständliche Erklärungen mit direkt darauffolgenden Übungsaufgaben (z. B. Spurtabellen ausfüllen, Automaten modellieren, Regex entwerfen).

• Integrierte Differenzierung:Die Aufgabenstellungen sind durch ein transparentes Sterne-System in drei Anforderungsbereiche (leicht, mittel, schwer) unterteilt, um unterschiedlichen Leistungsniveaus gerecht zu werden.

• Zusatzmaterialien:Ein kompaktes Fachglossar klärt alle relevanten Begrifflichkeiten (z. B. Alphabet, ε-Übergang, Kleene-Stern). Ein ausführlicher Lösungsteil mit ausformulierten Erklärungen und Skizzen-Beschreibungen ermöglicht eine zuverlässige (Selbst-)Kontrolle.

Einsatzmöglichkeiten im Unterricht:Das modular aufgebaute Material ist auf einen Umfang von etwa 8 bis 12 Unterrichtsstunden ausgelegt und deckt die Kernthemen der theoretischen Informatik in der Oberstufe ab. Der Großteil der Aufgaben lässt sich analytisch und ohne Computer („unplugged“) mit Stift und Papier bearbeiten. Für die praktische Vertiefung bietet das Python-Kapitel eine direkte Brücke in die angewandte Programmierung.