Differenz regulärer Sprachen

Seien L₁, L₂ zwei reguläre Sprachen. Wir beweisen, dass ihre Differenz L = L₁ ∖ L₂ ebenfalls eine reguläre Sprache ist.

Idee

Eigentlich gibt es nicht viel zu beweisen. Für die Differenz zweier Mengen gilt nämlich der folgende Zusammenhang:

$$L_1\setminus L_2=L_1\cap L_2^{\prime },$$

wobei L₂′ das Komplement der Sprache L₂ ist. Aus den Kapiteln über den Schnitt regulärer Sprachen und das Komplement einer regulären Sprache wissen wir, dass reguläre Sprachen unter beiden Operationen abgeschlossen sind. Das bedeutet, dass wir einen Automaten konstruieren können, der den Schnitt von Sprachen akzeptiert, und einen, der das Komplement einer Sprache akzeptiert. Mit diesen Automaten können wir einen Automaten konstruieren, der die Sprache L₁ ∩ L₂′ akzeptiert, und das ist zugleich die Sprache L₁ ∖ L₂.

Beispiel

Gegeben sei dieser Automat A₁, der alle Wörter akzeptiert, die eine gerade Anzahl von Einsen enthalten:

und der Automat A₂, der Wörter mit einer ungeraden Anzahl von Nullen akzeptiert:

Wir konstruieren einen Automaten, der die Differenz dieser Sprachen akzeptiert. Dazu brauchen wir den Automaten A₂′, der das Komplement zum Automaten A₂ ist. Wir vertauschen einfach die Endzustände und die Nicht-Endzustände:

Jetzt konstruieren wir nur noch den Automaten A, der den Schnitt der Sprachen L(A₁) und L(A₂′) akzeptiert:

Quellen

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