Schließung von regulären Sprachen

Eine Sprache L ist genau dann regulär, wenn es einen Automaten A gibt, der diese Sprache akzeptiert, d.h. L(A) = L. Wir beweisen, dass reguläre Sprachen unter den Operationen Vereinigung, Schnittmenge, Verkettung und Abschluss geschlossen sind.

Geschlossenheit einer Menge in Bezug auf eine Operation

Wir sagen, dass die Menge M unter der Operation $\otimes$ geschlossen ist, wenn es gilt, dass

$$ \forall x, y \in M: x \otimes y \in M $$

Ein Beispiel ist die Additionsoperation für die Menge der natürlichen Zahlen. Die Summe zweier beliebiger natürlicher Zahlen ist wieder eine natürliche Zahl. Umgekehrt ist die Menge der natürlichen Zahlen nicht geschlossen bei der Subtraktion, weil z.B. 7 − 15 = −8 und die Zahl −8 keine natürlichen Zahlen sind.

Wir können beweisen, gegen welche Operationen die Menge der regulären Sprachen abgeschlossen ist. Alle Beweise werden konstruktiv sein, d.h. wir werden einen Automaten konstruieren, der die resultierende Sprache annimmt.