Kellerautomat

Ein Kellerautomat ist ein endlicher Automat, der um einen Kellerspeicher erweitert wurde. Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur Turingmaschine.

Kommentare

Die Leistungsfähigkeit Endlicher Automaten hat Grenzen: Es fehlt ein Gedächtnis, um sich beliebig tief geschachtelte Konstruktionen zu merken. Sprachen mit derartigen geschachtelten Strukturen sind kontextfrei und können demnach mit Akzeptoren nicht erkannt werden. Aufgabe des Kellerautomaten ist es, den Anfang und das Ende von geschachtelten Konstruktionen zu erkennen. Dazu braucht er ein Gedächtnis. Als Gedächtnis dient dem Automat ein Kellerspeicher oder Stapel (stack). Ausgehend vom Startzustand endet der Automat nach endlich vielen Schritten entweder im Endzustand oder nicht. In Abhängigkeit vom Eingabezeichen, vom aktuellen Zustand und vom obersten Kellersymbol wird ein Zustandswechsel ausgelöst und die Kellerspitze verändert. Im Keller können beliebig viele Symbole abgelegt werden. Im Kellerspeicher kann aber nur das oberste Zeichen verändert werden. Es stehen dafür drei Speicheroperationen zur Verfügung: Push (legt ein Zeichen zuoberst in den Speicher), Pop (entfernt das oberste Kellerzeichen) und # (ändert den Keller nicht). Es gilt somit das Prinzip: Last In First Out (LIFO). Das neue Zeichen wird zuoberst in den Speicher gelegt. Es können in einem Schritt auch mehrere Zeichen hinterlegt werden. Das zuletzt hinterlegte Zeichen wird wieder zuerst entfernt.