Difference between revisions of "Kellerautomat"
(New page: Ein Kellerautomat ist ein endlicher Automat, der um einen Kellerspeicher erweitert wurde. Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur Turingmaschine. ==Komme...) |
|||
| Line 1: | Line 1: | ||
Ein Kellerautomat ist ein endlicher Automat, der um einen [[Kellerspeicher]] erweitert wurde. Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur [[Turingmaschine]]. | Ein Kellerautomat ist ein endlicher Automat, der um einen [[Kellerspeicher]] erweitert wurde. Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur [[Turingmaschine]]. | ||
| − | ==Kommentare== | + | ==Kommentare== |
Die Leistungsfähigkeit [[Endlicher Automat|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 [[Akzeptor]]en 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. | Die Leistungsfähigkeit [[Endlicher Automat|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 [[Akzeptor]]en 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. | ||
{{wb}} | {{wb}} | ||
[[Category:Computerlinguistik]] | [[Category:Computerlinguistik]] | ||
Revision as of 16:20, 21 October 2008
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.
