Abschlusseigenschaften 48

Die regulären Sprachen sind abgeschlossen unter:

• Vereinigung
  $L\left(G_{1}\right)\cup L\left(G_{2}\right)$
• Schnitt
  Wort muss in beiden Sprachen vorkommen
• Komplement
  Bei Grammatik: Endzustände ersetzen gegen Variablen ohne die alten Endzustände
• Produkt
  Konkatenation der Wörter aus den einzelnen Sprachen
  $L\left(G_{1}\right)L\left(G_{2}\right)$
• Stern
  Wiederholen der Wörter

Umkehrschluss nicht möglich: Wenn nichtreguläre Sprachen kombiniert werden, kann das Resultat trotzdem eine reguläre Sprache sein. Das einzige was sich Aussagen lässt ist, dass wenn eine Sprache nicht Regulär ist, mindestens eine Ihrer Komponenten auch nicht regulär war.