s n h m r u
i

Einstieg - Kellerautomat

Ein zusätzlicher Speicher: der Keller

Im vorigen Kapitel haben wir gesehen, dass ein endlicher Automat die Klammersprache (), (()), ((())), … nicht erkennen kann: Er müsste sich beliebig viele offene Klammern merken. Deshalb ergänzen wir ihn um einen Keller. Das ist ein Speicher, in dem Zeichen wie auf einem Stapel liegen. Neue Zeichen werden oben abgelegt; lesen und entfernen lässt sich immer nur das oberste Zeichen. Zu Beginn liegt allein Z im Keller. Es markiert den Kellerboden und bleibt in unserem Beispiel erhalten.

Mit dem Keller die Klammersprache erkennen

Die Idee: Für jede öffnende Klammer legen wir ein Zeichen ab, für jede schließende Klammer entfernen wir eines. So merken wir uns, wie viele Klammern noch geschlossen werden müssen. Zur besseren Lesbarkeit schreiben wir a statt ( und b statt ). Aus (()) wird beispielsweise aabb; die Sprache heißt damit anbn mit n ≥ 1.

Probiere es aus: Für jedes gelesene a legst du ein a im Keller ab, für jedes b entfernst du das oberste a. Nach dem ersten b darf kein a mehr folgen. Sind alle Zeichen gelesen und liegt nur noch Z im Keller, sind die Anzahlen ausgeglichen.

Wähle die jeweils passende Aktion aus.

Von der Stapelübung zum Kellerautomaten

Mit dieser Vorübung lässt sich die Funktionsweise eines Kellerautomaten gut nachvollziehen: Im Keller speichert er, wie viele a noch durch b ausgeglichen werden müssen. Sein aktueller Zustand gibt an, in welcher Phase der Verarbeitung er sich befindet: Z0 für das Ablegen und Z1 für das Entfernen. Z2 ist der Endzustand. Zustandsnamen wie Z0 sind dabei etwas anderes als das Kellersymbol Z.

Eine Beschriftung wie a|Z→Za bedeutet: Lies ein a, entferne das oberste Z und lege zuerst Z, dann a ab. So kommt ein a im Keller hinzu. Bei b|a→ wird das oberste a aus dem Keller entfernt und nichts abgelegt.

Erkunde den Automaten

  1. Teste aaabbb schrittweise. Vergleiche Zustand und Keller mit der Stapelübung. Wie viele b werden nach den drei a noch erwartet?
  2. Untersuche aaabb, aabbb und abab. Erkläre, warum es bei jedem Wort einen anderen Grund für die Ablehnung gibt.
  3. Wenn die Eingabe aufgebraucht ist, folgt beim passenden Wort noch ein Übergang nach Z2. Beobachte, ob dabei ein Eingabezeichen gelesen oder der Keller verändert wird. Die Beschriftung ε|Z→Z bedeutet: kein Eingabezeichen lesen, Z entfernen und wieder ablegen.
  4. Formuliere in eigenen Worten: Was speichert der Keller, was speichern die Zustände und wann wird ein Wort akzeptiert?

Suche

v
100.130.2.3.3.1 Einstieg - Kellerautomat
Kopieren durch Anklicken

Rückmeldung geben