Satz NDKA erkennt if-else

Einfache Sprache

Um Wörter in if-else zu erkennen müssen wir im Grunde zwei Eigenschaften prüfen:

• Es müssen gleich viele $e$ und $i$ vorkommen.
• Jedes Präfix der Eingabe muss mehr $e$ als $i$ beinhalten.

Der Kellerautomat wird diese Eigenschaften wie folgt überprüfen:

• Für jedes gelesene $i$ wird ein Symbol eingekellert.
• Für jedes gelesene $e$ wird ein Symbol ausgekellert.
• Es wird akzeptiert
  1. wenn der Kellerspeicher leer ist oder alternativ
  2. wird zu beginn ein zusätzliches Symbol eingekellert so, dass es wenn der Keller leer ist ausgekellert werden kann um dabei in den akzeptierenden Zustand zu wecheseln.

Achtung

Es gilt nicht $L_\text{empty stack}(\mathcal P_1) = L_{ie}$. Da $\mathcal P_1$ mit einem $Z$ im Keller startet, bedeutet $Z^n$ auf im Keller, dass $n-1$ mehr $i$ als $e$ eingelesen wurden. Wenn nun der Keller leer ist bedeutet dies, dass zum ersten mal das Wort mehr $i$ als $e$ enthält, es also grade nicht zu $L_{ie}$ gehört.

Def. Satz NDKA erkennt if-else durch leeren Keller

Def. Satz NDKA erkennt if-else durch Endzustand

Wir definieren den Kellerautomat $\mathcal P_2$ der if-else durch Endzustand erkennt wie folgt

$$\mathcal P_2 = (\{p,q,r\},\{i,e\},\{Z,X\},\delta_2, q,X,\{r\})$$

mit

$$\delta_2(t,a,A)=\begin{cases}\{(q,ZX)\}&\text{if}&t=p\land a=\varepsilon\land A=X\\\{(q,ZZ)\}&\text{if}&t=q\land a=i\land A=Z\\\{(q,\varepsilon)\}&\text{if}&t=q\land a=e\land A=Z\\\{(r,\varepsilon)\}&\text{if}&t=q\land a=e\land A=X\\\end{cases}$$

Beweis: #TODO