Regulär

L ist von NEA / DEA erkennbar (L ist regulär).

Lemma: Ist \(L \subset \varSigma^*\) von DEA erkennbar, so auch \(\varSigma \backslash L\)

Beweis:

Sei \(a = (Q, \varSigma, q_0, \delta, F)\) ein DEA der L erkennt, so gilt:

\[\begin{split}w \in \varSigma^* \backslash L &\Longleftrightarrow \delta(q_0, w) \in Q \backslash L \\ &\Longleftrightarrow a' = (Q, \varSigma, q_0, \delta, Q \backslash F) \text{ akzeptiert w}.\end{split}\]

Also erkennt a’ \(\varSigma^* \backslash L\).

Folgerung:

Die durch DEA’s erkennbare Sprachen über \(\varSigma\) bilden eine boolsche Algebra (d.h abgeschlossen unter Vereinigung, Schnitt und Komplement).