Satz NDKA von Endzustand zu äquivalenten leeren Kelller

Einfache Sprache

Die Idee ist das wir $\mathcal P_F$ so modifizieren, dass sobald ein akzeptierender Zustand erreicht wird, in einen Zustand übergeht in dem der Keller geleert wird ohne Eingabe zu lesen. Das bevor ein akzeptierender Zustand erreicht wird nicht zufällig der Keller leer ist wird am Anfang ein $\mathcal P_F$ fremdes Symbol eingekellert. So kann $P_F$ nicht den Keller leeren.

Def. Satz NDKA von Endzustand zu äquivalenten leeren Kelller

Sei $L$ die Durch Endzustand erkannte Sprache eines NDKA $\mathcal P_F =(Q,\Sigma,\Gamma,\delta_F,q_0,Z_0,F)$, also $L = L_\text{final state}(\mathcal P_F)$, dann existiert ein NDKA $\mathcal P_N$ so, dass $L = L_\text{empty stack}(\mathcal P_N)$.

Beweisidee: Satz NDKA von Endzustand zu äquivalenten leeren Kelller.svg Beiweis: Sei $P_N = (Q\cup \{p_0,p\},\Sigma,\Gamma\cup\{X_0\},\delta_N,p_0,X_0)$ wobei

$$\delta_N(q,a,Y) =\begin{cases}\{(q_0,Z_0X_0)\} &\text{if } q=p_0\land a=\varepsilon\land Y=X_0,\\\delta_F(q,a,Y)&\text{if }q\in Q\setminus F\land a\in\Sigma_\varepsilon\land Y\in\Gamma,\\\delta_F(q,a,Y)\cup\{(p,\varepsilon)\}&\text{if }q\in F\land a=\varepsilon\land Y\in\Gamma\cup\{X_0\}.\\\{(p,\varepsilon)\}&\text{if }q=p\land a=\varepsilon\land Y\in\Gamma\cup\{X_0\}.\\\end{cases}$$

Zu zeigen ist $L_\text{final state}(\mathcal P_F)\iff w\in L_\text{empty stack}(\mathcal P_N)$.

“$\Rightarrow$”: Sei $w\in L_\text{final state}(\mathcal P_F)$. Also nach der Definition existiert ein $\alpha\in\Gamma^*$ und $q\in F$ so, dass

$$(q_0,w,Z_0)\overset{*}{\underset{\mathcal P_F}\vdash}(q,\varepsilon, \alpha)\;.$$

Da alle Transitionen von $\mathcal P_F$ auch in $\mathcal P_N$ existieren gilt

$$(q_0,w,Z_0)\overset{*}{\underset{\mathcal P_N}\vdash}(q,\varepsilon, \alpha)\;.$$

Nun nutzen wir den Satz ungelesene Eingabe und unbenutzer Speicher beeinflusst Erweiterte Folgekonfiguration nicht um $X_0$ am unteren Ende des Kellers anzufügen ohne Auswirkung auf die Ableitung, also

$$(q_0,w,Z_0X_0)\overset{*}{\underset{\mathcal P_N}\vdash}(q,\varepsilon, \alpha X_0)\;.$$

Zusammen mit denn anderen Transitionsregeln ergibt sich folgende Ableitung

$$(q_0,w,X_0){\underset{\mathcal P_N}\vdash}(q_0,w,Z_0X_0)\overset{*}{\underset{\mathcal P_N}\vdash}(q,\varepsilon, \alpha X_0)\overset{*}{\underset{\mathcal P_N}\vdash}(p,\varepsilon,\varepsilon)\;.$$

Also ist $w\in L_\text{empty stack}(\mathcal P_N)\;.$

“$\Leftarrow$”: Aus der Definition von $\mathcal P_N$ können wir folgende Beobachtungen machen:

$\mathcal P_N$ kann den Keller nur leeren, wenn er im wenn er im Zustand $p$ ist, da das zu beginn gekellerte Symbol $X_0$ von keiner Transition von $\mathcal P_F$ ausgekellert werden kann.
Der Zustand $p$ kann nur erreicht werden, die simulierte $\mathcal P_F$ in einem akzeptierenden Zustand ist.
Ausgehend vom Startzustand $p_0$ gibt es nur eine mögliche Folgekonfiguration, die den Startzustand von $\mathcal P_F$ beinhaltet.

Daher muss für $w\in L_\text{empty state}(\mathcal P_F)$ die erweiterte Ableitung für einen $q\in F$ wie folgt aussehen:

Zwischen der Konfiguration $(q_0,w,Z_0X_0)$ bis $(q,\varepsilon, \alpha X_0)$ sind alle Transitionen auch in $\mathcal P_F$. Da $X_0$ von keiner Transition von $\mathcal P_F$ hat können wir nach dem Satz ungelesene Eingabe und unbenutzer Speicher beeinflusst Erweiterte Folgekonfiguration nicht folgen das für $\mathcal P_F$ die Berechnung

$$(q_0,w,X_0)\underset{\mathcal P_F}\vdash(q,\varepsilon,\alpha)$$

existiert muss, wobei $q\in F$ und ein beliebiger Kellerinhalt $\alpha\in\Gamma^*$. Da also $\mathcal P_F$ $w$ durch Endzustand akzeptiert, ist $w\in L_\text{final state}(\mathcal P_F)$.

Home: