Beweisarchiv: Theoretische Informatik: Sprachen: Pumping-Lemma

Beweis für reguläre Sprachen

Voraussetzung

Sei L eine reguläre Sprache also L ∈ L₃.

Behauptung

Es gibt eine natürliche Zahl n ∈ N, so dass für alle Wörter x ∈ L mit |x| ≥ n eine Zerlegung x = uvw existiert, für die gilt:

|v| ≥ 1
|uv| ≤ n
∀ i ≥ 0: uvⁱw ∈ L

Beweis

Falls L endlich ist, so existiert eine obere Schranke für die Länge der Wörter aus L. Es existiert also eine natürliche Zahl n ∈ N, für die gilt: |x| < n ∀ x ∈ L. Umgekehrt gilt, dass die Menge aller Wörter aus L, die länger als n sind, eine leere Menge ist: L' := {x ∈ L | |x| ≥ n} = ø. Da für leere Mengen Aussagen der Form „für alle Elemente der Menge gilt…“ trivialerweise immer erfüllt sind, ist auch die Behauptung für dieses n trivialerweise erfüllt. Das Pumping-emma ist also trivial, falls L endlich ist.

Sei daher L ohne Beschränkung der Allgemeinheit unendlich, dass heißt es existiert keine obere Schranke für die Länge der Wörter aus L. Oder anders formuliert: Für jedes Wort aus L findet sich immer ein anderes Wort aus L, das noch länger ist.

Da L regulär ist, existiert ein deterministischer endlicher Automat M, der L akzeptiert. Sei n := |M| die Anzahl der Zustände dieses Automaten. Weiter sei x ∈ L ein beliebiges Wort aus L mit mehr als n Zeichen, also |x| > n. Die Existenz eines solchen Wortes wurde im vorherigen Abschnitt sichergestellt.

Ohne Beschränkung der Allgemeinheit durchlaufe M auf x die Zustandsfolge q₁→...→q_k, wobei q_k der akzeptierende Endzustand sei. Da M weniger Zustände hat als x Zeichen enthält, durchläuft M auf x mindestens einen Zustand mehr als einmal, das heißt es existieren i ≠ j ∈ {1, ..., k} mit q_i = q_j. M durchläuft auf x also einen Zyklus.

Sei v der Teil von x, der durch Durchlaufen des Zyklus q_i→...→q_j entsteht. Ferner sei u der Teil von x, der durch die davor liegende Zustandsfolge q₁→...→q_i entsteht, w sei der Teil, der durch die dahinter liegende Zustandsfolge q_j→...→q_k entsteht. Es gilt also x = uvw. Für alle n ≥ |M| ist nun das Pumping-Lemma erfüllt:

Der erste Teil der Behauptung folgt direkt aus der Existenz des Zyklus. Da ein Zyklus aus mindestens einer Kante besteht und für jede Kante ein Zeichen hinzugefügt wird, gilt |v| ≥ 1.
Der zweite Teil der Behauptung folgt trivial aus der Wahl der Konstante n. Dadurch, dass n größer oder gleich der Anzahl der Zustände von M ist, kann |uv| unmöglich größer als n sein. Es ist allerdings durchaus möglich, dass u oder w leer sind.
Durch wiederholtes Durchlaufen des Zyklus entstehen die Wörter uvvw, uvvvw, ..., uvⁱw mit beliebigem i ≥ 1. Ferner kann der Zyklus auch ganz ausgelassen werden, wodurch das Wort uv⁰w = uw entsteht. Alle diese Wörter sind in L, da der deterministische endliche Automat seine Berechnung stets im akzeptierenden Endzustand beendet. $\Box$