• Artikel
• Bearbeiten
• Historie
• Druckansicht

Pumping Lemma für kontextfreie Sprachen

Um zu zeigen, dass eine bestimmte Sprache L nicht kontextfrei ist, kann man so vorgehen:

1. Wähle n (2^m, m ist die Anzahl Nichtterminalsymbole)
2. Wähle ein Wort z ∈ L, so dass |z| ≥ n
3. Teile z auf in z = uvwxy, |ux| ≥ 1, |vwx| ≤ n
4. Zeige, dass für jedes uvwxy ein i≥0 existiert, so dass uvⁱwxⁱy ∉ L
5. Wenn das klappt, kann L nicht kontextfrei sein.