Informatik · Klasse 13

Ideen für aktives Lernen

Nichtdeterministische Endliche Automaten (NFA)

Bei NFAs hilft aktives Entwerfen und Vergleichen, weil die nichtdeterministischen Eigenschaften wie ε-Übergänge und Mehrfachzustände bei passivem Zuhören schwer vorstellbar bleiben. Durch konkrete Modellierung und Simulation erkennen Lernende sofort, wie Kompaktheit und Flexibilität zusammenhängen.

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

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

Aktivität 01

• Kollaboratives Problemlösen
• 25 Min. · Partnerarbeit

Paararbeit: NFA-Entwurf

Paare erhalten eine reguläre Sprache und entwerfen einen NFA mit ε-Übergängen. Sie testen den Automaten mit fünf Eingabestrings und notieren Akzeptanzpfade. Abschließend vergleichen sie mit einem Partnerpaar.

Vergleichen Sie die Ausdrucksstärke von NFAs und DFAs.

Moderationstipp

Bei der Paararbeit zum NFA-Entwurf darauf achten, dass beide Partner ihre Zustandsübergänge mündlich begründen, bevor sie den Automaten zeichnen.

Worauf zu achten ist

Geben Sie den Schülerinnen und Schülern einen kleinen NFA (z. B. mit 3 Zuständen und einem ε-Übergang). Bitten Sie sie, alle möglichen Folgezustände für eine gegebene Eingabesequenz aufzulisten und zu begründen, ob die Sprache akzeptiert wird.

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Beziehungsfähigkeit
• Entscheidungsfähigkeit
• Selbststeuerung

Aktivität 02

• Lernen an Stationen
• 45 Min. · Kleingruppen

Lernen an Stationen: Powerset-Konstruktion

Drei Stationen: NFA analysieren, Zustandsmengen bilden, DFA vervollständigen. Gruppen rotieren alle 10 Minuten, protokollieren Zwischenschritte und diskutieren exponentielles Wachstum.

Erklären Sie den Prozess der Umwandlung eines NFA in einen äquivalenten DFA.

Moderationstipp

Bei der Stationenarbeit zur Powerset-Konstruktion leere Tabellen als visuelle Hilfen anbieten, um die Zustandsmengen systematisch zu erfassen.

Worauf zu achten ist

Stellen Sie die Frage: 'Unter welchen Umständen könnte die Konstruktion eines NFA und dessen anschließende Umwandlung in einen DFA sinnvoller sein als die direkte Konstruktion eines DFAs?' Sammeln Sie die Argumente der Schüler bezüglich Einfachheit der Beschreibung vs. Effizienz der Ausführung.

• Erinnern
• Verstehen
• Anwenden
• Analysieren
• Selbststeuerung
• Beziehungsfähigkeit

Aktivität 03

• Kollaboratives Problemlösen
• 35 Min. · Ganze Klasse

Klassensimulation: NFA vs. DFA

Die Klasse simuliert parallele Pfade eines NFAs mit Karten für Zustände. Jeder Schüler verkörpert einen Pfad, verfolgt Eingaben gemeinsam. Ergebnis: Vergleich der Kompaktheit.

Analysieren Sie, wann der Einsatz eines NFA gegenüber einem DFA vorteilhaft ist.

Moderationstipp

Bei der Klassensimulation von NFA vs. DFA die Schülerinnen und Schüler als Zustände positionieren und durch den Raum laufen lassen, um parallele Pfade erlebbar zu machen.

Worauf zu achten ist

Bitten Sie die Schülerinnen und Schüler, den Prozess der Zustandsmengenkonstruktion in eigenen Worten zu beschreiben und ein Beispiel für eine Sprache zu nennen, für deren NFA-Darstellung die Anzahl der Zustände deutlich geringer ist als im äquivalenten DFA.

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Beziehungsfähigkeit
• Entscheidungsfähigkeit
• Selbststeuerung

Aktivität 04

• Kollaboratives Problemlösen
• 20 Min. · Einzelarbeit

Individuelle Analyse: Vorteile

Schüler listen Szenarien auf, wo NFAs DFAs vorzuziehen sind, z. B. in der Modellierung. Sie skizzieren Beispiele und bewerten Komplexität.

Vergleichen Sie die Ausdrucksstärke von NFAs und DFAs.

Moderationstipp

Bei der individuellen Analyse der Vorteile von NFAs gezielt nach Beispielen fragen, in denen Nichtdeterminismus die Beschreibung vereinfacht, aber die Ausführung nicht erschwert.

Worauf zu achten ist

Geben Sie den Schülerinnen und Schülern einen kleinen NFA (z. B. mit 3 Zuständen und einem ε-Übergang). Bitten Sie sie, alle möglichen Folgezustände für eine gegebene Eingabesequenz aufzulisten und zu begründen, ob die Sprache akzeptiert wird.

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Beziehungsfähigkeit
• Entscheidungsfähigkeit
• Selbststeuerung

Einige Hinweise zum Unterrichten dieser Einheit

Lehrkräfte sollten NFAs als Werkzeug zur Sprachmodellierung einführen, nicht als theoretisches Konstrukt. Der Fokus liegt auf dem Vergleich mit DFAs, um zu zeigen, dass Nichtdeterminismus zwar die Darstellung verändert, aber nicht die Mächtigkeit. Visualisierungen und physische Simulationen helfen, das abstrakte Konzept greifbar zu machen. Wichtig ist, ε-Übergänge und parallele Pfade schrittweise einzuführen, um Überforderung zu vermeiden.

Am Ende können Schülerinnen und Schüler NFAs entwerfen, deren Umwandlung in DFAs nachvollziehen und die Äquivalenz beider Modelle an konkreten Beispielen begründen. Sie erklären zudem, warum NFAs trotz Nichtdeterminismus keine zusätzliche Ausdrucksstärke bieten.

---

Vorsicht vor diesen Fehlvorstellungen

• Während der Paararbeit zum NFA-Entwurf achten Sie darauf, dass Schülerinnen und Schüler nicht annehmen, NFAs könnten Sprachen akzeptieren, die DFAs nicht akzeptieren.

  Fordern Sie die Paare auf, ihre NFA-Entwürfe mit der gleichen Sprache zu testen und die Ergebnisse zu vergleichen. Zeigen Sie dabei, wie dieselbe Eingabe in beiden Modellen akzeptiert oder abgelehnt wird.

• Während der Stationenarbeit zur Powerset-Konstruktion kann die Annahme entstehen, dass die Zustandsanzahl immer exponentiell wächst.

  Bitten Sie die Schülerinnen und Schüler, konkrete Umwandlungen zu dokumentieren und zu vergleichen, bei denen Zustände kollabieren. Diskutieren Sie im Plenum, warum dies bei bestimmten Sprachen möglich ist.

• Während der Klassensimulation von NFA vs. DFA könnte der Eindruck entstehen, dass parallele Pfade die Berechnung unmöglich machen.

  Lassen Sie die Schülerinnen und Schüler mit einer festen Eingabesequenz durch den simulierten NFA laufen und fragen Sie gezielt nach akzeptierenden Pfaden. Zeigen Sie so, dass nur ein einziger akzeptierender Pfad ausreicht.

---

In dieser Übersicht verwendete Methoden

• Kollaboratives Problemlösen
• Lernen an Stationen