Durch leeren Keller erkannte Sprache eines NDKA

Einfache Sprache

$L_\text{empty stack}(\mathcal P)$ ist die Sprache, die alle Wörter beinhaltet, welche als Eingabe für $\mathcal P$ dazu führen, dass $\mathcal P$ einen leeren Kellerspeicher hat.

Def. Durch leeren Keller erkannte Sprache eines NDKA

Sei $\mathcal P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ ein NDKA. Die durch leeren Keller Erkannte Sprache von $\mathcal P$, $L_\text{empty stack}(\mathcal P)$, ist definiert als

$$L_\text{empty stack}(\mathcal P) = \left\{w\in \Sigma^*\mid\exists q\in Q:(q_0,w,Z_0)\overset{*}\vdash(q,\varepsilon, \varepsilon)\right\}$$

.

Mit anderen Worten: $L_\text{empty stack}(\mathcal P)$ enthält alle durch leeren Keller akzeptierte Wörter von $\mathcal P$.