nur für LK: Kellerautomaten

Endliche Automaten ohne Ausgabe und mit Kellerspeicher - Kellerautomat

Im Baumarkt gibt es einen Automaten, der Schrauben und die passenden 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 also nicht von einem 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).

Funktionsmodell eines Kellerautomaten

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

• ist nach oben offen, also unendlich groß,

• hat das Symbol # zur Anzeige des leeren Kellers.

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 Kellerleerzeichen #
• SOLANGE ein Zustandsübergang möglich ist:
  • Lies mithilfe der Leseköpfe das Zeichen aus der aktuellen Zelle des Eingabeband 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 Kellerleerzeichen 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, die dem aktuellem Zustand in Abhängigkeit vom jeweils aktuellen (ggf. leerem) Eingabezeichen und Kellerzeichen höchstens eine Kelleroperation und einen Folgezustand zuordnet
  • z₀ ∈ Z ist der Anfangszustand
  • k₀ ∈ Γ ist das Kellerleerzeichen (#)
  • Z_E ... Endzustandsmenge (nichtleere, endliche Teilmenge von Z)

Bei einem nichtdeterministischer Kellerautomaten müssen die Zustandsübergänge nicht eindeutig 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: (erwünschtes Kellerzeichen, erwünschtes Eingabezeichen): zu realisierende 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.

ε hat also eine Mehrfachbedeutung: 

• • als Kelleroperation: nichts zurückschreiben
  • als "virtuelles" Eingabezeichen - nichts vom Band lesen

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 die gleiche Eingabe folgt auch immer die gleiche Ausgabe und zusätzlich wird die gleiche Folge an Zuständen durchlaufen. 

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 raten, wo die Mitte ist. Ein Algorithmus oder ein Automat, der eine Lösung rät oder für die gleiche Eingabe bei identischer Startvorgabe verschiedene Lösungen ausgibt, wird nichtdeterministisch genannt. Genau so etwas benötigen wir jetzt. Das System muss alles einkellern und an einer zu ratenden Stelle mit dem Auskellern beginnen. Wenn wir Glück haben, war es die richtige, sonst muss das System eben neu raten. 

So unsinnig uns der Nichtdeterminismus für Computer auch erscheinen mag, er findet trotzdem seine Anwendung in der Welt der Informatik (Randomisierte Algorithmen, Quicksort).