Kellerautomat

Formal definiert man einen Kellerautomaten als 7-Tupel (Q,S,K,δ,q₀,#,F):

-        Q ist eine nicht leere, endliche Menge von Zuständen

-        S ist ein nicht leeres, endliches Eingabealphabet.

-        K ist ein nicht leeres, endliches Kelleralphabet

-        dist die Übergangsfunktion, die jeder Kombination aus einem Zustand, einem Eingabezeichen und einem Kellerzeichen einen Nachfolgezustand und eine Kelleroperation zuordnet

-        q₀ ϵ Q ist der Startzustand

-        # ϵ K ist das Anfangssymbol im Keller

-        F ist die Menge der akzeptierenden Endzustände, wobei F eine Teilmenge von Q ist

Der im Beispiel erläuterte Kellerautomat für die Sprache L = {aⁿbⁿ|n ϵ N} lässt sich somit wie folgt formal definieren.

-        Q = {z₀,z₁,z₂}

-        S={a,b}

-        K = {#,A}

-        F = {z₂}

-        -d

Alter Zustand	Gelesene Eingabe	Oberstes Kellerzeichen	Neuer Zustand	Kelleroperation
z0	A	#	z0	Push(A)	1.Regel
z0	a	A	z0	Push(A)	2.Regel
z0	b	A	Z1	Pop()	3.Regel
Z1	b	A	Z1	Pop()	4.Regel
Z1	ϵ	#	Z2	Pop()	5.Regel

Alle nicht aufgeführten Übergänge, z.B. wenn zu Beginn ein b eingelesen wird, führen in einen Fehlerzustand und werden aus Gründen der Übersichtlichkeit weggelassen. 

Fazit

Der Kellerautomat kann aufgrund seines Speichers Wörter mit einer komplexeren Struktur erkennen als ein deterministischer endlicher Automat. So ist die Fähigkeit passende Klammerpaare erkennen zu können von großer Bedeutung, um mathematische Terme zu erkennen. Doch auch dem Kellerautomaten sind Grenzen gesetzt. Zwar kann der Kellerautomat für Wörter der Form aⁿ b^b sich die Anzahl der a merken, aber für Wörter, für der der Automat sich die gleiche Anzahl drei verschiedener Buchstaben (a,b,c) merken müsste, würde der Kellerspeicher nicht genügen. Ein Kellerautomat kann zwar die Anzahl der a speichern und sie mit den folgenden b vergleichen, aber die Anzahl der a steht für weitere Berechnungen nicht mehr zu Verfügung, da der Keller geller wurde.

Sprachen der Form L = {aⁿ,bⁿ,cⁿ | n > 0} können von einem Kellerautomaten nicht erkannt werden. Um das zu bewerkstelligen, müsste man die Einschränkungen des Kellerautomaten aufheben. Das Modell müsste es erlauben, sich auf der Eingabe in beide Richtungen zu bewegen und der Zugriff auf den Speicher dürfte sich nicht nur auf das erste Element beschränken.