Kellerautomat - Revision history

NBlöcher: Marked as {{ref}}

2014-07-06T15:40:12Z

Marked as {{ref}}

Haspelmath: boldface

2008-10-23T10:41:07Z

boldface

Okolowski at 16:20, 21 October 2008

2008-10-21T16:20:25Z

Okolowski: 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...

2008-10-21T16:20:13Z

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...

New page

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

==Kommentare== => aus Wikilingua übernommen, kann man das so lassen?
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}}
[[Category:Computerlinguistik]]

← Older revision		Revision as of 10:41, 23 October 2008
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==

@@ Line 4: / Line 4: @@
 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}}{{ref}}
 [[Category:Computerlinguistik]]

@@ 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]].
-==Kommentare==  => aus Wikilingua übernommen, kann man das so lassen?
+==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.
 {{wb}}
 [[Category:Computerlinguistik]]