Kellerautomaten und kontextfreie Sprachen

Kellerautomaten sind für Schülerinnen und Schüler oft abstrakt, weil sie Zustände mit Stapeloperationen kombinieren. Aktive Stationsarbeit und Simulationen machen sichtbar, warum der Stapel für geschachtelte Strukturen wie Klammerausdrücke notwendig ist. Durch praktische Anwendung wird die Theorie greifbar und die Motivation steigt.

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

Lernziele

1. Erklären Sie die Funktionsweise eines Kellerautomaten anhand eines gegebenen Wortes und eines leeren Stapels.
2. Vergleichen Sie die Akzeptanzkriterien von Kellerautomaten und endlichen Automaten für eine gegebene Sprache.
3. Analysieren Sie die Struktur von verschachtelten Klammerausdrücken und weisen Sie die erforderlichen Stapeloperationen zu.
4. Entwerfen Sie einen einfachen Kellerautomaten für eine spezifische kontextfreie Sprache, z.B. Palindrome.
5. Bewerten Sie die Eignung eines Kellerautomaten zur Erkennung einer gegebenen Sprachstruktur im Vergleich zu einem endlichen Automaten.

Planspiel

⏱ 50 Min.·Kleingruppen

Stationenrotation: Komponenten eines Kellerautomaten

Richten Sie vier Stationen ein: Zustandsübergänge modellieren (mit Karten), Stapeloperationen simulieren (mit Stapelwürfeln), Eingabe verarbeiten (mit Beispielwörtern) und Akzeptanz prüfen (mit Entscheidungsbäumen). Gruppen rotieren alle 10 Minuten und protokollieren Beobachtungen. Abschließende Plenumdiskussion verbindet Stationen.

Vorbereitung & Details

Erklären Sie die Funktionsweise eines Kellerautomaten und seine Komponenten.

Moderationstipp: Bei der Stationenrotation achten Sie darauf, dass die Materialien für den Stapelkopf und die Übergangsführung klar beschriftet sind, damit die Schüler die mechanische Bewegung nachvollziehen können.

Setup: Flexibler Raum für verschiedene Gruppenstationen

Materials: Rollenkarten mit Zielen und Ressourcen, Spielwährung oder Token, Rundenprotokoll

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Entscheidungsfähigkeit

Planspiel

⏱ 30 Min.·Partnerarbeit

Paararbeit: Klammerausdrücke analysieren

Paare erhalten Klammersequenzen und simulieren einen Kellerautomaten mit Papierstreifen als Stapel. Sie pushen bei öffnender Klammer, poppen bei schließender und notieren Zustandswechsel. Fehlkonfigurationen diskutieren sie und korrigieren gemeinsam.

Vorbereitung & Details

Vergleichen Sie die Fähigkeiten von Kellerautomaten mit endlichen Automaten.

Moderationstipp: Legen Sie bei der Paararbeit zu Klammerausdrücken Wert auf lautes Aussprechen der Stapeloperationen, um die Zusammenarbeit zu fördern und Missverständnisse früh zu erkennen.

Setup: Flexibler Raum für verschiedene Gruppenstationen

Materials: Rollenkarten mit Zielen und Ressourcen, Spielwährung oder Token, Rundenprotokoll

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Entscheidungsfähigkeit

Planspiel

⏱ 45 Min.·Kleingruppen

Gruppenaufgabe: PDA vs. endlicher Automat

Gruppen bauen Modelle für reguläre und kontextfreie Sprachen: einen endlichen Automaten für a*b und einen Kellerautomaten für balanced Klammern. Sie testen Wörter und vergleichen Erfolge. Präsentation der Ergebnisse im Plenum.

Vorbereitung & Details

Analysieren Sie, wie Kellerautomaten die Struktur von Klammerausdrücken verarbeiten.

Moderationstipp: Bei der Gruppenaufgabe PDA vs. endlicher Automat weisen Sie die Gruppen an, konkrete Beispiele zu sammeln, bei denen ein endlicher Automat scheitert, um die Notwendigkeit des Stapels zu verdeutlichen.

Setup: Flexibler Raum für verschiedene Gruppenstationen

Materials: Rollenkarten mit Zielen und Ressourcen, Spielwährung oder Token, Rundenprotokoll

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Entscheidungsfähigkeit

Planspiel

⏱ 60 Min.·Einzelarbeit

Individuelle Programmierung: PDA-Simulator

Schüler implementieren einen einfachen Kellerautomaten in Python mit Stack-Datenstruktur. Geben Sie Vorlagen und Testfälle. Sie testen mit eigenen Wörtern und debuggen Fehler.

Vorbereitung & Details

Erklären Sie die Funktionsweise eines Kellerautomaten und seine Komponenten.

Moderationstipp: Beim individuellen Programmieren des PDA-Simulators geben Sie klare Beispiele vor, die bereits akzeptierte und abgelehnte Wörter enthalten, um die Debugging-Fähigkeiten zu schärfen.

Setup: Flexibler Raum für verschiedene Gruppenstationen

Materials: Rollenkarten mit Zielen und Ressourcen, Spielwährung oder Token, Rundenprotokoll

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Entscheidungsfähigkeit

Dieses Thema unterrichten

Experten empfehlen, Kellerautomaten zunächst mit konkreten Beispielen wie Klammerausdrücken oder Palindromen zu starten, bevor abstrakte Definitionen folgen. Visualisierungen des Stapels als 'Gedächtnis' helfen, die Rolle des Stapels zu veranschaulichen. Vermeiden Sie es, den Stapel als 'Ersatz' für Zustände darzustellen, sondern betonen Sie die Ergänzung. Praktische Simulationen zeigen schneller als theoretische Erklärungen, warum deterministische und nicht-deterministische Kellerautomaten unterschiedlich mächtig sind.

Was Sie erwartet

Am Ende können die Schülerinnen und Schüler die Komponenten eines Kellerautomaten benennen, einfache kontextfreie Sprachen mit Stapeloperationen verarbeiten und die Grenzen endlicher Automaten erklären. Sie erkennen, wann ein Stapel benötigt wird und wie Zustände mit Stapelinhalten zusammenwirken.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Während der Stationenrotation zu den Komponenten eines Kellerautomaten achten Sie darauf, dass Schüler nicht annehmen, der Stapel ersetze alle Zustände des Automaten. Korrigieren Sie dies mit dem Hinweis: 'Beobachten Sie in der Station zur Übergangsführung, wie Zustände und Stapel zusammenarbeiten – der Stapel speichert nur temporäre Informationen.'

Was Sie stattdessen lehren sollten

Während der Stationenrotation zu den Komponenten eines Kellerautomaten achten Sie darauf, dass Schüler nicht annehmen, der Stapel ersetze alle Zustände des Automaten. Korrigieren Sie dies mit dem Hinweis: 'Beobachten Sie in der Station zur Übergangsführung, wie Zustände und Stapel zusammenarbeiten – der Stapel speichert nur temporäre Informationen.'

Häufige Fehlvorstellung

Während der Gruppenaufgabe PDA vs. endlicher Automat beobachten Sie, ob Schüler den Stapel als universellen Ersatz für alle Sprachen sehen. Lenken Sie die Diskussion mit dem Hinweis: 'Vergleichen Sie in Ihrer Gruppe die akzeptierten Wörter der beiden Automaten – wo scheitert der endliche Automat konkret? Beschreiben Sie das mit Stapeloperationen.'

Was Sie stattdessen lehren sollten

Während der Gruppenaufgabe PDA vs. endlicher Automat beobachten Sie, ob Schüler den Stapel als universellen Ersatz für alle Sprachen sehen. Lenken Sie die Diskussion mit dem Hinweis: 'Vergleichen Sie in Ihrer Gruppe die akzeptierten Wörter der beiden Automaten – wo scheitert der endliche Automat konkret? Beschreiben Sie das mit Stapeloperationen.'

Häufige Fehlvorstellung

Während der individuellen Programmierung des PDA-Simulators achten Sie darauf, dass Schüler annehmen, jeder Stapelinhalt führe zur Akzeptanz. Weisen Sie sie an: 'Testen Sie in Ihrem Simulator Wörter wie 'aabb', die bei leerem Stapel nicht akzeptiert werden, und dokumentieren Sie, warum der Zustand ebenfalls eine Rolle spielt.'

Was Sie stattdessen lehren sollten

Während der individuellen Programmierung des PDA-Simulators achten Sie darauf, dass Schüler annehmen, jeder Stapelinhalt führe zur Akzeptanz. Weisen Sie sie an: 'Testen Sie in Ihrem Simulator Wörter wie 'aabb', die bei leerem Stapel nicht akzeptiert werden, und dokumentieren Sie, warum der Zustand ebenfalls eine Rolle spielt.'

Ideen zur Lernstandserhebung

Lernstandskontrolle

Nach der Stationenrotation zu den Komponenten des Kellerautomaten geben Sie den Schülerinnen und Schülern ein kurzes Wort wie '(())' und bitten sie, die notwendigen Stapeloperationen (Push/Pop) und Zustandswechsel zu notieren, um das Wort mit einem vorgegebenen Kellerautomaten zu akzeptieren. Sie sollen auch angeben, ob das Wort akzeptiert wird.

Diskussionsfrage

Nach der Paararbeit zu Klammerausdrücken leiten Sie eine Diskussion mit der Frage: 'Warum kann ein endlicher Automat keine Sprache erkennen, bei der die Anzahl der 'a's gleich der Anzahl der 'b's ist, während ein Kellerautomat dies kann?' Fokussieren Sie die Diskussion auf die Rolle des Stapelspeichers und die temporäre Speicherung von Symbolen.

Kurze Überprüfung

Während der Gruppenaufgabe PDA vs. endlicher Automat zeigen Sie eine einfache kontextfreie Grammatik für Klammerausdrücke. Bitten Sie die Schüler, eine Regel zu identifizieren, die die Notwendigkeit eines Stapelspeichers verdeutlicht, und erklären Sie kurz, warum diese Regel ohne Stapel nicht umsetzbar wäre.

Erweiterungen & Unterstützung

• Fordern Sie schnelle Schüler auf, einen nicht-deterministischen Pfad für ein Wort mit Mehrdeutigkeiten wie 'aabbb' zu entwerfen und im PDA-Simulator zu testen.
• Für Schüler, die Schwierigkeiten haben, bereiten Sie einen vereinfachten Kellerautomaten mit nur einem Zustand vor, der die Stapeloperationen Schritt für Schritt zeigt.
• Vertiefen Sie die Theorie, indem Sie die Schüler eine Grammatik in einen Kellerautomaten umwandeln lassen und umgekehrt, um die Verbindung zwischen beiden Konzepten zu verdeutlichen.

Schlüsselvokabular

Kellerautomat (Pushdown-Automat)	Ein abstrakter Automat, der die Fähigkeiten eines endlichen Automaten um einen Stapelspeicher erweitert. Er kann Symbole auf den Stapel legen (push) und vom Stapel nehmen (pop).
Kontextfreie Sprache	Eine Sprache, deren Wörter durch eine kontextfreie Grammatik erzeugt werden können. Kellerautomaten sind die entsprechenden Automatenmodelle für diese Sprachen.
Stapel (Stack)	Eine Datenstruktur, die nach dem LIFO-Prinzip (Last-In, First-Out) arbeitet. Symbole werden oben hinzugefügt und oben entfernt.
Übergangsfunktion	Definiert, wie der Automat seinen Zustand, den Inhalt des Stapels und das nächste Eingabesymbol verarbeitet, um den nächsten Zustand und die Stapeländerung zu bestimmen.
Akzeptanzbedingung	Die Kriterien, die erfüllt sein müssen, damit ein Kellerautomat ein eingegebenes Wort als gültig erkennt, z.B. das Erreichen eines Endzustands oder das Leeren des Stapels.