Kellerautomaten 67

Definition 67

Ein (nichtdeterministischer) Kellerautomat, kurz PDA (pushdown automation), wird auf ein Eingabewort ist eine Erweiterung von DFA / NFA um das einen Keller als Speicher. Ein PDA $M$ wird spezifiziert durch ein $6$-Tupel

$$M=\left(Z,\Sigma,\Gamma,\delta,z_{0},\char93 \right)$$

• $Z$ endliche Menge der (internen) Zustände
• $\Sigma$ endliches Eingabealphabet
• $\Gamma$ endliches Kelleralphabet
• $z_{0}\in Z$ Startzustand
• $\delta:Z\times\left(\Sigma\cap\left\{ \varepsilon\right\} \right)\times\Gamma\rightarrow\mathcal{P}_{e}\left(Z\times\Gamma^{*}\right)$ Überführungsfunktion
  • z.B. $\left(z',B_{1}\ldots B_{k}\right)\in\delta\left(z,a,A\right)$
  • $\left(z',B_{1}\ldots B_{k}\right)\in\delta\left(z,\epsilon,A\right)$ spontaner Zustandswechsel ohne lesen eines neuen Terminals
• $\char93 \in\Gamma$ das unterste Kellersymbol

Eine Konfiguration $k$ eines Kellerautomaten ist durch ein Tripel $k\in Z\times\Sigma^{*}\times\Gamma^{*}$ gegeben.

• Startkonfiguration zur Eingabe $x\in\Sigma^{*}$: $\left(z_{0},x,\char93 \right)$

Die Rechenschrittrelation $\vdash$ist wie folgt definiert:

$$\left(z,a_{1}\ldots a_{n},A_{1}\ldots A_{m}\right)\vdash\left\{ \... ...}\ldots B_{k}\right)\in\delta\left(z,\varepsilon,A_{1}\right)\end{array}\right.$$

• es wird immer in Abhängigkeit vom obersten Symbol auf dem Stack, dem akt. internen Zustand, und eventuell (wenn es eine Regel mit einem $\varepsilon$ an zweiter Stelle gibt, dann nicht) dem Eingabeterminal ein neuer interner Zustand und ein Satz an Symbolen bestimmt, die auf den Stack gelegt werden, nachdem das oberste Symbol auf dem Stack entfernt wurde.

$$k\vdash^{*}k'\Leftrightarrow\left(\exists m\geq0:\exists k_{0},k_... ...wedge k'=k_{m}\wedge\forall_{\left[0,m-1\right]}^{i}:k_{i}\vdash k_{i+1}\right)$$

Die von $M$ (durch leeren Keller) akzeptierte Sprache ist:

$$N\left(M\right)=\left\{ x\in\Sigma^{*}\vert\exists_{Z}^{z}:\left(z_{0},x,\char93 \right)\vdash^{*}\left(z,\varepsilon,\varepsilon\right)\right\}$$

• $L$ kontextfrei $\Leftrightarrow$ $L$ wird von einem nichtdeterministischen Kellerautomaten akzeptiert
• Zu jedem PDA $M$ gibt es einen PDA $M'$ mit nur einem Zustand, sodass $N\left(M\right)=N\left(M'\right)$ gilt
  • durch Transformation in Grammatik, und anschließende Rücktransformation.

Von Grammatik zum Kellerautomaten 72

Gegeben ist eine kontextfreie Grammatik $G=\left(V,\Sigma,P,S\right)$ (Chomskynormalisierung nicht erforderlich, sogar eher kontraproduktiv, da die alles viel komplizierter macht). Ausgegeben wird ein PDA $M=\left(Z,\Sigma,\Gamma,\delta,z_{0},\char93 \right)$.

• $Z=\left\{ z\right\}$
• $\Sigma$ wird 1:1 übernommen
• $\Gamma=V\cup\Sigma$
• $z_{0}=z$
• $\char93 =S$ Startvariable wird als unterstes Kellersymbol genommen
• Erstellen der Überführungsfunktion $\delta$
  • Für alle Produktionen $\left(l\rightarrow r\right)\in P$
    • Füge eine Regel der Form $\delta\left(z,\varepsilon,l\right)=\left(z,r\right)$ hinzu
  • Für alle Terminale $a\in\Sigma$
    • Füge eine Regel der Form $\delta\left(z,a,a\right)=\left(z,\varepsilon\right)$ hinzu

Von Kellerautomaten zur Grammatik 73

Gegeben ist ein PDA $M=\left(Z,\Sigma,\Gamma,\delta,z_{0},\char93 \right)$. Ausgegeben wird eine kontextfreie Grammatik $G=\left(V,\Sigma,P,S\right)$.

• $\Sigma$ wird 1:1 übernommen
• $S$ wird mit $S$ besetzt
• $V=\left\{ S\right\} \cup\left(Z\times\Gamma\times Z\right)$
• Erstelle Produktionsregeln $P$
  • Für alle Zustände $z\in Z$
    • Füge eine Regel der Form $S\rightarrow\left(z_{0},\char93 ,z\right)$ hinzu
  • Für alle $\left(z',\varepsilon\right)\in\delta\left(z,a,A\right)$
    • Füge eine Regel der Form $\left(z,A,z'\right)\rightarrow a$ hinzu
  • Für alle $\left(z_{1},B\right)\in\delta\left(z,a,A\right)$ und alle $z'\in Z$
    • Füge eine Regel der Form $\left(z,A,z'\right)\rightarrow a\left(z_{1},B,z'\right)$ hinzu
  • Für alle $\left(z_{1},BC\right)\in\delta\left(z,a,A\right)$ und alle $z',z_{2}\in Z$
    • Füge eine Regel der Form $\left(z,A,z'\right)\rightarrow a\left(z_{1},B,z_{2}\right)\left(z_{2},C,z'\right)$ hinzu

Ist $G$ in Greibach Normalform, so kann ein PDA $M$ mit $L\left(G\right)=N\left(M\right)$ konstruiert werden, der keine $\varepsilon$-Übergänge hat.