Pumping-Lemma für kontextfreie Sprachen

Sei eine kontextfreie Sprache. Dann gibt es eine Konstante , so dass sich alle Wörter , zerlegen lassen in , so dass:

1. (Mittelteil begrenzt)
2. (Mindestens eine aufgepumpte Zeichenreihe ist leer)

Beispiel

• , so dass als darstellbar ist mit
  • .
• Wähle .
  • , ebenso .
  • muss gleiche Anzahl a, b, c enthalten (wegen mindestens einen).
  • kann nicht gleichzeitig a und c enthalten: aaa, aab, bbb, bbc, bcc, ccc
  • kann also nicht die gleiche Anzahl a, b, c enthalten.
  • Widerspruch!