Theoretische Informatik - Abschlußeigenschaften

Nächste Seite: Griebach Normalform Aufwärts: Kontextfreie Sprachen (CFG) Vorherige Seite: Pumping Lemma für kontextfreie Inhalt

Abschlußeigenschaften

Die Klasse der Kontextfreien Sprachen ist unter Vereinigung, Konkatenation und Kleenabschluß abgeschlossen, nicht aber unter Durchschnitts⁵⁸ oder Komplementbildung⁵⁹.

Fußnoten

... Durchschnitts ⁵⁸

$\begin{displaymath}L_{1}=\{a^{n}b^{n}c^{m}:n,m\geq 1\}\,\,\,\,\,L_{2}=\{a^{m}b^{n}c^{n}:n,m\geq 1\}\end{displaymath}$

Obwohl beide Sprachen kontextfrei sind, ist

$\begin{displaymath}L_{1}\cap L_{2}= \{a^{n}b^{n}c^{n}:n\geq 1\}\end{displaymath}$

nicht kontextfrei

... Komplementbildung ⁵⁹

Ist unter der Komplementbildung nicht abgeschlossen, weil sie unter dem Durchschnitt nicht abgeschlosse sind. Dies gilt wegen der Regel von De-Morgan