Das Pumping Lemma liefert keine hinreichende Bedingung für Regularität einer Sprache. Es gibt Sprachen, die die im Pumping Lemma von regulären Sprachen geforderte Eigenschaft haben, aber trotzdem nicht regulär sind. Man kann mit dem Pumping Lemma deshalb nicht beweisen, dass eine Sprache regulär ist. Um zu beweisen, dass eine Sprache regulär ist, gibt man stattdessen einen Automaten oder einen regulären Ausdruck oder eine Typ-3-Grammatik an.
Das Pumping Lemma liefert eine notwendige Bedingung für Regularität einer Sprache. Ist diese Bedingung nicht erfüllt, dann kann die Sprache nicht regulär sein.
Das Pumping Lemma fordert die Existenz einer natürlichen Zahl (auch Pumpingzahl genannt). Ansatz ist also
Sei \(N\in \mathbb{N}\).
Das Pumping Lemma fordert weiter, dass sich jedes Wort \(w\) mit \(|w|\geq N\) der Sprache auf gewisse Art zerlegen lässt. Man begibt sich jetzt also auf die Suche nach einem Wort und betrachtet alle Zerlegungen diese Wortes. Der Trick dabei ist, dass Wort so zu wählen, dass bei jeder Zerlegung das Aufpumpen zur Verletzung einer der Eigenschaften der Wörter der betrachteten Sprache führt.
\(a^{i} b^{j} c^{\lfloor k / 15\rfloor} b^{\lceil k / 3\rceil} a^{\lfloor k / 6\rfloor}\)
Sorge dafür, dass in dem aufpumpbaren Teil des Wortes ein Teil von \(c^{\lfloor k / 15\rfloor}\) vorkommt, aber \(b^{\lceil k / 3\rceil} a^{\lfloor k / 6\rfloor}\) nicht mehr vorkommt. Wähle dazu geeignete Werte für \(i\), \(j\) und \(k\) in Abhängigkeit von \(N\).
