Informatik · Klasse 13

Ideen für aktives Lernen

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.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Formale Sprachen und Automaten

• 30–60 Min.
• Partnerarbeit → Ganze Klasse
• 4 Aktivitäten

Aktivität 01

• 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.

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.

Worauf zu achten ist

Geben Sie den Schülerinnen und Schülern ein kurzes Wort (z.B. '(()())' oder 'abccba') und bitten Sie 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.

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

Aktivität 02

• 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.

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.

Worauf zu achten ist

Stellen Sie die Frage: 'Warum kann ein endlicher Automat keine Sprache erkennen, die aus allen Wörtern besteht, bei denen die Anzahl der 'a's gleich der Anzahl der 'b's ist, während ein Kellerautomat dies kann?' Leiten Sie die Diskussion auf die Rolle des Stapelspeichers.

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

Aktivität 03

• 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.

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.

Worauf zu achten ist

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.

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

Aktivität 04

• 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.

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.

Worauf zu achten ist

Geben Sie den Schülerinnen und Schülern ein kurzes Wort (z.B. '(()())' oder 'abccba') und bitten Sie 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.

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

Einige Hinweise zum Unterrichten dieser Einheit

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.

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

• 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.'

  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.'

• 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.'

  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.'

• 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.'

  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.'

---

In dieser Übersicht verwendete Methoden

• Planspiel