Fragen zu kontextfreien Sprachen

Welche der folgenden Aussagen beschreibt korrekt das Pumping-Lemma für kontextfreie Sprachen?

• A) Jede kontextfreie Sprache L enthält ein Wort, das sich in drei Teile u, v, w zerlegen lässt, sodass uvⁿw ∈ L für alle n ≥ 0.

• B) Es existiert eine Zerlegung eines Wortes z ∈ L in fünf Teile u, v, w, x, y mit bestimmten Bedingungen, sodass uvⁿwxⁿy ∈ L für alle n ≥ 0.

• C) Für jede kontextfreie Sprache L gilt: Alle Wörter lassen sich in zwei Teile teilen, sodass das erste Teil in der Sprache liegt.

• D) Das Pumping-Lemma gilt nur für reguläre Sprachen.

Welche der folgenden Sprachen ist kontextfrei?

• A) L = { aⁿbⁿcⁿ | n ≥ 0 }

• B) L = { aⁿbⁿ | n ≥ 0 }

• C) L = { ww | w ∈ {a, b}* }

• D) L = { aⁱbʲcᵏ | i, j, k ≥ 0 und i = j oder j = k }

Welche dieser Sprachen ist nicht kontextfrei?

• A) L = { aⁿbᵐcᵐ | n, m ≥ 0 }

• B) L = { aⁿbⁿcⁿ | n ≥ 0 }

• C) L = { aⁿbⁿ | n ≥ 0 }

• D) L = { aⁿbᵐ | n ≠ m }

Welche der folgenden Sprachen ist kontextfrei, aber nicht regulär?

• A) L = { aⁿbⁿ | n ≥ 0 }

• B) L = { (ab)ⁿ | n ≥ 0 }

• C) L = { aⁿbᵐ | n, m ≥ 0 }

• D) L = { aⁿbⁿcᵐ | n, m ≥ 0 }

Ist die folgende Sprache kontextfrei? L = { aᵐbⁿ | m, n ≥ 0 }

• A) Ja

• B) Nein

Welche der folgenden Operationen sind regulären Sprachen gegenüber abgeschlossen?

• A) Vereinigung

• B) Schnitt

• C) Komplement

• D) Klenee-stern

Welche der folgenden Operationen sind kontextfreien Sprachen gegenüber abgeschlossen?

• A) Vereinigung

• B) Schnitt

• C) Komplement

• D) Konkatenation

• E) Kleene-stern

Gegeben zwei Sprachen L₁, L₂ ∈ CFL. Welche der folgenden Kombinationen ergibt nicht notwendigerweise wieder eine CFL?

• A) L₁ ∪ L₂

• B) L₁ ⋅ L₂

• C) L₁*

• D) L₁ ∩ L₂