Ψ Die Informatikseite

Menü

Abschlußeigenschaften der Klasse der kontextfreien Sprachen

Die Klasse der Kontextfreien Sprachen ist unter Vereinigung, Konkatenation und Kleenabschluß abgeschlossen, nicht aber unter Durchschnitts58 oder Komplementbildung59.

Fußnoten

... Durchschnitts58

\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
... Komplementbildung59
Ist unter der Komplementbildung nicht abgeschlossen, weil sie unter dem Durchschnitt nicht abgeschlosse sind. Dies gilt wegen der Regel von De-Morgan