Normale Sprache Ergänzung
Kapitoly: Schließung von regulären Sprachen, Vereinheitlichung, Zugang zu, Der Unterschied, Ergänzung, Verkettung, Schlussfolgerung
Wir haben eine reguläre Sprache L. Wir beweisen, dass das Komplement von L wieder eine reguläre Sprache ist.
Was ist ein Komplement
Unter dem Komplement der Sprache L verstehen wir alle Wörter, die nicht in der Sprache Lenthalten sind. Wir bezeichnen das Komplement mit L', d.h. für das Alphabet $\Sigma$ gilt, dass:
$$ L' = \left\{w \in \Sigma^\ast,|, w \notin L\right\}. $$
Für eine Sprache mit Wörtern, die mindestens ein Symbol 1 enthalten, wäre ein Komplement beispielsweise eine Sprache, die Wörter enthält, die kein einziges Symbol 1 enthalten.
Verfahren
Das Verfahren ist sehr einfach. Wir haben die reguläre Sprache L und den Automaten $A=\left<Q, \Sigma, \delta, q_0, F\right>$, der sie miteinander verbindet. Wir konstruieren den Automaten A', der L' akzeptiert, indem wir die terminalen und nicht-terminalen Zustände vertauschen: $A'=\left<Q, \Sigma, \delta, q_0, Q\setminus F\right>$. Das war's.
Beispiel
Nehmen wir diesen Automaten:
Ein Automat, der ein Sprachkomplement empfängt, würde wie folgt aussehen:
