Satz ungelese Eingabe und unbenutzer Speicher beeinflusst Erweiterte Folgekonfiguration nicht

Einfache Sprache

Def. Satz ungelese Eingabe und unbenutzer Speicher beeinflusst Erweiterte Folgekonfiguration nicht

Sei $\mathcal P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ ein NDKA und $(p,y,\beta)$ eine Folgekonfiguration von $(q,x,\alpha)$, also $(q,x,\alpha)\overset{*}\vdash (p,y,\beta)$, dann gilt für alle $w\in\Sigma^*$ und $\gamma\in\Gamma^*$

$$(q, xw,\alpha\gamma)\overset{*}\vdash(p,yw,\beta\gamma)\;.$$

Beweisidee: induktiv über die Anzahl der Folgekonfigurationen. Bei jeder Folgekonfiguration wird $w$ und/oder $\gamma$ in keinster weise benutzt. Daher auch nicht bei der Verkettung von den Folgekonfigurationen bzw. der erweiterten Folgekonfiguration.