• Artikel
• Bearbeiten
• Historie
• Druckansicht

Pumping Lemma für reguläre Sprachen

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

1. Wähle n (höher als Anzahl Nichtterminalsymbole)
2. Wähle ein Wort z ∈ L, so dass |z| ≥ n
3. Teile z auf in z = uvw, |uv| ≤ n, |v| ≥ 1
4. Zeige, dass für jedes uvw ein i existiert, so dass uvⁱw ∉ L
5. Wenn das klappt, kann L nicht regulär sein.