Durch Endzustand erkannte Sprache eines NDKA

Einfache Sprache

Def. Durch Endzustand erkannte Sprache eines NDKA

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

$$L_\text{final state}(\mathcal P) = \left\{w\in \Sigma^*\mid\exists q\in F, \alpha\in\Gamma^*:(q_0,w,Z_0)\overset{*}\vdash(q,\varepsilon, \alpha)\right\}$$

.

Mit anderen Worten: $L_\text{final state}(\mathcal P)$ enthält alle durch Endzustand akzeptierte Wörter von $\mathcal P$.