Informatik · Klasse 13

Ideen für aktives Lernen

Chomsky-Hierarchie der formalen Sprachen

Für die Chomsky-Hierarchie funktioniert aktives Lernen besonders gut, weil Schülerinnen und Schüler durch praktische Erfahrungen mit Automaten und Grammatiken abstrakte Konzepte greifbar machen. Die vier Typen werden durch eigenes Handeln – Bauen, Klassifizieren, Vergleichen – zu nachvollziehbaren Bausteinen des Wissens.

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

• 20–45 Min.
• Partnerarbeit → Ganze Klasse
• 4 Aktivitäten

Aktivität 01

• Gruppenpuzzle
• 45 Min. · Kleingruppen

Klassifikations-Rallye: Chomsky-Typen zuordnen

Teilen Sie Sprachbeispiele wie {a^n b^n} oder reguläre Muster auf Karten aus. Gruppen ordnen sie in 10 Minuten den Typen zu und begründen mit Grammatikregeln. Diskutieren Sie dann im Plenum die Grenzen.

Erklären Sie die verschiedenen Klassen der Chomsky-Hierarchie und ihre Beziehungen.

Moderationstipp

Während der Klassifikations-Rallye stellen Sie sicher, dass jedes Team mindestens ein Beispiel aus der Informatik (z.B. reguläre Ausdrücke in Suchmustern) und eines aus der Linguistik (z.B. Grammatikregeln) bearbeitet.

Worauf zu achten ist

Geben Sie jeder Schülerin und jedem Schüler eine Karte mit einer kurzen Beschreibung einer formalen Sprache (z.B. 'Sprache aller Palindrome über {a, b}' oder 'Sprache aller Wörter mit gleich vielen a's und b's'). Die Schüler sollen die entsprechende Klasse der Chomsky-Hierarchie (Typ-0, Typ-1, Typ-2, Typ-3) notieren und kurz begründen, warum sie diese Klasse gewählt haben.

• Verstehen
• Analysieren
• Bewerten
• Beziehungsfähigkeit
• Selbststeuerung

Aktivität 02

• Gruppenpuzzle
• 30 Min. · Partnerarbeit

Automaten-Bauwerkstatt: Pushdown vs. Endlich

Paare bauen mit Karten und Stapeln einen Pushdown-Automaten für eine kontextfreie Sprache und vergleichen mit einem endlichen Automaten. Testen Sie mit Eingaben und protokollieren Erfolge.

Vergleichen Sie die Ausdrucksstärke der verschiedenen Sprachklassen.

Moderationstipp

In der Automaten-Bauwerkstatt lassen Sie die Schülerinnen und Schüler die Automaten zunächst auf Papier skizzieren, bevor sie sie in einer Simulation testen, um den Transfer vom Modell zur Anwendung zu fördern.

Worauf zu achten ist

Stellen Sie eine Liste von Beispielen für Produktionsregeln auf (z.B. S -> aSb, A -> a, B -> BC). Bitten Sie die Schüler, die Regeln zu analysieren und zu entscheiden, ob sie zu einer regulären, kontextfreien oder kontextsensitiven Grammatik gehören könnten. Diskutieren Sie die Ergebnisse im Plenum.

• Verstehen
• Analysieren
• Bewerten
• Beziehungsfähigkeit
• Selbststeuerung

Aktivität 03

• Gruppenpuzzle
• 20 Min. · Ganze Klasse

Hierarchie-Ketten: Ausdrucksstärke verknüpfen

Im Plenum zeichnen Schüler eine Kette der Typen auf dem Whiteboard und ergänzen Beispiele. Jede Gruppe fügt ein reales Anwendungsbeispiel hinzu, z. B. XML-Parsing.

Analysieren Sie, warum Programmiersprachen in bestimmten Klassen der Hierarchie liegen.

Moderationstipp

Bei der Hierarchie-Ketten-Aktivität achten Sie darauf, dass Gruppen nicht nur Listen erstellen, sondern die Beziehungen zwischen den Typen mit konkreten Beispielen begründen, z.B. warum eine Sprache Typ-1 ist, aber nicht Typ-2.

Worauf zu achten ist

Fragen Sie die Klasse: 'Warum sind die meisten Programmiersprachen als kontextfrei (Typ-2) klassifiziert, und welche Einschränkungen ergeben sich daraus für die Beschreibung komplexer Sprachkonstrukte?' Leiten Sie eine Diskussion über die praktische Relevanz dieser Klassifizierung für die Softwareentwicklung.

• Verstehen
• Analysieren
• Bewerten
• Beziehungsfähigkeit
• Selbststeuerung

Aktivität 04

• Gruppenpuzzle
• 25 Min. · Einzelarbeit

Sprachen-Quiz: Typ-Entscheidung

Individuell lösen Schüler Aufgaben zur Klassifikation von Grammatiken. Tauschen Sie dann Lösungen in Pairs aus und korrigieren gemeinsam.

Erklären Sie die verschiedenen Klassen der Chomsky-Hierarchie und ihre Beziehungen.

Moderationstipp

Im Sprachen-Quiz verwenden Sie bewusst auch mehrdeutige Beispiele wie {a^n b^n | n ≥ 0}, um die Diskussion über kontextfreie vs. kontextsensitive Sprachen anzuregen.

Worauf zu achten ist

Geben Sie jeder Schülerin und jedem Schüler eine Karte mit einer kurzen Beschreibung einer formalen Sprache (z.B. 'Sprache aller Palindrome über {a, b}' oder 'Sprache aller Wörter mit gleich vielen a's und b's'). Die Schüler sollen die entsprechende Klasse der Chomsky-Hierarchie (Typ-0, Typ-1, Typ-2, Typ-3) notieren und kurz begründen, warum sie diese Klasse gewählt haben.

• Verstehen
• Analysieren
• Bewerten
• Beziehungsfähigkeit
• Selbststeuerung

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte beginnen mit konkreten Beispielen aus der Lebenswelt der Schüler, z.B. regulären Ausdrücken in Suchmaschinen oder der Struktur von Programmiersprachen wie Python. Vermeiden Sie abstrakte Definitionen am Anfang – stattdessen lassen Sie die Lernenden zunächst beobachten, wie Automaten oder Grammatiken funktionieren. Wichtig ist, die Hierarchie als Werkzeug zu vermitteln: Welche Klasse eignet sich für welche Aufgabe? Nutzen Sie dabei immer wieder Vergleiche zwischen den Typen, z.B. durch Gegenüberstellungen von endlichen Automaten und Pushdown-Automaten.

Am Ende der Einheit können die Lernenden die vier Chomsky-Typen sicher unterscheiden, Produktionsregeln korrekt zuordnen und die Ausdrucksstärke der Klassen anhand von Beispielen erläutern. Sie argumentieren sachlich und nutzen Fachbegriffe präzise in Diskussionen.

---

Vorsicht vor diesen Fehlvorstellungen

• Während der Klassifikations-Rallye beobachten Sie, dass einige Schüler Programmiersprachen wie C als regulär einordnen.

  Lassen Sie diese Schüler die Grammatikregeln von C (z.B. verschachtelte Bedingungen oder Funktionen) analysieren und gemeinsam mit der Gruppe überlegen, warum diese Strukturen den Pushdown-Automaten erfordern. Nutzen Sie die bereitgestellten Grammatikbeispiele aus der Bauwerkstatt als Vergleich.

• Während der Hierarchie-Ketten-Aktivität wird behauptet, dass Typ-0-Sprachen in der Praxis immer die beste Wahl sind.

  Fordern Sie die Gruppe auf, die Unentscheidbarkeit von Typ-0-Sprachen an einem konkreten Beispiel zu diskutieren, z.B. an der Halteproblematik. Nutzen Sie die Hierarchie-Karten, um zu zeigen, warum niedrigere Typen in der Programmierung bevorzugt werden.

• Während der Automaten-Bauwerkstatt verstehen Schüler kontextfreie Grammatiken als 'ohne Kontext'.

  Lassen Sie die Schüler im Anschluss an die Bauaktivität ein Simulationsspiel durchführen, bei dem sie selbst den Stapel eines Pushdown-Automaten bedienen. Fragen Sie sie, wie der Kontext (der Stapel) die Verarbeitung beeinflusst, und vergleichen Sie dies mit einem endlichen Automaten ohne Stapel.

---

In dieser Übersicht verwendete Methoden

• Gruppenpuzzle