Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Deterministische kontextfreie Sprachen Aufwärts: Kontextfreie Sprachen (CFG) Vorherige Seite: Griebach Normalform   Inhalt

Unterabschnitte

Kellerautomaten

Definition: Nichtdeterministischer Kellerautomat (NKA)

Ein NKA ist ein Tupel

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

bestehend aus
  • endlichen Menge $Q$ 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 $q$ der aktuelle Zustand, $x$ das noch zu bearbeitende Band und $\xi$ der Keller ist, wobei das oberste Kellersymbol ganz links steht und das unterste ganz rechts.

Notation der Übergangsfunktion60:

\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 $S$ auf den Kellerspeicher. Wenn nun $A$ als oberstes Element auf dem Kellerspeicher steht, können wir
  • im Wort einen nach rechts gehen, wenn das aktuelle Zeichen $a$ 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

... Übergangsfunktion60
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.
next up previous contents
Nächste Seite: Deterministische kontextfreie Sprachen Aufwärts: Kontextfreie Sprachen (CFG) Vorherige Seite: Griebach Normalform   Inhalt