Deterministisch kontextfreie Sprachen 76

Ein Kellerautomat $M$ heißt deterministisch, falls für alle $z\in Z$, $a\in\Sigma$ und $A\in\Gamma$ gilt:

$$\left\vert\delta\left(z,a,A\right)\right\vert+\left\vert\delta\left(z,\varepsilon,A\right)\right\vert\leq1$$

Ferner hat ein deterministischer Kellerautomat (Deterministic Push Down Automation = DPDA) eine ausgezeichnete Menge von Endzuständen $E\subseteq Z$.

$$T\left(M\right)=\left\{ x\in\Sigma^{*}\vert\exists z\in E:\left(z_{0},x,\char93 \right)\vdash^{*}\left(z,\varepsilon,\alpha\right)\right\}$$

ist die von einem DPDA akzeptierte Sprache.

Eine Sprache $L\subseteq\Sigma^{*}$ heißt deterministisch kontextfrei, wenn es einen DPDA $M$ gibt mit $L=T\left(M\right)$.

• $\mathcal{L}_{2}\subset$ deterministisch kontextfreie Sprachen $\subset\mathcal{L}_{3}$
• Stimmen mit den $LR\left(k\right)$-Sprachen überein (siehe Compilerbau)
• Die deterministisch kontextfreien Sprachen sind
  • unter Komplementbildung abgeschlossen
  • nicht unter Durchschnitt abgeschlossen
  • nicht unter Komplementbildung abgeschlossen
• Der Durchschnitt einer (deterministischen) kontextfreien Sprache mit einer regulären Sprache ist wieder (deterministisch) kontextfrei