Abgeschlossenheit regulärer 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 die regulären Sprachen unter den Operationen Vereinigung, Schnitt, Konkatenation und Kleene-Stern abgeschlossen sind.

Abgeschlossenheit einer Menge unter einer Operation

Wir sagen, dass eine Menge M unter der Operation ⊗ abgeschlossen ist, wenn gilt:

$$\mathrm{\forall }x,y\in M:x\otimes y\in M$$

Ein Beispiel ist die Addition auf der Menge der natürlichen Zahlen. Die Summe zweier beliebiger natürlicher Zahlen ist wieder eine natürliche Zahl. Dagegen ist die Menge der natürlichen Zahlen unter der Subtraktion nicht abgeschlossen, denn zum Beispiel ist 7 − 15 = −8 und die Zahl −8 ist keine natürliche Zahl.

Wir beweisen, unter welchen Operationen die Menge der regulären Sprachen abgeschlossen ist. Alle Beweise werden konstruktiv sein, d. h. wir konstruieren einen Automaten, der die resultierende Sprache akzeptiert.