Fortsetzung

Definition der Fortsetzung von \(\delta\) mit \(\delta^*: Q \times \varSigma^* \rightarrow Q\) wird definiert durch

\[\delta^*(q, \varepsilon) = q \delta^*(q, w a) = \delta(\delta^*(q,w), a) \text{ für } w \in \varSigma^*, a \in \varSigma\]

\(\delta^*(p,w) = q \Longleftrightarrow a: p \rightarrow^w q\)

Beweis

Durch Induktion über den Aufbau der Wörter über \(\varSigma\):

\(\underline{w = \varepsilon}\):

\[\delta^*(p, \varepsilon) = q \Longleftrightarrow p = q \Longleftrightarrow a: p \rightarrow^{\varepsilon} q\]

\(\underline{w = v a \in \varepsilon}\):

\[\begin{split}\delta^*(p, \varepsilon) = q &\Longleftrightarrow^{Def. \delta^*} \delta(\delta^*(p, v), a) = q \\ &\Longleftrightarrow \exists p': \delta^*(p,v) = p' \wedge \delta(p', a) = q \\ &\Longleftrightarrow \exists p': a: p \rightarrow^v p' \wedge p' \rightarrow^ q \\ &\Longleftrightarrow^{IV} p \rightarrow^{va} Q\end{split}\]

Bemerkung b

\(L(a) = \{ w \in \varSigma^* \mid \delta^*(q_0, w) \in F\}\)

Schreibweise

\(\delta(q,w)\) statt \(\delta^*(q,w)\)