Folgekonfiguration eines Kellerautomaten

Einfache Sprache

Eine Folgekonfiguration für einen NDKA erhält man in dem man den NDKA ein Schritt auf einer Konfiguration eines Kellerautomaten arbeiten lässt. Falls es mehrere Schritte sein sollen benutzt man die Erweiterte Folgekonfiguration eines Kellerautomaten

Def. Folgekonfiguration eines Kellerautomaten

Sei $\mathcal P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ ein NDKA. Wir definieren die Folgekonfiguration-Relation $\underset{\mathcal P}\vdash$, bzw. $\vdash$ wenn $\mathcal P$ aus dem Kontext klar ist, wie folgt:

Sei $(p,\alpha)\in\delta(q,a,X)$ für passendes $q\in Q$, $a\in\Sigma$ und $X\in \Gamma$. Dann gilt

$$\forall w\in\Sigma^*, \beta\in\Gamma^*:(q,aw,X\beta)\vdash(p,w,\alpha\beta)$$