Der Unterschied der regulären Sprachen
Kapitoly: Schließung von regulären Sprachen, Vereinheitlichung, Zugang zu, Der Unterschied, Ergänzung, Verkettung, Schlussfolgerung
Wir haben zwei reguläre Sprachen L1, L2. Wir beweisen, dass ihre Differenz L = L1 ∖ L2 auch eine reguläre Sprache ist.
Idee
Es gibt nicht wirklich viel zu beweisen. Tatsächlich gilt die folgende Beziehung für die Differenz zweier Mengen:
$$ L_1 \setminus L_2 = L_1 \cap L_2^\prime, $$
wobei $L_2^\prime$ das Komplement der Sprache L2 ist. Wir wissen aus den Kapiteln über die Schnittmenge regulärer Sprachen und das Komplement regulärer Sprachen, dass reguläre Sprachen für beide Operationen geschlossen sind. Das bedeutet, dass wir einen Automaten konstruieren können, der die Schnittmenge von Sprachen und das Komplement einer Sprache annimmt. Wir können also diese Automaten verwenden, um einen Automaten zu konstruieren, der die Sprache $L_1 \cap L_2^\prime$ akzeptiert, die auch die Sprache L1 ∖ L2 ist.
Beispiel
Nehmen wir diesen Automaten A1, der alle Wörter akzeptiert, die eine gerade Anzahl von 1en enthalten:
und einen Automaten A2, der Wörter akzeptiert, die eine ungerade Anzahl von 0 enthalten:
Wir konstruieren einen Automaten, der die Differenz dieser beiden Sprachen akzeptiert. Wir brauchen also einen Automaten $A_2^\prime$, der komplementär zum Automaten A2 sein wird. Wir vertauschen einfach die End- und Nicht-End-Zustände:
Jetzt konstruieren wir einfach einen Automaten A, der die Schnittmenge der Sprachen L(A1) und $L(A_2^\prime)$ akzeptiert:
