Satz Umwandlung KFG in äquivalenter NDKA

Einfache Sprache

Def. Satz Umwandlung KFG in äquivalenter NDKA

Sei $\mathcal G = (T,V,S,P)$ eine Kontextfreie Grammatik. Konstruiere den NDKA $\mathcal P = (\{q\},T,V\cup T,\delta,q,S)$ wobei

$$\delta(q,a,\alpha) =\begin{cases}\{(q,\beta)\mid\alpha\to \beta \in P\} &\text{if}& a=\varepsilon\land \alpha\in V\cup T,\\\{(q,\varepsilon)\} &\text{if}& a\in T \land a = \alpha.\end{cases}$$

Die Durch leeren Keller erkannte Sprache eines NDKA $\mathcal P$ ist gleich der von $\mathcal G$ produzierten Sprache. Also

$$L(\mathcal G) = L_\text{empty stack}(\mathcal P)\;.$$

Beweisidee: Wir simulieren mit dem Kellerautomaten $\mathcal P$ die leftmost Ableitung von $\mathcal G$. Wir können uns darauf einschränken, wegen diesem Satz Syntaxbaum, erweiterte Ableitung und rekursive Inferenz sind äquivalent.

Bemerke, dass jede leftmost Ableitung, die Variablen enthält, als $xA\alpha$ geschrieben werden kann, wobei $x\in T^*$, $A\in V$ und $\alpha\in\Sigma^*$. Wir nennen $A\alpha$ Tail.

In $\mathcal P$ ist $x$ die Terminal-Zeichenkette dem Anfang der Eingabe übereinstimmt. $A$ ist das Symbol auf dem Keller, was als nächstes mit einer Produktionsregel ersetzt wird oder als wenn passendes Terminal $x$ hinzugefügt wird. $\alpha$ ist der Rest unter $A$, der noch verarbeitet werden muss.

Nun funktioniert $\mathcal P$ folgendermaßen: $\mathcal P$ startet mit der Eingabe $w$ und dem Startsymbol im Keller. Es gibt zwei mögliche Transitionen:

• Falls ein Terminalsymbol oben auf dem Keller liegt, muss es entfernt werden. Dies kann es nur, wenn es mit dem nächsten Symbol in der Eingabe übereinstimmt. Sonst verwerfe.
• Falls ein Variable auf dem Keller liegt, kann diese mit Hilfe einer nichtdeterministisch ausgewählten passenden Produktionsregel aus $P$ durch deren Body ausgetauscht werden.

Beide Transitionen werden so lange wiederholt, bis der Keller leer ist. Dann wird akzeptiert.

Wir raten also die leftmost Ableitung für $w$ von $S$.

Beweis: Zu zeigen $w\in L(\mathcal G) \iff w \in L_\text{empty stack}(\mathcal P)$.

“$\Rightarrow$”: Sei $w\in L(\mathcal G)$. Dann existiert nach der Definition von Kontextfreie Sprachen eine leftmost Ableitung

Wir wollen nun mit Induktion zeigen, dass $(q,w,S)\overset{*}{\underset{P}\vdash}(q,y_i,\alpha_i)$, wobei $y_i$ und $\alpha_i$ die leftmost Ableitung $\gamma_i$ repräsentieren was folgendes bedeutet:

• $\alpha_i$ ist der tail $\gamma_i$. Also $\gamma_i = x_i\alpha_i$ für ein $x_i$.
• $y_i$ ist der Rest der Eingabe, wenn $x_i$ schon von $w$ »weggelesen« wurde. Also $x_iy_i = w_i$.

IA: Sei $i = 1$. Dann ist $x_1 = \varepsilon$ und $y_1 = w$.

IS: Zu zeigen ist $(q,w,S)\overset{*}\vdash(q,y_{i+1},\alpha_{i+1})$ unter der Annahme (IH), dass $(q,w,S)\overset{*}\vdash(q,y_{i},\alpha_{i})$ gilt. Da $\alpha_i$ ein tail ist, beginnt es mit einer Variablen $A$. Im letzten Ableitungsschritt von $\gamma_i$ nach $\gamma_{i+1}$ wird dieses $A$ mithilfe einer möglichen Produktionsregel zu $\beta$. Der obere Fall im $\delta$ von $\mathcal P$ lässt uns $A$ auf dem Keller durch $\beta$ ersetzen. Dann nutzen wir den unteren Fall um $\beta$ mit der Eingabe zu überprüfen. Wir erhalten $(q,y_{i+1},\alpha_{i+1})$, was die nächste leftmost Ableitung $\gamma_{i+1}$ darstellt.

Abschließend bemerke, dass $\alpha_n = \varepsilon$, da der tail von $\gamma_n$ leer ist. Daher $(q,w,S)\overset{*}\vdash(q,\varepsilon,\varepsilon)$, weshalb $\mathcal P$ $w$ durch leeren Keller erkennt, also $w\in L_\text{empty stack}(\mathcal P)$.

“$\Leftarrow$”: Wir zeigen etwas mächtigeres und zwar

Das bedeutet, dass wenn $\mathcal P$ eine Berechnung durchführt, deren Endeffekt, dass auskellern von $A$ ist ohne unter $A$ auszukellern, dann kann die Eingabe $x$ von $\mathcal G$ ausgehend von $A$ abgeleitet werden.

Wir nutzen Induktion über die Länge der Berechnung von $\mathcal P$.

IA: $\mathcal P$ macht eine Transition. Die einzige Möglichkeit wie $\varepsilon$ im Keller sein kann ist, wenn $A\to\varepsilon\in P$ und diese benutzt wird. Es kommt der obere Fall zu Anwendung. Also $A\Rightarrow w$.

IB: Jetzt macht $\mathcal P$ $n$ Transitionen mit $n> 1$. Die erste Transition muss der obere Fall von $\delta$ sein, da $A$, nach der Beobachtung zu leftmost Ableitung, eine Variable sein muss (da der untere Fall nur eintreten kann, wenn $A$ ein Terminalsymbol ist). Nehme an es werde die Produktionsregel $A\to Y_1Y_2\ldots Y_k$ benutzt. Dann ist für $i\in[1,k]$ $Y_i$ ein Terminalsymbol oder eine Variable. Die nächsten $n-1$ Transitionen von $\mathcal P$ müssen $x$ »weglesen« und dabei alle $Y_i$ auskellern. Wir definieren die Zerlegung $x=x_1x_2\ldots x_k$, wobei $x_i$ ist der Teil von $x$ der, während der Verarbeitung von $Y_i$ und dessen Ableitungen, »weggelesen« wird.

Beispiel

Der Graph zeigt die Größe des Kellers im Relation zur Eingabe. Im Keller sind $BaC$ und die Eingabe ist in $x = x_1x_2x_3$ aufgeteilt, wobei $x_2 = a$. Wir sehen das während der Verarbeitung einer Variable der Keller beliebig anwachsen und bis zur nächsten Variable oder Terminalsymbol $Y_{i+1}$ anwachsen bzw. schrumpfen kann.

Wir stellen also fest, dass $(q,x_ix_{i+1}\ldots x_k,Y_i)\overset{*}\vdash(q,x_{i+1}\ldots x_k,\varepsilon)$ für $i\in[1,k]$. Da keiner der Berechnungen mehr als $n-1$ lang sein kann, können wir mit der IH schließen, dass $Y_i\overset{*}\Rightarrow x_i$.

Falls $Y_i$ ein Terminalsymbol ist, gilt auch $Y_i\overset{*}\Rightarrow x_i$.

Zusammen ergibt sich die Ableitung

Was äquivalent zu $A\overset{*}\Rightarrow x$ ist.

Wir setzen ein $A=S$ und $x = w$. Da $w\in L_\text{empty stack}(\mathcal P)$ existiert die Berechnung $(q,w,S)\overset{*}\vdash(q,\varepsilon,\varepsilon)$. Aus der oben induktiv bewiesenen Aussagen folgt $S\overset{*}\Rightarrow w$. Was $w\in L(\mathcal G)$ bedeutet.