Kellerautomaten ::: Theoretische Informatik

Ein NKA ist ein Tupel

$\begin{displaymath}K=(Q,\Sigma,\Gamma,\delta,q_{0},\char93 ,F)\end{displaymath}$

bestehend aus

endlichen Menge von Zuständen
Eingabealphabeth $\Sigma$
Kelleralphabet $\Gamma$
Anfangszustand $q_{0}\in Q$
Kellerstartsymbol $\char93$ (unterstes Kellerzeichen)
Menge $F\subseteq Q$ von Endzuständen
Übergangsfunktion $\delta$

Konfiguration, Notation der Übergangsfunktion und Konfigurationswechsel

Konfiguration:
Eine Konfiguration hat die Form

$\begin{displaymath}K=(q,x,\xi)\end{displaymath}$

wobei

der aktuelle Zustand,

das noch zu bearbeitende Band und $\xi$ der Keller ist, wobei das oberste Kellersymbol ganz links steht und das unterste ganz rechts.

Notation der Übergangsfunktion⁶⁰:

$\begin{displaymath}\delta(q_{aktuell},x_{erstes},\xi_{oberstes})=\{(q_{neu\,1},\xi_{neu\,1}),\ldots, (q_{neu\,n},\xi_{neu\,n})\}\end{displaymath}$

Bei einem NKA kann in mehrere Folgezustände und/oder Belegungen des Stacks überführt werden, bei DKAs ist es immer nur einer. Leider kann man die Übergangsfunktion und damit den ganzen Automaten nicht mehr zeichnen wie bei DFAs oder NFAs.

Konfigurationswechsel z.B.:

$\begin{displaymath}(q_{1},aaa,\char93 )\vdash(q_{2},aa,a\char93 )\vdash^{*}(q_{F},\epsilon,\epsilon)\end{displaymath}$

Genaueres über die Akzeptanz siehe unten.

Akzeptanzverhalten

Wir haben bei Kellerautomaten zwei Möglichkeiten für die Akzeptanz:

Akzeptanz durch Endzustände:
Nach dem Lesen des kompletten Eingabewortes wird akzeptiert, wenn ein Endzustand erreicht ist. Der Kellerinhalt ist hierbei egal.

Die durch die Endzustände akzeptierte Sprache ist

$\begin{displaymath}L(K)=\{w\in\Sigma^{*}:(q_{0},w,\char93 )\vdash^{*}(q,\epsilon,\xi)\,f\uml {u}r\,beliebiges\,\xi\,und\,q\in F\}\end{displaymath}$

Akzeptanz durch leeren Keller:
Nach dem Lesen des kompletten Eingabewortes wird akzeptiert, wenn der Keller leer ist. Es gibt bei dieser Akzeptanzform keine Endzustände.

Die durch den leeren Keller akzeptierte Sprache ist

$\begin{displaymath}L(K)=\{w\in\Sigma^{*}:(q_{0},w,\char93 )\vdash^{*}(q,\epsilon,\epsilon)\,f\uml {u}r\,ein\,beliebiges\,q\in Q\}\end{displaymath}$

Akzeptanz durch Endzustand $\rightarrow$ Akzeptanz durch leeren Keller

Wir fügen von jedem ehemaligen Endzustand eine Übergangsfunktion mit $\epsilon$ -Übergang zu dem Zustand $q_{leeren}$ ein. Im Zustand $q_{leeren}$ leeren wir den Keller vollständig und akzeptieren somit. Es kann sein, daß der Keller einmal während der Berechnung leer wird und wir sozusagen ausversehen akzeptieren. Deshalb fügen wir ein Kellersymbol $\bot$ an die unterste Position des Kellers ein. Dieses entfernen wir erst, wenn wir in den Zustand $q_{leeren}$ kommen. Wir benötigen dazu noch einen anderen Startzustand des NKAs, damit $\bot$ zuerst in den Keller gelegt wird und dann erst die Berechnung gestartet wird.

Akzeptanz durch leeren Keller $\rightarrow$ Akzeptanz durch Endzustand

Wieder führen wir ein Symbol $\bot$ ein, welches ganz unten auf dem Stack liegt, um zu verhindern, daß der Automat vorzeitig verwirft, obwohl er eigentlich akzeptieren soll, damit wir noch die Möglichkeit haben, in einen Endzustand zu überführen. Sobald wir nun in eine Konfiguration $(q,\epsilon,\bot)$ geraten, überführen wir in einen Zustand $q_{F}$ der Endzustand ist. Zuvor entfernen wir dann auch wieder $\bot$ .

Kontextfreie Grammatik $\rightarrow$ NKA

Die Grammatik muß in Greibach-Normalform vorliegen. Die Regeln sind dann der Art: $A\rightarrow aB_{1}B_{2}\ldots B_{n}$ . Zu Beginn steht schieben wir das Startsymbol

auf den Kellerspeicher. Wenn nun

als oberstes Element auf dem Kellerspeicher steht, können wir

im Wort einen nach rechts gehen, wenn das aktuelle Zeichen ist (ansonsten verwerfen wir)
und dann $B_{1}B_{2}\ldots B_{n}$ auf den Keller schieben, so daß $B_{1}$ oben steht.

Für eine solche NKA benötigen wir nur einen Zustand, der zugleich Endzustand ist, und nehmen die Verschiebungen auf dem Stack mit $\epsilon$ -Moves vor. Wir akzeptieren bei leerem Keller.

NKA $\rightarrow$ kontextfreie Grammatik

Eine NKA und eine kontextfreie Grammatik in beiden Richtungen überführbar und somit äquivalent.

NKAs mit zwei Kellern

NKAs mit zwei Kellern haben die Mächtigkeit von Turingmaschinen, da man mit einer Registermaschine mit zwei Kellern eine Turingmaschine simulieren kann. Man kann sich klar machen, daß dies auch für NKAs funktioniert, so daß NKAs eine Turingmaschine simulieren können.

reguläre Sprache $\cap$ kontextfreie Sprache = kontextfreie Sprache

Ist $L_{1}$ eine reguläre Sprache und $L_{2}$ eine kontextfreie Sprache, so ist $L_{1}\cap L_{2}$ kontextfrei.
Wir können uns vorstellen, daß das Produkt eines NKAs mit einem DFA maximal ein NKA sein wird. Wir haben auch hierfür keinen Beweis gemacht.

Fußnoten

... Übergangsfunktion ⁶⁰: Das oberste Kellerelement wird immer gepoppt. Will man es auf dem Stack liegen lassen, muß man es wieder pushen. Hier kann nun $\epsilon$ stehen, wenn es entfernt werden soll.

Griebach Normalform Kontextfreie Sprachen (CFG) Deterministische kontextfreie Sprachen

Ψ Die Informatikseite