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 \alpha$ auf $\alpha$ geschruft und das Restwort von $xw$ auf $w$; wenn also $x\alpha \Rightarrow^* xw$ galt, so gilt nun immer noch $\alpha \Rightarrow^* w$. Wenn ein Nichtterminal $X$ oben auf dem Stack liegt, dieser also die Form $X \alpha$ hat, und $w$ das Restwort ist, dann gilt also $X \alpha \Rightarrow^* w$. Der Automat rät nun nichtdeterministisch die erste in der Ableitung angewandte Produktion $X \rightarrow \beta$, löscht $X$ vom Stack und pusht $\beta$. Der Stack ist nun $\beta \alpha$, und $\beta \alpha \Rightarrow^* w$. Entscheidend ist der Nichtdeterminismus: es gibt eine korrekte Produktion $X \rightarrow \beta$, die schlussendlich zu $w$ führt; der Automat kann also diese Transition anwenden. Formaler: Die Zustände des Automaten sind $Q = \{\qstart, q_1, \qend\}$, das Stackalphabet ist \(\Gamma = \Sigma \cup N \cup \{\$\}\) und die Transitionsregeln sind

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.A\(\square\)

Beweis. Sei $M = (\Sigma, Q, \Gamma, \qstart, F, \delta)$ der Kellerautomat. Als erstes führen wir drei Schönheitsoperation durch:

1. Der Automat hat einen einzigen akzeptierenden Zustand $\qend$. Dies können wir einfach durch $\epsilon$ -Übergänge erreichen.

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

3. Für jede Transition

   $$ \begin{align*} (p, x) \step{a} (q, y) \end{align*} $$

   ist genau eines von $x,y$ leer (und das andere ist genau ein Stacksymbol aus $\Gamma$). Eine Transition der Form $(p, \epsilon) \step{a} (q, x)$ nennen wir eine Push-Operation, eine der Form $(p, y) \step{a} (q, \epsilon)$ nennen wir eine Pop-Operation. Der Automat kann in diese Form gebracht werden, indem wir Zwischenzustände einführen:

   $$ \begin{align*} &(p, x) \step{a} (q, y) \textnormal { wird ersetzt durch die zwei Transitionen } (p, x) \step{a} (p', \epsilon) \textnormal { und }(p', \epsilon) \step{a} (q, y) \\ &(p, \epsilon) \step{a} (q,\epsilon) \textnormal { wird ersetzt durch die zwei Transitionen } (p, \epsilon) \step{a} (p', \bigstar) \textnormal { und }(p', \bigstar) \step{a} (q, \epsilon) \ . \end{align*} $$

   Im zweiten Falle pushen wir also pro Forma ein ansonsten irrelevantes Symbol $\bigstar$ 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 $p,q$ von Zuständen ein Nichtterminalsymbol $A_{pq}$ einführen, dass genau die Wörter $w$ ableiten kann, für die

gilt, die also den Automaten von $p$ nach $q$ bringen können, wobei der Stack am Anfang und am Ende leer ist. Dies kann auf zwei Weisen geschehen:

1. Fall 1: in der Konfigurationsfolge von $(p, \epsilon) \Step{w}^* (q,\epsilon)$ wird der Stack zwischendurch auch mal leer, und zwar nachdem der Präfix $u$ des Wortes $w = uv$ gelesen ist, und der Automat ist zu diesem Zeitpunkt im Zustand $r$. Also:

   $$ \begin{align*} (p, \epsilon) \Step{u}^* (r,\epsilon) \Step{v}^* (q,\epsilon) \ . \end{align*} $$

   Es sollte also (wenn unsere Konstruktion erfolgreich ist) gelten, dass $A_{pr} \Rightarrow^* u$ und $A_{rq} \Rightarrow^* v$. Wir führen daher die Grammatikproduktion

   $$ \begin{align*} A_{pq} \rightarrow A_{pr} A_{rq} \end{align*} $$

   ein.

2. Fall 2: in der Konfigurationsfolge von $(p, \epsilon) \Step{w}^* (q,\epsilon)$ ist der Stack zwischendurch nie leer. Das heißt wiederum, dass das im ersten Schritt gepushte Stacksymbol $x$ am Ende gepoppt wird, also $w = avb$ mit

   $$ \begin{align*} (p, \epsilon) \step{a} (r, x) \Step{v}^* (s,x) \step{b} (q,\epsilon) \end{align*} $$

   Hier ist wichtig zu wissen, dass die erste Operation eine Push-Operation sein muss: Pop kann sie eh nicht sein, und die Möglichkeit $(p,\epsilon) \step{a} (r, \epsilon)$ haben wir durch unsere Schönheitsoperationen ausgeschlossen. Des weiteren ist zu beachten, dass in der Konfigurationsfolge von $(r, x) \Step{v}^* (s,x)$ der Stack nie leer wird. Keine Transition "liest" also das unterste Zeichen $x$ -- denn dann müsste nacha Schönheitsoperation das $x$ 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 $[x]$ sondern $\epsilon$, also der leere Stack wäre:

   $$ \begin{align*} (r, \epsilon) \Step{v}^* (s,\epsilon) \ . \end{align*} $$

   Wenn unsere Konstruktion Erfolg hat, hieße das also $A_{rs} \Rightarrow^* v$ und somit ist

   $$ \begin{align*} A_{pq} \rightarrow a A_{rs} b \end{align*} $$

   eine gültige Regel.

Schlussendlich führen wir noch die offensichtlich korrekten Regeln $A_pp \rightarrow \epsilon$ ein, da ja $(p, \epsilon) \Step{\epsilon}^* (p, \epsilon)$ offensichtlich gilt (da ja $\Step{}^*$ auch die aus null Übergangen bestehende Konfigurationsfolge erlaubt). Zusammenfassend gesagt besteht unsere Grammatik $G$ aus drei unterschiedlichen Typen von Regeln:

Das Startsymbol der Grammatik ist natürlich $A_{\qstart, \qend}$. Auch hier verzichte ich auf einen formalen Beweis, dass $L(G)=L(M)$ 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.A\(\square\)