nur für LK: Kellerautomaten

Endliche Automaten ohne Ausgabe und mit Kellerspeicher - Kellerautomat

Im Baumarkt gibt es einen Automaten, der Schrauben und die passende Anzahl Muttern eintütet. Zuerst wird die gewünschte Anzahl der Schrauben mit Mutter erfasst, dann die Schrauben und anschließend die Muttern in die Tüte gegeben. In eine Sprache übersetzt also: L = {Schraubeⁿ Mutterⁿ | n > 0}. Können wir einen Akzeptor konstruieren, der diese Sprache erkennt und akzeptiert?

Ansatz: Für n ≤ 3 liefert der Graph des Akzeptors (ohne Zustandsübergänge in einen Fehlzustand) eine Lösung:

Eine Erweiterung für größere n scheint auf den ersten Blick problemlos möglich, man muss nur neue Zustände einführen. Im allgemeinen Fall würde der Automat aber unendlich viele Zustände besitzen müssen. Dies widerspricht der Definition des Akzeptors. Diese Sprache kann nicht von einem endlichen Akzeptor erkannt werden. Wir benötigen dafür "irgendeinen" Speicher, der sich die Anzahl der Schrauben merken kann.

Kellerautomat – Kellerspeicher

Ein sehr simpler Speicher ist der sog. Kellerspeicher (Stapel, Stack). Wie in einem Keller können Objekte oben abgelegt (push) und von oben entnommen (pop) werden. Dabei gilt: das zuletzt abgelegte Objekt muss als erstes wieder entnommen werden. Dieses Prinzip bezeichnet man mit Last in – First out (LIFO). Dabei sind drei grundlegende Operationen möglich:

• push: ein Zeichen oben auf den Keller legen,
• pop: das oberste Zeichen aus dem Keller entfernen,
• nop: den Kellerinhalt unverändert lassen.

Funktionsmodell eines Kellerautomaten

Der Automat besitzt einen Kellerspeicher zum Ablegen von Objekten. Der Kellerspeicher

• ist nach oben offen, seine Größe ist nicht begrenzt.,

• hat das Symbol # zur Anzeige des Kellerbodens.

Zum Kellerautomaten gehören außerdem eine Steuereinheit und ein Eingabeband, dass die Eingabezeichen enthält, ein nach rechts bewegbarer Lesekopf sowie eine Lampe zur Anzeige des Akzeptierzustandes.

Arbeitsweise

• Initialisierung des Kellerautomaten: Keller ist leer, der Kellerlesekopf steht auf dem Kellerbodenzeichen #
• SOLANGE ein Zustandsübergang möglich ist:
  • Lies mithilfe der Leseköpfe das Zeichen aus der aktuellen Zelle des Eingabebands sowie das oberste Zeichen aus dem Kellerspeicher
  • Führe in Abhängigkeit vom aktuellen Zustand, dem gelesenen Keller- und Bandzeichen eine Kelleroperation aus und wechsle in einen Folgezustand.
  • Bewege das Eingabeband eine Zelle weiter.
• Falls der aktuelle Zustand ein Endzustand ist, das Eingabewort vollständig gelesen wurde und der Keller nur aus dem Kellerbodenzeichen # besteht, dann aktiviere die Akzeptanzanzeige.

Definition des Kellerautomaten

Ein deterministischer Kellerautomat KA = (X, Z, Γ, δ, z₀, k₀, Z_E) ist ein endlicher Automat ohne Ausgabe und mit Kellerspeicher. Dabei gilt:

• • X ... Eingabealphabet (nichtleere, endliche Menge)
  • Z ... Zustandsmenge (nichtleere, endliche Menge)
  • Γ ... Kelleralphabet (nichtleere, endliche Menge)
  • δ ... Überführungsfunktion. Sie legt in Abhängigkeit vom aktuellen Zustand, vom gelesenen Eingabezeichen und vom obersten Kellerzeichen den Folgezustand und die Kelleroperation fest. 
  • z₀ ∈ Z ist der Anfangszustand
  • k₀ ∈ Γ ist das Kellerbodenzeichen (manchmal auch Kellerleerzeichen) (#)
  • Z_E ... Endzustandsmenge (nichtleere, endliche Teilmenge von Z)

Bei einem nichtdeterministischen Kellerautomaten können für dieselbe Situation mehrere Zustandsübergänge möglich sein. Bei deterministischen Kellerautomaten darf für dieselbe Situation höchstens ein Zustandsübergang möglich sein.

Beispiel: Kellerautomat für den Schrauben-Muttern-Automaten

Die akzeptierte Sprache für den Automaten aus dem Eingangsbeispiel ist L = {Schraubeⁿ Mutterⁿ | n > 0}.

Dafür lässt sich ein Kellerautomat KA = (X, Z, Γ, δ, z₀, k₀, Z_E) konstruieren:

• • X = {Schraube, Mutter}
  • Z = {q₀, q₁, q₂}
  • Γ = {#, S}
  • δ als Graph
    
  • q₀
  • k₀ = #
  • Z_E = {q₂}

Die Beschriftung eines Übergangs ist wie folgt aufgebaut: (erwartetes Kellerzeichen, erwartetes Eingabezeichen): Kelleroperation.

• • Die Kelleroperation S# bedeutet dabei, dass das Zeichen S eingekellert werden soll, die Raute - die beim Lesen aus dem Keller entnommen wurde - jedoch davor wieder zurückgeschrieben werden muss.
  • Die Kelleroperation ε bedeutet dabei, dass kein Zeichen zurückgeschrieben werden muss.
  • Die Kelleroperation # bedeutet dabei, dass die Raute - die beim Lesen aus dem Keller entnommen wurde - wieder zurückgeschrieben werden muss.

Der Übergang in den Endzustand q2 sieht eigenartig aus, bedeutet aber:
Wenn der Keller leer ist und kein Zeichen mehr auf dem Band, dann setzte den Keller wieder leer und wechsle und den Endzustand.

Das Symbol ε steht jeweils dafür, dass an dieser Stelle kein Zeichen verwendet wird:

• • als Eingabezeichen: Es wird kein Zeichen vom Eingabeband gelesen.
  • bei der Kelleroperation: Es wird kein Zeichen zurück in den Keller geschrieben.

Determinismus und Nichtdeterminismus

Die Aufgabe mit den Palindromen ist gar nicht so einfach. Unterscheiden wir nach drei Fällen:

1. Palindrom mit Trennzeichen
2. Palindrom ohne Trennzeichen und mit gerader Länge
3. Palindrom ohne Trennzeichen und mit beliebiger Länge

Die Aufgabe 1 ist mithilfe eines Kellerautomaten einfach. Das System muss bis zum Trennzeichen alles einkellern und danach - bei Gleichheit der Zeichen auf dem Band und im Keller - auskellern - fertig. Dies ist bestimmt und deterministisch. Für dieselbe Eingabe ist in jeder Situation eindeutig festgelegt, welcher Zustandsübergang ausgeführt wird. 

In Aufgabe 2 haben wir kein Trennzeichen. Wir wissen also nicht, wo die Mitte ist. Wir können die Mitte auch nicht messen oder auf andere Art und Weise berechnen. Um das Palindrom zu erkennen, müssen wir also berechnen, wo die Mitte ist. Bei einem nichtdeterministischen Automaten können in derselben Situation mehrere Zustandsübergänge möglich sein. Man kann sich dies anschaulich so vorstellen, als würde der Automat mehrere Möglichkeiten ausprobieren. Ein Wort wird akzeptiert, wenn mindestens einer dieser möglichen Wege zu einer erfolgreichen Verarbeitung führt. Genau so etwas benötigen wir jetzt. Das System muss alles einkellern und an einer geeigneten Stelle mit dem Auskellern beginnen. Wenn wir Glück haben, war es die richtige, sonst muss das System eben neu probieren. 

Nichtdeterminismus ist vor allem ein theoretisches Modell. Er erlaubt es, die Leistungsfähigkeit von Automaten und Algorithmen zu untersuchen und unterschiedliche Automatenmodelle miteinander zu vergleichen.