Datenverarbeitende Systeme
Kapitel 5: Kellerautomaten

5.1 Was ist ein Kellerautomat?

Ein Kellerautomat ist eine erste besondere Form von Automaten. Kellerautomaten haben eine internen Zwischenspeicher, auf dem sie Informationen auslagern (einkellern) können. Der Speicher ist so organisiert, das er von unten her nach oben beschrieben wird und in der selben Reihenfolge (von oben nach unten) wieder gelesen. Die Definition sagt aus, das jeweils ein Eingabesymbol mit dem obersten Symbol im Keller und gibt daraufhin ein oder mehrere Zeichen auf dem Keller aus oder löscht das oberste Kellersymbol.

Folgende Kombinationen sind möglich:
(a, b)/a // Wenn a die Eingabe und b das Symbol im Keller ist, überschreibe das b mit einem a
(a, b)/@ // Wenn a die Eingabe und b das Symbol im Keller ist, lösche das b aus dem Keller
(a, b)/ba // Wenn a die Eingabe und b das Symbol im Keller ist, belasse das b im Keller und füge ein a hinzu

Das @ steht hier für das Formal gemeinte Epsilon, ich will nur nicht ständig ein Bild dafür einfügen.

Definition: Zu Beginn enthält der Keller immer das Symbol k0, das vorher festgelegt wird und nicht im Eingabe- oder Kelleralphabet enthalten ist. Der Kellerautomat bleibt stehen (terminiert), wenn es von einem Zustand aus für die aktuelle Kombination aus Eingabe- und Kellersymbol keine Kante gibt (abbruch) oder wenn Eingabe- und Kellerband leer sind (Wort erkannt). Ausnahme: Es gibt auch Kellerautomaten, die mit Endezustand erkennen. Sie sind fertig, wenn der Automat in einem bestimmten Endezustand gelangt und die Eingabe beendet ist. Der Regelfall sind jedoch Automaten, die mit leerem Keller erkennen.

Definiton: Ein Kellerautomat KA=(X, K, k0, S, s0, d, F) besteht aus:

Beispiel: Erkennen der Sprache aⁿbⁿ

Wir können mit Hilfedes Pumping Lemmas nachweisen, das diese Sprache nicht regulär ist und deshalb nicht von einem endlichen Automaten erkannt werden kann. Das liegt daran, dass für den Automaten nicht entscheidbar ist, wieviele a er gelesen hat und deshalb kann er nicht entscheiden, wieviele b das Wort enthalten muss. Der Kellerautomat jedoch kann sehr wohl feststellen, wieviele b kommen müssen, schließlich kann er ja vorher alle a in den Keller schreiben und dann je ein a mit einem b wegstreichen. Das sieht dann so aus:

Wann hat ein Kellerautomat ein Wort erkannt? / Wann terminiert ein KA?

Ein Kellerautomat hat ein Wort erkannt, wenn:

1. Ein Endezustand s_e aus F erreicht wurde Falls F nicht die leere Menge ist
2. Die Eingabe beendet ist und das Kellerband leer ist. Es kann allerdings dann noch Zustandsübergangsfunktionen geben, die mit leerer Eingabe den Keller „aufräumen“ (Das Kellerband muss nicht zeitgleich zum Eingabeende geleert sein!)

Ein Kellerautomat terminiert auch dann, wenn es von einem Zustand aus für die aktuelle Kombination aus Eingabesymbol und oberstem Kellersymbol keine Zustandsübergangsfunktion gibt. Das Wort gilt dann als nicht erkannt. Ein Kellerautomat muss nicht zwangsweise terminieren. Er ist nicht endlich!

5.2 Kellerautomaten und kontextfreie Sprachen

Die Klasse der durch Kellerautomaten darstellbaren Sprachen ist gleich der Klasse der kontextfreien Sprachen. Dies entspricht Grammatiken vom Typ 2 der Chromsky-Hirarchie. Sprachen niedrigeren Typs (0 oder 1) können nicht von Kellerautomaten erkannt werden.

Daraus ergibt sich, das jede kontextfreie Sprache von einem Kellerautomaten erkannt wird. Umgekehrt ist jede Sprache kontextfrei, die von einem Kellerautomaten erkannt werden kann.