Berechnung eines NDKA

Einfache Sprache

Def. Berechnung eines NDKA

Sei $\mathcal P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ ein NDKA. Eine Berechnung von $\mathcal{P}$ auf $w\in \Sigma^*$ ist gegeben durch zwei Konfiguration:

1. die Anfangskonfiguration $I = (q_0,w,Z_0)$ und
2. die Endkonfiguration $J = (q_m, v, \beta)$,

wobei $J$ eine Erweiterte Folgekonfiguration von $I$ ist, also $I\overset{*}\vdash J$.