Theoretische Informatik

Theorem 5.2.1 Zu jeder kontextfreien Grammatik

G = (Σ, N, S, P)

gibt es einen Kellerautomaten

M = (Σ, Q, Γ, q_{s t a r t}, δ)

, der die gleiche Sprache akzeptiert, also

L (G) = L (M)

.

Beweis. Der Beweis ist vergleichsweise einfach, weil wir die Grammatik eins zu eins in Automatentransitionen übersetzen können. Die Idee ist, dass die Symbole auf dem Stack, von unten nach oben gelesen, zu jedem Zeitpunkt eine Wortform bilden, aus der der noch nicht gelesene Teil des Restwortes ableitbar ist. Wenn oben auf dem Stack also ein Terminalsymbol

x

liegt und

x

auch das nächste Inputzeichen ist, dann poppen wir

x

vom Stack und lesen

x

, d.h. schieben den Lesekopf um ein Zeichen nach rechts; der Stack ist von

x α

auf

α

geschruft und das Restwort von

x w

auf

w

; wenn also

x α \Rightarrow^{*} x w

galt, so gilt nun immer noch

α \Rightarrow^{*} w

. Wenn ein Nichtterminal

X

oben auf dem Stack liegt, dieser also die Form

X α

hat, und

w

das Restwort ist, dann gilt also

X α \Rightarrow^{*} w

. Der Automat rät nun nichtdeterministisch die erste in der Ableitung angewandte Produktion

X \to β

, löscht

X

vom Stack und pusht

β

. Der Stack ist nun

β α

, und

β α \Rightarrow^{*} w

. Entscheidend ist der Nichtdeterminismus: es gibt eine korrekte Produktion

X \to β

, die schlussendlich zu

w

führt; der Automat kann also diese Transition anwenden.
Formaler: Die Zustände des Automaten sind

Q = {q_{s t a r t}, q_{1}, q_{e n d}}

, das Stackalphabet ist

Γ = Σ \cup N \cup {$}

und die Transitionsregeln sind

\begin{aligned} (q_{1}, x) & \overset{x}{\to} (q_{1}, ϵ) für jedes x \in Σ \\ (q_{1}, A) & \overset{ϵ}{\to} (q_{1}, β) für jede Produktion A \to β \\ (q_{s t a r t}, ϵ) & \overset{ϵ}{\to} (q_{1}, S $) \\ (q_{1}, $) & \overset{ϵ}{\to} (q_{e n d}, ϵ) \end{aligned}

Auf einen formalen Beweis, dass

L (M) = L (G)

ist, verzichte ich an dieser Stelle. Besser als Sipser in seinem Lehrbuch Introduction to the Theory of Computing könnte ich das eh nicht.

◻

Beispiel 5.2.2 Betrachten wir die Grammatik

\begin{aligned} S & \to A | B | C | ϵ \\ A & \to {B} S \\ B & \to [C] S \\ C & \to (A) S | () S \end{aligned}

Ein Wort in der erzeugten Sprache wäre zum Beispiel {[()()]()}()

Schreiben wir nun einen Kellerautomaten, der diese Sprache akzeptiert. Die Idee ist, dass wir Terminalsymbole und Nichtterminalsymbole auf den Stack legen. Ein [ oben auf dem Stack bedeutet dann ich will jetzt sofort ein [ lesen; ein Nichtterminal wie $A$ oben auf dem Stack bedeutet, dass wir als nächstes ein von $A$ ableitbares Wort, also ein $A \to w \in Σ^{*}$ lesen wollen. Um ein $w$ mit $A \to w$ lesen zu können, müssen wir sofort ein { lesen, dann ein Wort $v$ mit $B \to v$ , dann ein } und so weiter. Wir können das also im Automaten implementieren, indem wir $A$ vom Stack löschen und durch ${B} S$ auf den Stack legen, mit dem linkesten Symbol zuoberst. Wenn wir für ein Nichtterminal mehrere Regeln haben, also z.B. $X \to α$ und $X \to β$ , dann können ein $X$ auf dem Stack sowohl durch $α$ als auch durch $β$ ersetzen. Hierfür benötigen wir den Nichtdeterminismus. Beachten Sie, dass wir ein Nichtterminal grundsätzlich immer durch die entsprechende rechte Seite ersetzen können, egal, was das nächste Zeichen ist; es wird im Automaten also ein $\overset{ϵ}{\to}$ -Übergang sein.

Konkret also bauen wir für obige Grammatik die folgenden Automatentransitionen:

\begin{aligned} (q_{1}, S) & \overset{ϵ}{\to} (q_{1}, A) \\ (q_{1}, S) & \overset{ϵ}{\to} (q_{1}, B) \\ (q_{1}, S) & \overset{ϵ}{\to} (q_{1}, C) \\ (q_{1}, S) & \overset{ϵ}{\to} (q_{1}, ϵ) \\ (q_{1}, A) & \overset{ϵ}{\to} (q_{1}, {B} S) \\ (q_{1}, B) & \overset{ϵ}{\to} (q_{1}, [C] S) \\ (q_{1}, C) & \overset{ϵ}{\to} (q_{1}, (A) S) \\ (q_{1}, C) & \overset{ϵ}{\to} (q_{1}, () S) \\ (q_{1}, {) & \overset{{}{\to} (q_{1}, ϵ) \\ (q_{1},}) & \overset{}}{\to} (q_{1}, ϵ) \\ (q_{1}, [) & \overset{[}{\to} (q_{1}, ϵ) \\ (q_{1},]) & \overset{]}{\to} (q_{1}, ϵ) \\ (q_{1}, () & \overset{(}{\to} (q_{1}, ϵ) \\ (q_{1},)) & \overset{)}{\to} (q_{1}, ϵ) \end{aligned}

Dies ist völlig mechanisch und benötigt kein Nachdenken. Wie fangen wir an? Wir legen anfangs ein

S

auf den leeren Stack. Wenn dieses

S

abgearbeitet ist und das Wort zu Ende ist, akzeptieren wir, und nur dann. Um festzustellen, dass wir wirklich den Stack ganz leer gemacht haben, brauchen wir die Markierung $. Also:

\begin{array}{r} (q_{s t a r t}, ϵ) \overset{ϵ}{\to} (q_{1}, S $) \\ (q_{1}, $) \overset{ϵ}{\to} (q_{e n d}, ϵ) \end{array}

Unsere Maschine hat also nur drei Zustände:

q_{s t a r t}

,

q_{1}

und

q_{e n d}

, welches der akeptierende Endzustand ist. Beachten Sie, dass es von

q_{e n d}

aus keine ausgehenden Transitionen gibt; sollte es also nach Erreichen von

q_{e n d}

noch weitere Zeichen im Eingabewort geben, so kann der Automat keine weiteren Schritte durchführen, was einem reject entspricht. Erreichen des Zustandes

q_{e n d}

führt also nur dann zu einem accept, wenn dies am Ende des Wortes geschieht.

Theorem. 5.2.3Zu jedem Kellerautomaten

gibt es eine kontextfreie Grammatik

mit

.

Beweis. Sei

der Kellerautomat. Als erstes führen wir drei Schönheitsoperation durch:

Der Automat hat einen einzigen akzeptierenden Zustand . Dies können wir einfach durch -Übergänge erreichen.
Der Automat leert den Stack, bevor er akzeptiert. Dies können wir z.B. dadurch erreichen, dass wir anfangs ein auf den Stack legen und am Ende den Stack poppen, bis wir gepoppt haben.
Für jede Transition ist genau eines von leer (und das andere ist genau ein Stacksymbol aus ). Eine Transition der Form nennen wir eine Push-Operation, eine der Form nennen wir eine Pop-Operation. Der Automat kann in diese Form gebracht werden, indem wir Zwischenzustände einführen: Im zweiten Falle pushen wir also pro Forma ein ansonsten irrelevantes Symbol auf den Stack, um es gleich darauf runterzupoppen.

Wenn nun der Automat die eben beschriebene Form hat, so ist die Idee, dass wir für jedes Paar von Zuständen ein Nichtterminalsymbol einführen, dass genau die Wörter ableiten kann, für die gilt, die also den Automaten von nach bringen können, wobei der Stack am Anfang und am Ende leer ist. Dies kann auf zwei Weisen geschehen:

Fall 1: in der Konfigurationsfolge von wird der Stack zwischendurch auch mal leer, und zwar nachdem der Präfix des Wortes gelesen ist, und der Automat ist zu diesem Zeitpunkt im Zustand . Also: Es sollte also (wenn unsere Konstruktion erfolgreich ist) gelten, dass und . Wir führen daher die Grammatikproduktion ein.
Fall 2: in der Konfigurationsfolge von ist der Stack zwischendurch nie leer. Das heißt wiederum, dass das im ersten Schritt gepushte Stacksymbol am Ende gepoppt wird, also mit Hier ist wichtig zu wissen, dass die erste Operation eine Push-Operation sein muss: Pop kann sie eh nicht sein, und die Möglichkeit haben wir durch unsere Schönheitsoperationen ausgeschlossen. Des weiteren ist zu beachten, dass in der Konfigurationsfolge von der Stack nie leer wird. Keine Transition "liest" also das unterste Zeichen -- denn dann müsste nacha Schönheitsoperation das ja gepoppt werden und der Stack würde vollständig geleert. In anderen Worten: die Konfigurationsfolge wäre auch dann gültig, wenn Anfangs- und Endstack nicht sondern , also der leere Stack wäre: Wenn unsere Konstruktion Erfolg hat, hieße das also und somit ist eine gültige Regel.

Schlussendlich führen wir noch die offensichtlich korrekten Regeln ein, da ja offensichtlich gilt (da ja auch die aus null Übergangen bestehende Konfigurationsfolge erlaubt).

Zusammenfassend gesagt besteht unsere Grammatik

aus drei unterschiedlichen Typen von Regeln:

Das Startsymbol der Grammatik ist natürlich .

Auch hier verzichte ich auf einen formalen Beweis, dass

gilt. Der Beweis verwendet (wenig überraschend) Induktion über die Länge der Ableitung bzw. Induktion über die Länge der Konfigurationsfolge und ist in Sipsers Lehrbuch im Detail erklärt.

Beispiel 5.2.4 Wir betrachten die Sprache

Diese ist nicht regulär, da der Präfix und der Suffix aus

die gleiche Länge

haben müssen. Wir bauen zuerst einen Kellerautomaten und übersetzen den dann entsprechend dem Schema aus dem letzten Theorem in eine Grammatik. Dann vergleichen wir die entstandene Grammatik mit der, die wir per Hand aus der obigen Sprachbeschreibung bauen würden.

Unser Automat hat einen Zustand , in welchem er führenden 's auf den Stack legt und einen Zustand , in welchem er die 's am Ende liest und vom Stack poppt. Zwischen den beiden 's in der Mitte ist er in einem Zustand , in welchem er die Eingabesymbole mehr oder weniger ignoriert. Der Automat muss nichtdeterministisch sein, da er "erraten" muss, welches das letzte ist, weil er dann mit dem Stack-Poppen beginnen muss.

Die beiden rot gefärbten Transitionen benötigen eine Schönheitsoperation:

Unsere Zustandsmenge ist also . Rein theoretisch müssten wir nun für alle Tripel von Zuständen eine Produktion einführen, also allein hierfür schon Produktionen. Wir können das reduzieren, indem wir die im Beweis beschriebene mechanische Prozedur mit ein wenig selbständigem Denken kombinieren.

Die erste Beobachtung ist, dass wir gar nicht von jedem Zustand zu jedem kommen können, sondern nur "vorwärts", also wie in diesem Diagramm:

Nichtterminale wie führen wir also gar nicht erst ein. Auch schreiben wir statt und verwenden die Indizes 0 für und 4 für . Als zweite Beobachtung sehen wir, dass man mit leerem Stapel beispielsweise gar nicht von nach kommt: auf dem Weg dorthin wird ein gepusht und nie gepoppt; gleiches gilt für viele weitere Zustandspaare. Das erweiterte Diagramm hier gibt eine Orientierung. Neben jeden Zustand haben wir schematisch den Stack gemalt:

Die einzigen Nichtterminale sind also die "trivialen" der Form

und darüberhinaus

Da man von

zu sich selber und von

zu sich selber nur mit dem leeren Wort gelant, ersetzen wir

und

sofort durch

. Als Produktionen der Form

erhalten wir also:

Schon deutlich besser als die 125 Produktionen, die wir bekämen, wenn wir stur an der Methode im Beweis festhalten würden. Wir brauchen noch Produktionen der Form

. Dafür müssen wir nach Push-Pop-Paaren

,

suchen. Stack-Symbole sind

. Suchen wir also zuerst nach Paaren von Transitionen, die

pushen und poppen.

Das waren die einzigen Transitionen, in denen

gepusht und gepoppt wird. Betrachten wir als nächstes das Stacksymbol

:

Nun zu den Transitionen mit Stacksymbol

. Da gibt es zwei Push-Transitionen und eine Pop-Transition, also zwei Paare:

Und schlussendlich die mit Stacksymbol $. Da gibt es eine Push- und eine Pop-Transition:

Sammeln wir nun alle Produktionen:

wobei

das Startsymbol ist. Wir haben diejenigen Nichtterminale und Produktionen rot markiert, aus denen nur

hervorgehen kann. Wir können die Grammatik nun entsprechend vereinfachen. Zusätzlich löschen wir

und ernennen

zu unserem Startsymbol:

Überlegen wir nun, ausgehend von dieser Grammatik, was wir aus dem Startsymbol ableiten können. Die einzigen zwei Produktionen mit sind und , also gilt Aus können wir per Produktion erst einmal alle Wortformem der Form ableiten; per dann alle Wortform . Also: Die Grammatik erzeugt also die gewünschte Sprache.

5.2 Kontextfreie Grammatiken und Kellerautomaten