Satz Umwandlung NDKA in äquivalenter KFG

Einfache Sprache

Def. Satz Umwandlung NDKA in äquivalenter KFG

Sei $\mathcal P = (Q,A,\Gamma,\delta,q_0,Z_0)$ ein NDKA. Dann sei ein KFG $\mathcal G$, die dieselbe Sprache erkennt wie $\mathcal P$, also $L(\mathcal G) = L_\text{empty stack}(\mathcal P)$, wie folgt definiert

$$\mathcal G = (A, V, S, R)$$

, wobei

• $V = \{S\}\cup\{[pXq]\mid p,q\in Q\land X\in\Gamma\}$ und
• $R = \{S\to[q_0Z_0p]\mid p\in Q\}\cup \left\{[qXr_k]\to a[rY_1r_1][r_1Y_2r_2]\ldots[r_{k-1}Y_kr_k]\mid (r,Y_1\ldots Y_k)\in \delta(q,a,X):a\in A_\varepsilon,k\in\mathbb N_0, r_i\in Q\right\}$

Bemerke:

• $\mathcal P$ kein $F$ hat, da es um Durch leeren Keller erkannte Sprache eines NDKA geht.
• $[\cdot]$ steht für ein zusammengesetztes Symbol abhängig von dem Inhalt. Es soll also als ein Symbol gewertet werden und bei unterschiedlichem Inhalt als unterschiedlich gewertet werden.

Beweisidee:

Beispiel: Beispiel KFG aus if-else Kellerautomat