Beispiel KFG aus if-else Kellerautomat

Einfache Sprache

Wir nutzen den Satz Umwandlung NDKA in äquivalenter KFG um den in NDKA $\mathcal P_1$ in eine KFG umzuwandeln, die $L_{ei}$ erkennt.

Def. Satz KFG erkennt if-else

Sei $\mathcal P_1 = (\{q\},\{i,e\},\{Z\},\delta_1, q,Z)$ der Kellerautomat, der if-else durch leeren Keller erkennt.

Die aus dem Satz Umwandlung NDKA in äquivalenter KFG resultierende KFG

$$\mathcal G = (\{i,e\},\{S\},S,\{S\to iSS\;|\;e\})$$

erkennt die Sprache if-else.

Beweis: Wir wenden einfach die Konstruktionsvorschrift von Satz Umwandlung NDKA in äquivalenter KFG an um aus einem Kellerautomat, von dem wir wissen, dass er if-else erkennt Satz NDKA erkennt if-else, eine KFG zu machen:

Wir der Satz stumpf angewand erhalten wir folgende Grammatik

• Die Menge der Terminalsymbole ist gleich dem Eingabealphabet.
• Die Variablenmenge besteht nur aus dem Startzustand $S$ und dem Zustand $[qZq]$, da $\mathcal P_1$ nur einen Zustand $q$ und Bandsymbol $Z$ hat.
• Als Produktionsregeln ergibt sich:
  1. die Regel $S\to[qZq]$,
  2. aus der Transition $(q,ZZ)\in\delta_1(q,i,Z)$ können wir dir Regel $[qZq]\to i[qZq][qZq]$ ableiten und
  3. aus der Transition $(q,\varepsilon)\in\delta_1(q,e,Z)$ ergibt sich $[qZq]\to \varepsilon$.

Wenn wir nun $[qZq]$ durch die, noch nicht in der Grammatik vorhandenen, Variable $A$ ersetzen erhalten wir

Weiter können wir $S$ entfernen, da immer die Regel $S\to A$ angewendet wird. Wir erhalten