Einführung in die Automatentheorie

Aktive Lernformen sind hier besonders wirksam, weil endliche Automaten abstrakte Konzepte sind, die durch konkrete Handlungen und Visualisierungen greifbar werden. Schüler verstehen Zustände, Übergänge und Akzeptanzbedingungen besser, wenn sie diese selbst modellieren und erleben statt nur zu beschreiben.

• Klasse 13
• Informatik Oberstufe: Komplexe Systeme und Theoretische Grundlagen
• 3 Aktivitäten
• 30 Min.–60 Min.

Lernziele

1. Analysieren Sie die Zustandsübergänge eines gegebenen endlichen Automaten anhand eines Zustandsdiagramms.
2. Erklären Sie die Funktion eines einfachen endlichen Automaten zur Erkennung eines spezifischen Musters in einer Zeichenkette.
3. Entwerfen Sie einen endlichen Automaten, der eine einfache Sprache (z. B. eine Zeichenkette, die mit 'a' beginnt) akzeptiert.
4. Vergleichen Sie die Akzeptanzfähigkeit zweier endlicher Automaten für dieselbe Eingabezeichenkette.
5. Bewerten Sie die Eignung eines endlichen Automaten zur Modellierung eines gegebenen technischen Systems (z. B. einer Ampel).

Rollenspiel

⏱ 45 Min.·Ganze Klasse

Rollenspiel: Der menschliche Automat

Schüler schlüpfen in die Rollen von Zuständen und Übergangsregeln. Ein 'Eingabewort' wird durch die Klasse gereicht, während die Schüler physisch die Position wechseln, um zu prüfen, ob das Wort akzeptiert wird.

Vorbereitung & Details

Erklären Sie, wie Automaten als Modelle für Berechnungen dienen können.

Moderationstipp: Legen Sie beim Rollenspiel klare Regeln für die Zustandsübergänge fest und lassen Sie die Schüler diese gemeinsam auf Klebezetteln an der Tafel visualisieren.

Setup: Spielfläche oder entsprechend angeordnete Tische für das Szenario

Materials: Rollenkarten mit Hintergrundinfos und Zielen, Szenario-Briefing

• Anwenden
• Analysieren
• Bewerten
• Sozialbewusstsein
• Selbstwahrnehmung

Forschungskreis

⏱ 60 Min.·Kleingruppen

Forschungskreis: Automaten-Reverse-Engineering

Kleingruppen erhalten Black-Box-Automaten (als Software-Simulation) und müssen durch gezielte Eingaben das zugrunde liegende Zustandsdiagramm rekonstruieren und präsentieren.

Vorbereitung & Details

Vergleichen Sie die Leistungsfähigkeit von Automaten mit menschlicher Problemlösung.

Moderationstipp: Nutzen Sie beim Reverse-Engineering verschiedene Automaten (z.B. Ampel, Getränkeautomat) und lassen Sie Schüler in Kleingruppen die Eingaben und Ausgaben systematisch dokumentieren.

Setup: Gruppentische mit Zugang zu Quellenmaterialien

Materials: Quellensammlung, Arbeitsblatt zum Forschungszyklus, Leitfaden zur Fragestellung, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Ich-Du-Wir (Denken-Austauschen-Vorstellen)

⏱ 30 Min.·Partnerarbeit

Ich-Du-Wir (Denken-Austauschen-Vorstellen): Reguläre Ausdrücke im Alltag

Schüler suchen Beispiele für reguläre Ausdrücke (z.B. E-Mail-Validierung) und entwerfen in Paaren den passenden endlichen Automaten dazu, bevor sie ihre Lösungen mit der Klasse vergleichen.

Vorbereitung & Details

Analysieren Sie die historischen Ursprünge der Automatentheorie und ihre Relevanz heute.

Moderationstipp: Fordern Sie beim Think-Pair-Share die Schüler auf, zunächst eigene Beispiele aus dem Alltag zu sammeln, bevor sie diese mit regulären Ausdrücken formalisieren.

Setup: Standard-Klassenzimmer; die Lernenden wenden sich dem Sitznachbarn zu

Materials: Diskussionsimpuls (projiziert oder gedruckt), Optional: Notizblatt für die Partnerarbeit

• Verstehen
• Anwenden
• Analysieren
• Selbstwahrnehmung
• Beziehungsfähigkeit

Dieses Thema unterrichten

Erfahrene Lehrkräfte beginnen mit einfachen, anschaulichen Beispielen wie einer Ampelschaltung oder einem Getränkeautomaten, bevor sie zu abstrakten Zustandsdiagrammen übergehen. Wichtig ist, dass Schüler selbst Fehler machen und diese korrigieren, um ein tiefes Verständnis für die Modellierung zu entwickeln. Vermeiden Sie Frontalunterricht zu Definitionen – lieber die Schüler die Definitionen aus ihren Beobachtungen ableiten lassen.

Was Sie erwartet

Am Ende der Einheit können Schüler endliche Automaten korrekt definieren, ihre Zustandsübergänge nachvollziehen und reguläre Sprachen mit Automaten verknüpfen. Sie erkennen die Grenzen endlicher Automaten und begründen diese mathematisch oder an Beispielen.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

During Rollenspiel: Der menschliche Automat, sehen Sie vor, dass Schüler annehmen, ein Automat könne sich unendlich viele Informationen merken.

Was Sie stattdessen lehren sollten

Nutzen Sie das Rollenspiel, um gezielt zu fragen: 'Wie merken Sie sich, welche Tasten bereits gedrückt wurden?' und lenken Sie den Fokus auf den aktuellen Zustand als einzige Speichereinheit.

Häufige Fehlvorstellung

During Collaborative Investigation: Automaten-Reverse-Engineering, halten Schüler nicht-deterministische Automaten für leistungsfähiger als deterministische.

Was Sie stattdessen lehren sollten

Lassen Sie die Schüler während der Untersuchung vergleichen, wie dieselbe Sprache einmal mit und einmal ohne Nicht-Determinismus modelliert wird, und diskutieren Sie, warum beide Ansätze zum gleichen Ergebnis führen.

Ideen zur Lernstandserhebung

Lernstandskontrolle

After Rollenspiel: Der menschliche Automat, geben Sie den Schülern ein Zustandsdiagramm eines einfachen Automaten (z.B. für eine Tür mit Sensoren) und lassen Sie sie die Übergangsfunktion für eine gegebene Eingabefolge beschreiben.

Kurze Überprüfung

During Think-Pair-Share: Reguläre Ausdrücke im Alltag, zeigen Sie eine kurze Zeichenkette und ein Zustandsdiagramm. Fragen Sie: 'Welchen Zustand erreicht der Automat nach dem dritten Symbol? Begründen Sie kurz ihre Antwort in einem Satz.'

Diskussionsfrage

After Collaborative Investigation: Automaten-Reverse-Engineering, diskutieren Sie in Kleingruppen: 'Warum kann ein endlicher Automat keine verschachtelten Klammern erkennen? Zeigen Sie dies an einem konkreten Beispiel aus den untersuchten Automaten.'

Erweiterungen & Unterstützung

• Fordern Sie schnelle Schüler auf, einen nicht-deterministischen Automaten für ein komplexes Muster (z.B. 'aa*bb*') zu entwerfen und diesen in einen deterministischen umzuwandeln.
• Unterstützen Sie unsichere Schüler durch vorgefertigte Zustandsdiagramme mit Lücken, die sie mit Eingaben und Übergängen vervollständigen müssen.
• Vertiefen Sie mit einer Gruppenarbeit: Entwickeln Sie einen Automaten für eine einfache Programmiersprache mit Schlüsselwörtern und formalisieren Sie dessen Grammatik in regulären Ausdrücken.

Schlüsselvokabular

Zustand	Eine Konfiguration oder ein Status, in dem sich ein Automat zu einem bestimmten Zeitpunkt befinden kann. Die Anzahl der Zustände ist endlich.
Alphabet	Eine endliche Menge von Symbolen, die von einem Automaten verarbeitet werden können. Dies sind die 'Bausteine' der Eingabezeichenketten.
Übergangsfunktion	Eine Regel, die bestimmt, von welchem Zustand der Automat in den nächsten Zustand wechselt, abhängig vom aktuellen Zustand und dem gelesenen Eingabesymbol.
Akzeptierender Zustand	Ein spezieller Zustand, in dem sich der Automat am Ende der Eingabe befinden muss, damit die Eingabe als 'gültig' oder 'akzeptiert' gilt.
Zustandsdiagramm	Eine grafische Darstellung eines Automaten, die Zustände als Knoten und Übergänge als gerichtete Kanten zeigt.