Komplement einer regulären Sprache

Sei L eine reguläre Sprache. Wir beweisen, dass das Komplement der Sprache L wieder eine reguläre Sprache ist.

Was ist das Komplement

Unter dem Komplement der Sprache L verstehen wir alle Wörter, die nicht in der Sprache L liegen. Das Komplement bezeichnen wir mit L'. Für ein Alphabet Σ gilt also:

$$L^{\prime }=\{w\in {\mathrm{\Sigma }}^{\ast }|w\notin L\}.$$

Zum Beispiel wäre für die Sprache der Wörter, die mindestens ein Symbol 1 enthalten, das Komplement die Sprache der Wörter, die kein einziges Symbol 1 enthalten.

Vorgehen

Das Vorgehen ist sehr einfach. Wir haben eine reguläre Sprache L und einen deterministischen vollständigen Automaten A = ⟨Q, Σ, δ, q₀, F⟩, der sie akzeptiert (jeden endlichen Automaten kann man in einen solchen umwandeln). Den Automaten A', der L' akzeptiert, konstruieren wir, indem wir die Endzustände und die Nicht-Endzustände vertauschen: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Das ist alles.

Beispiel

Gegeben sei dieser Automat:

Der Automat, der das Komplement der Sprache akzeptiert, sähe so aus:

Quellen

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools