Abschlusseigenschaften 62

Die kontextfreien Sprachen sind abgeschlossen unter:

• Vereinigung
  $L\left(G_{1}\right)\cup L\left(G_{2}\right)$
• 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 nicht kontextfreie Sprachen kombiniert werden, kann das Resultat trotzdem eine kontextfreie Sprache sein. Das einzige was sich Aussagen lässt ist, dass wenn eine Sprache nicht kontextfreie ist, mindestens eine Ihrer Komponenten auch nicht kontextfrei war.

• Der Durchschnitt einer (deterministischen) kontextfreien Sprache mit einer regulären Sprache ist wieder (deterministisch) kontextfrei