Es gibt zwei Pumping-Lemmas, die für 1. reguläre Sprachen und 2. Kontext – freie Sprachen definiert sind Pumping-Lemma für reguläre Sprachen Für jede reguläre Sprache L gibt es eine ganze Zahl n, so dass für alle x ? L mit |x| ? n, es gibt u, v, w ? ?^*, so dass x = uvw und (1) |uv| ? n (2) |v| ? 1 (3) für alle i ? 0: UV^ichw ? L In einfachen Worten bedeutet dies, dass, wenn ein String v „gepumpt“ wird, d. h. wenn v beliebig oft eingefügt wird, der resultierende String immer noch in L bleibt. Das Pumping-Lemma wird als Beweis für die Unregelmäßigkeit einer Sprache verwendet. Wenn eine Sprache also regulär ist, erfüllt sie immer das Pumping-Lemma. Wenn es mindestens eine durch Pumpen erzeugte Zeichenfolge gibt, die nicht in L liegt, dann ist L sicherlich nicht regulär. Das Gegenteil davon ist möglicherweise nicht immer der Fall. Das heißt, wenn Pumping Lemma gilt, bedeutet das nicht, dass die Sprache regulär ist.

Beweisen wir zum Beispiel L₀₁= n ? 0 ist unregelmäßig. Nehmen wir an, dass L regulär ist, dann folgen durch Pumping Lemma die oben angegebenen Regeln. Sei nun x ? L und |x| ? N. Nach Pumping Lemma gibt es also u, v, w, so dass (1) – (3) gilt. Wir zeigen, dass für alle u, v, w (1) – (3) nicht gilt. Wenn (1) und (2) gelten, dann ist x = 0^N1^N= uvw mit |uv| ? n und |v| ? 1. Also, u = 0^A, v = 0^B, w = 0^C1^Nwo: a + b? n, b ? 1, c ? 0, a + b + c = n Aber dann schlägt (3) für i = 0 uv fehl⁰w = uw = 0^A0^C1^N= 0^{a + c}1^N? L, da a + c ? N.

Pumping Lemma für kontextfreie Sprachen (CFL) Das Pumping-Lemma für CFL besagt, dass es für jede kontextfreie Sprache L möglich ist, zwei Teilzeichenfolgen zu finden, die beliebig oft „gepumpt“ werden können und dennoch in derselben Sprache vorliegen. Für jede Sprache L zerlegen wir ihre Strings in fünf Teile und pumpen den zweiten und vierten Teilstring. Auch hier wird Pumping Lemma als Werkzeug verwendet, um zu beweisen, dass eine Sprache keine CFL ist. Denn wenn eine Zeichenfolge ihre Bedingungen nicht erfüllt, ist die Sprache keine CFL. Wenn also L eine CFL ist, gibt es eine ganze Zahl n, so dass für alle x ? L mit |x| ? n, es gibt u, v, w, x, y ? ?^*, so dass x = uvwxy und (1) |vwx| ? n (2) |vx| ? 1 (3) für alle i ? 0: UV^ichwx^ichUnd ? l

Für das obige Beispiel 0^N1^Nist CFL, da jede Zeichenfolge das Ergebnis des Pumpens an zwei Stellen sein kann, eine für 0 und eine für 1. Lassen Sie uns beweisen, dass L₀₁₂= n ? 0 ist nicht kontextfrei. Nehmen wir an, dass L kontextfrei ist, dann folgen durch Pumping Lemma die oben angegebenen Regeln. Sei nun x ? L und |x| ? N. Nach Pumping Lemma gibt es also u, v, w, x, y, so dass (1) – (3) gilt. Wir zeigen, dass für alle u, v, w, x, y (1) – (3) nicht gelten. Wenn (1) und (2) gelten, dann ist x = 0^N1^N2^N= uvwxy mit |vwx| ? n und |vx| ? 1. (1) sagt uns, dass vwx nicht sowohl 0 als auch 2 enthält. Daher hat entweder vwx keine Nullen oder vwx keine 2. Wir müssen also zwei Fälle betrachten. Angenommen, vwx hat keine Nullen. Nach (2) enthält vx eine 1 oder eine 2. Somit hat uwy „n“ Nullen und uwy entweder weniger als „n“ Einsen oder weniger als „n“ 2en. Aber (3) sagt uns, dass uwy = uv⁰wx⁰ja? L. Wenn uwy also eine gleiche Anzahl von Nullen, Einsen und Zweien hat, ergibt sich ein Widerspruch. Der Fall, in dem vwx keine 2 hat, ist ähnlich und führt ebenfalls zu einem Widerspruch. Somit ist L nicht kontextfrei. Quelle: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Einführung in die Automatentheorie, Sprachen und Berechnung.

Dieser Artikel wurde verfasst von Nirupam Singh .