Satz NDKA von leeren Keller zu äquivalenten Endzustand
Einfache Sprache
Def. Satz NDKA von leeren Keller zu äquivalenten Endzustand
Sei $L$ die Durch leeren Keller erkannte Sprache eines NDKA $\mathcal P_N =(Q,\Sigma,\Gamma,\delta_N,q_0,Z_0)$, also $L = L_\text{empty stack}(\mathcal P_N)$, dann existiert ein NDKA $\mathcal P_F$ so, dass $L = L_\text{final state}(\mathcal P_F)$.
Beiweisidee: 
Beweis: Sei $P_F = (Q\cup \{p_0,p_f\},\Sigma,\Gamma\cup\{X_0\},\delta_F,p_0,X_0,\{p_f\})$ wobei
$$\delta_F(q,a,Y) =\begin{cases}\{(q_0,Z_0X_0)\} &\text{if } q=p_0\land a=\varepsilon\land Y=X_0,\\ \delta_N(q,a,Y)&\text{if }q\in Q\land a\in\Sigma\land Y\in\Gamma,\\\delta_N(q,a,Y)\cup\{(p_f,\varepsilon)\}&\text{if }q\in Q\land a=\varepsilon\land Y=X_0.\\\end{cases}$$Zu zeigen ist $w\in L_\text{empty stack}(\mathcal P_N)\iff L_\text{final state}(\mathcal P_F)$.
“$\Rightarrow$”: Sei $w\in L_\text{empty stack}(\mathcal P_N)$. Also nach der Definition gilt
$$(q_0,w,Z_0)\overset{*}{\underset{\mathcal P_N}\vdash}(q,\varepsilon, \varepsilon)$$für ein beliebiges $q\in Q$. Nach dem Satz ungelesene Eingabe und unbenutzer Speicher beeinflusst Erweiterte Folgekonfiguration nicht können wir $X_0$ am unteren Ende des Kellers anfügen, also
$$(q_0,w,Z_0X_0)\overset{*}{\underset{\mathcal P_N}\vdash}(q,\varepsilon, X_0)\;.$$Da jede Transition von $\mathcal P_N$ auch in $\mathcal P_F$ ist, existiert die erweiterte Ableitung auch für $\mathcal P_F$, also
$$(q_0,w,Z_0X_0)\overset{*}{\underset{\mathcal P_F}\vdash}(q,\varepsilon, X_0)\;.$$Dass können wir um zwei Ableitungen aus $\delta_F$ erweitern und erhalten
$$(p_0,w,X_0){\underset{\mathcal P_F}\vdash}(q_0,w,Z_0X_0)\overset{*}{\underset{\mathcal P_F}\vdash}(q,\varepsilon, X_0){\underset{\mathcal P_F}\vdash}(p_f,\varepsilon,\varepsilon)\;.$$$\mathcal P_F$ akzeptierte durch Endzustand $w$. Also ist $w\in L_\text{final state}(\mathcal P_F)\;.$
“$\Leftarrow$”: Aus der Definition von $\mathcal P_F$ können wir folgende Beobachtungen machen:
- $X_0$ kommt nur als letztes Zeichen im Keller vor.
- Wir kommen nur in den (einzigen) Endzustand, wenn $X_0$ auf dem Stapel oben liegt.
- Von dem einzigen Startzustand $p_0$ können wir nur zu $q_0$, in dem wir $X_0$ in den leeren Keller einkellern. Da es die einzige Transition ist, muss $\mathcal P_F$ diese zu beginn anwenden.
Für $w\in L_\text{empty state}(\mathcal P_F)$ muss die erweiterte Ableitung wie folgt aussehen:
$$(p_0,w,X_0){\underset{\mathcal P_F}\vdash}(q_0,w,Z_0X_0)\overset{*}{\underset{\mathcal P_F}\vdash}(q,\varepsilon, X_0){\underset{\mathcal P_F}\vdash}(p_f,\varepsilon,\varepsilon)\;.$$Alle bis auf die letzte und erste Ableitung müssen auch in $\delta_N$ möglich sein, denn es können nur Transitionen die auch in $\mathcal P_N$ definiert sind benutzt werden. Das sieht man, da $X_0$ nicht. Also gilt
$$(q_0,w,Z_0)\overset{*}{\underset{\mathcal P_N}\vdash}(q,\varepsilon, \varepsilon)$$Also ist $w\in L_\text{empty stack}(\mathcal P_N)\;.$