Skip to main content
Unterrichtsentwürfe
Wie funktionieren Kellerautomaten?
Icon text page.png
Wie funktionieren Kellerautomaten?
Themenbereiche Hat Schlagwort::Automaten
Schulformen Gymnasium, Gesamtschule
Länge Einzelstunde
Jgst Sek. II
Autor Annika Bölte
Schlagwörter Kellerautomaten, Theoretische Informatik
Lizenz CC-BY-NC-SA-icon-88x31.png


Beschreibung

Die Verfasserin entwickelt ein Unterrichtskonzept, das über problemlösendes und handlungsorientiertes Lernen Einsichten in die Arbeitsweise von Kellerautomaten ermöglicht. Dabei werden Verfahren der Simulation und des Rollenspiels sowie eines induktiven Aufbaus des Lernarrangements verknüft mit kooperativen Methoden.

Der Unterrichtsentwurf ist auf den Seiten des Lernzentrum für Schulpraktische Lehrerausbildung Paderborn frei zugänglich. (Update 03.11.2015: Die Seiten des ZfsL Paderborn sind nicht mehr verfügbar.)

Übersicht

Stundenziel

Die SuS sollen das Konzept der Kellerautomaten auf verschiedenen Abstraktionsebenen beschreiben können, indem sie einen Kellerautomaten mit verteilten Rollen simulieren, seine Arbeitsweise bildlich festhalten und schließlich seinen Zustandsgraph konstruieren.

Inhaltliche Teilziele

Die SuS sollen...

  • die Unzulänglichkeit von endlichen Automaten für bestimmte Sprachen einsehen können
  • die Arbeitsweise eines Kellerautomaten simulieren und beschreiben sowie bildlich und symbolisch darstellen können
  • zu einer einfachen kontextfreien Sprache einen Kellerautomaten konstruieren können, der diese Sprache erkennt

Prozessbezogene Teilziele

Die SuS sollen...

  • effektiv in der Gruppe zusammenarbeiten können, indem sie sich auf der Grundlage von festen Regeln auf eine gemeinsame Strategie einigen
  • Problemlösendes Arbeiten anwenden können, indem sie ihre Lösungsideen auf ihre Tragfähigkeit testen
  • vom Rollenspiel abstrahieren können
  • mit formalen Definitionen umgehen können

Einbettung in die Unterrichtsreihe

In der theoretischen Informatik sucht man nach abstrakten Modellen, die unabhängig von der konkreten Implementierung die wesentlichen Aspekte eines Computers erfassen. Der Einstieg in dieses Thema erfolgte über die Automatentheorie in Anlehnung an Analysen und Beschrei- bungen von realen Automaten wie einem Parkschein- oder Geldwechselautomat. Diese Über- legungen führten zum Modell des Mealy-Automaten, dessen Ausgabe von seinem Zustand und seiner Eingabe abhängt. Als weitere Abstraktion dieses Modells wurden die erkennenden endlichen Automaten eingeführt, die bestimmte Eingaben erkennen und akzeptieren und durch ihren Zustand (anstatt durch eine Ausgabe) das Ergebnis nach außen signalisieren. Die Ausgabe dieser Automaten ist also auf „ja“ oder „nein“ beschränkt. Die Theorie der erkennenden endlichen Automaten führt direkt zu Betrachtungen von formalen Sprachen, die von Au- tomaten erkannt werden können. Die SuS haben zu verschiedensten formalen Sprachen er- kennende endliche Automaten konstruiert und so z.B. eine Mustererkennung in Texten beschrieben.

Die Worte, die von endlichen Automaten erkannt werden können, sind jedoch sehr einfach strukturiert. Nur Sprachen, die keine beliebig tief verschachtelten Strukturen enthalten, können von endlichen Automaten erkannt werden. Somit übersteigt z.B. bereits die Analyse arithmetischer Terme, insbesondere verschachtelter Klammern die Fähigkeiten endlicher Automaten. 

Stunde Thema Bemerkungen
1/2 Einstieg: Was können Computer? -
3 Mealy-Automaten als Abstraktion einfacher Automaten aus dem Alltag -
4/5 Erkennende endliche Automaten -
5/6 Wie baut man einen Automaten? – Konstruktionsstrategien mit dem Exorciser entwickeln -
6 Automaten zur Mustererkennung in Texten (Expertenrunde zur HA) -
7/8 Nichtdeterministische endliche Automaten -
9 Was können endliche Automaten nicht? – Einstieg in Kellerautomaten -
10/11 Kellerautomaten und Sprachhierarchien – Was unterscheidet die Sprachen von EA und PDAs? -

Didaktisch-methodischer Kommentar

Orientiert am Verlauf der Stunde werden im Folgenden die wesentlichen didaktischen und methodischen Entscheidungen erläutert und begründet.

1. Problemaufwurf

Als Kontext für den Einstieg dient die syntaktische Analyse beim Übersetzen von Programmcode in Maschinensprache. Jedes Programm wird durch einen Compiler auf lexikalische, syntaktische und semantische Korrektheit geprüft, bevor es übersetzt und schließlich ausgeführt werden kann. Die SuS kennen aus ihren bisherigen Programmiererfahrungen sehr gut die Fehlermeldungen, die erscheinen, wenn beim Programmieren z.B. eine Klammer vergessen wurde. Für das Problem, korrekte von falschen Klammersetzungen in einem Programm zu unterscheiden, muss es also einen Algorithmus geben. Die Frage ist nun, ob das bisherige Modell der endlichen Automaten zur Lösung dieses Problems ausreicht.

Um das Problem effizient bearbeiten zu können, wird es zunächst auf seine wesentlichen As- pekte reduziert. So ist erstens jeglicher Text, der außer der Klammern im Programm vor- kommt, für die syntaktische Analyse der korrekten Klammerung irrelevant und kann somit weggelassen werden. Des Weiteren sollen zunächst nur einfache Schachtelungen beliebiger Tiefe berücksichtigt werden, also z.B. {{{}}} aber keine Konstrukte wie {{}{}}. Natürlich kommen auch letztgenannte Fälle in Programmen vor; sie sollen im späteren Verlauf der Rei- he mit einbezogen werden. Drittens halte ich es für sinnvoll, die etwas unhandlichen und beim Lesen schwer zu unterscheidenden Klammern durch Buchstaben zu ersetzen. Alternativ hätten diese Reduktionen und Eingrenzungen des Problems auch die SuS selbst vornehmen können. Abgesehen davon, dass ein solches Vorgehen viel Zeit und eine hohe Selbstständigkeit der SuS vorausgesetzt hätte, wäre ein weiteres Problem dadurch entstanden, dass verschiedene Arbeitsgruppen möglicherweise ganz unterschiedliche Reduktionen vorgenommen hätten, so dass eine Vergleichbarkeit der Lösungen nicht mehr gewährleistet gewesen wäre. Das Problem in seiner vollen Komplexität würde viele SuS dieses Grundkurses überfordern und vom Wesentlichen des Problems ablenken. Um den Fokus statt dessen zielsicher auf das neue Automatenmodell zu lenken, geschieht diese Vorstrukturierung des Problems in einem kurzen Lehrervortrag.

Der Versuch einer Lösung des Problems mit dem bekannten Modell der endlichen Automaten führt in die Irre und motiviert die Notwendigkeit einer Erweiterung des Modells.

2. Entwicklung und Simulation eines geeigneten Kellerautomaten

Das wesentliche Problem bei der Planung der Stunde besteht darin, die Arbeitsweise eines Kellerautomaten für die SuS greifbar und verständlich zu machen. Die Definition eines Kellerautomaten ist sehr eng; bereits kleine Änderungen in der Funktionsweise (beispielsweise wenn zugelassen wird, dass der Lesekopf nicht nur nach rechts, sondern auch nach links wandern oder wenn auf dem Eingabeband nicht nur gelesen sondern auch geschrieben werden darf) eröffnen weitere Möglichkeiten und erweitern die Menge der erkannten Sprachen enorm. Da aber im Laufe der Reihe gerade auf die Unterschiede der verschiedenen Automa- tenmodelle und ihre zugehörigen Sprachklassen eingegangen werden soll (Chomsky-Hierarchie), ist eine präzise Definition des Kellerautomaten unabdingbar. Die Definition kann also nicht von den SuS selbst erarbeitet oder erschlossen werden.

Anstatt die SuS jedoch von Beginn an mit der recht abstrakten Definition eines Kellerautomaten zu konfrontieren, sollen Sie zunächst auf handelnde Art und Weise die Arbeitsweise durchspielen. Das Rollenspiel ist so konzipiert, dass die Definition des Kellerautomaten in den (Spiel-)Regeln der einzelnen Rollenträger versteckt ist. Aus diesem Grund ist es absolut not- wendig, dass sich die SuS exakt an die gegebenen Regeln halten. Durch die Rolleneinteilung soll den SuS deutlich werden, von welchen Bestandteilen Informationen gelesen werden müs- sen (Eingabeband, Keller, Steuereinheit) und welche Bestandteile nach jedem Schritt verän- dert werden können (Keller, Steuereinheit). Damit ist die Grundstruktur der Übergangsfunktion eines Kellerautomaten erschlossen.

Diese Erarbeitungsphase setzt vor Allem auf enaktive und ikonische Darstellungsformen. Die SuS simulieren einen Kellerautomaten durch eigene Handlungen, während der Protokollant die Schritte in einer ikonischen Darstellung festhält. Erst später (in der Transferphase) soll zur symbolischen Darstellung des Kellerautomaten in Form eines Zustandsgraphen übergegan- gen werden (Dieses Vorgehen orientiert sich an dem E-I-S Prinzip nach BRUNER). Der Wechsel der Darstellungsformen stellt auch eine innere Differenzierung dar, da das Abstraktionsvermögen der Lernenden unterschiedlich stark ausgeprägt ist. Schwierigkeiten in dieser Phase könnten dadurch entstehen, dass zwei Aspekte durch die SuS erarbeitet werden müssen. Zum Einen müssen Sie die grundsätzliche Funktionsweise eines Kellerautomaten verstehen. Zum Anderen sollen Sie eine Strategie zur Erkennung korrekter Klammerungen entwickeln. Gruppen, die keine Idee für eine solche Strategie finden können, möchte ich mit einer Hilfekarte unterstützen, so dass sie den Kellerautomaten trotzdem durchspielen, seine Arbeitsweise verstehen und somit das Hauptlernziel erreichen können.

3. Sicherung

In der Sicherungsphase sollen Erkenntnisse, die im Rollenspiel implizit erlangt wurden, noch einmal für alle explizit gemacht und auf den Punkt gebracht werden. So haben die SuS beispielsweise die Übergangsfunktion des Kellerautomaten durch ihre Handlungen ausgeführt, indem sie sich in jedem Durchlauf das aktuelle Eingabezeichen, das oberste Kellerzeichen und den Zustand der Steuereinheit angeschaut haben und auf dieser Grundlage entschieden haben, welche Operation auf dem Keller ausgeführt werden und ob die Steuereinheit ihren Zustand wechseln soll. Sie haben also eine Funktion der Form (Eingabezeichen, Kellerzeichen, Zustand) → (Kelleroperation, Zustand) ausgeführt. Diese Übergangsfunktion wird an der Tafel festgehalten, da sie die Arbeitsweise eines Kellerautomaten auszeichnet, insbesondere auch in Abgrenzung zur bereits bekannten Übergangsfunktion eines endlichen Automaten.

In einem zweiten Schritt wird in dieser Phase auch die Lösung der Klammererkennung vorgestellt und diskutiert, so dass die SuS alle die nötigen Voraussetzungen erlangen, um die Hausaufgabe bearbeiten zu können.

Verlaufsplan

Zeit Phase Arbeitsschritte Sozial-/
Aktionsform
Medien /
Material
Bemerkungen
Stundenziel: Die SuS sollen das Konzept der Kellerautomaten auf verschiedenen Abstraktionsebenen beschreiben können, indem sie einen Kellerautomaten mit verteilten Rollen simulieren, seine Arbeitsweise bildlich festhalten und schließlich seinen Zustandsgraph konstruieren.
5 min Einsteig Compiler muss Klammerlogik erkennen können (syntaktische Analyse). Kann dies ein endlicher Automat leisten?

Problem: Der Automat muss sich merken, wie viele öffnende Klammern schon vorkamen. Reduktion des Problems auf das Erkennen von Worten der Form anbn.

LV Beamer Einbettung in einen bekannten Kontext

Das Problem wird reduziert, um effizient weiterarbeiten zu können.

10 min Problemaufwurf Konstruktion der endlichen Automaten.

Das bisherige Automatenmodell reicht nicht aus; man bräuchte unendlich viele Zustände. Lösung: zusätzlicher Speicher

PA
SV
UG
AB
Tool:JFlap
Die Automaten werden am Rechner konstruiert, da dann die Präsentation flexibler gestaltet werden kann, z. B. können die Automaten mit JFlap direkt getestet oder angepasst werden.
10 min Erarbeitung Funktionsweise von Kellerautomaten

Entwickeln einer Strategie für einen Kellerautomaten, der die Klammersprache akzeptiert sowie Simulation dieses Automaten (Rollenspiel).

GA AB Enaktive und ikonische Darstellungsformen stehen beim Rollenspiel im Vordergrund.
10 min Sicherung Präsentation der Arbeitsweise des Kellerautomaten Festhalten der wesentlichen Aspekte eines Kellerautomaten: Jede Aktion ist abhängig von

Eingabezeichen Zeichen auf dem Keller Zustand Es können verändert werden: Zeichen auf dem Keller (push, pop) Zustand Damit ist die Übergangsfunktion definiert.

SV
UG
Folie
Tafel
Im Rollenspiel implizit gemachte Erkenntnisse werden im UG noch einmal für alle explizit gemacht und auf den Punkt gebracht.
10 min Transfer Informationsblatt mit formaler Definition

Kellerautomat zur Erkennung korrekter Klammerungen formal beschreiben

PA
EA
AB Die formale Definition des Kellerautomaten stellt die höchste Abstraktionsstufe dar.

Diese Phase wird ggf. in die Hausaufgabe ausgelagert.

Hausaufgabe: keine

Links