Erweiterte Folgekonfiguration eines Kellerautomaten
Einfache Sprache
Die Erweiterte Folgekonfiguration eines Nichtdeterministischer Kellerautomat wird analog zur Folgekonfiguration eines Kellerautomaten definiert, nur dass in diesem Fall mehrere oder Null Schritte des Kellerautomaten erlaubt sind.
Def. Erweiterte Folgekonfiguration eines Kellerautomaten
Sei $\mathcal P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ ein NDKA. Wir definieren die erweiterte Folgekonfiguration-Relation $\overset{*}{\underset{\mathcal P}\vdash}$, bzw. $\overset{*}\vdash$ wenn $\mathcal P$ aus dem Kontext klar ist, induktiv wie folgt:
IA: Für alle Konfiguration eines Kellerautomaten $I$ gilt $I\overset{*}\vdash I\;.$
IS: Für zwei Konfigurationen $I, J$ gilt $I\overset{*}\vdash J$, falls eine Konfiguration $K$ existiert so, dass $I \vdash K$ und $K\overset{*}\vdash J$ gilt. Es muss also eine Folge von Konfigurationen $K_1,\ldots,K_n$ existieren so, dass $I=K_1$, $J=K_n$ und $\forall i\in[1,n-1]:K_i\vdash K_{i+1}\;.$