Zum Inhalt springen

Beweisarchiv: Theoretische Informatik: Sprachen: Pumping-Lemma

Aus Wikibooks

Beweisarchiv: Theoretische Informatik

Sprachen: Pumping-Lemma
Berechenbarkeit: Halteproblem


Beweis für reguläre Sprachen

[Bearbeiten]

Voraussetzung

[Bearbeiten]

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

Behauptung

[Bearbeiten]

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:

  1. |v| ≥ 1
  2. |uv| ≤ n
  3. ∀ i ≥ 0: uviw ∈ L

Beweis

[Bearbeiten]

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 q1→...→qk, wobei qk 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 qi = qj. M durchläuft auf x also einen Zyklus.

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

  1. 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.
  2. 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.
  3. Durch wiederholtes Durchlaufen des Zyklus entstehen die Wörter uvvw, uvvvw, ..., uviw mit beliebigem i ≥ 1. Ferner kann der Zyklus auch ganz ausgelassen werden, wodurch das Wort uv0w = uw entsteht. Alle diese Wörter sind in L, da der deterministische endliche Automat seine Berechnung stets im akzeptierenden Endzustand beendet.