Ψ Die Informatikseite

Menü
Informatik » Bachelor » Theoretische Informatik » Kontextfreie Sprachen (CFG) » Abschlußeigenschaften der Klasse der kontextfreien Sprachen
Pumping Lemma für kontextfreie Sprachen Kontextfreie Sprachen (CFG) Griebach Normalform

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

Pumping Lemma für kontextfreie Sprachen Kontextfreie Sprachen (CFG) Griebach Normalform