Theoretische Informatik

Satz:  (Pumping-Lemma, uvwxy-Theorem)

Sei A ein Alphabet und L ⊆ A* eine kontextfreie Sprache. Dann lassen sich alle Wörter z ∈ L ab einer gewissen Länge |z| ≥ p (der Pumping-Länge) darstellen als

z  =  uvwxy

mit

u, v, w, x, y ∈ A*

|vx| > 0

|vwx| ≤ p

sodass gilt

uv^kwx^ky ∈ L   für alle k ∈ ℕ₀.

Beweis:  Sei G = (V, T, P, S) eine kontextfreie Grammatik in Chomsky-Normalform für die Sprache L.

In einer kontextfreien Grammatik in Chomsky-Normalform hat jede Produktion die Form

mit X, Y, Z ∈ V und a ∈ T.

Der Ableitungsbaum für ein Wort z ∈ L ist somit ein binärer Baum, dessen Blätter die einzelnen Zeichen des Wortes z sind. Ist p die Länge des Wortes z, so hat also der binäre Baum p Blätter.

Ein binärer Baum mit p Blättern hat eine Tiefe von mindestens log(p). Der Ableitungsbaum hat sogar eine Tiefe von mindestens log(p)+1, da jedes Blatt nur einen Vorgänger im Baum hat.

Sei nun m die Anzahl der Variablen in G, d.h. m = |V|, und sei p = 2^m+1. Dann hat jedes Wort z ∈ L der Länge |z| ≥ p einen Ableitungsbaum mit einer Tiefe von mindestens m+2.

Wir betrachten nun einen Pfad maximaler Länge von der Wurzel des Ableitungsbaums zu einem Blatt. Das Endstück q der Länge m+2 dieses Pfades enthält m+1 Vorkommen von Variablen. Unter diesen muss sich eine Variable R befinden, die dort mehrfach vorkommt, denn die Grammatik hat nur m verschiedene Variablen (Bild 1a).

Wie in Bild 1b zu sehen, erzeugt das unterste Vorkommen der Variablen R auf dem Pfad q das Teilwort w. Das nächsthöhere Vorkommen von R auf q erzeugt das Teilwort vwx.

 

 

Bild 1: Ableitungsbaum für ein Wort der Länge  ≥ p

 

Die Tiefe des Teilbaums, der von diesem oberen Vorkommen von R erzeugt wird, beträgt höchstens m+2, denn es gibt keinen Pfad der Länge  >  m+2 von dort zu einem Blatt. Daher beträgt die Länge von vwx höchstens 2^m+1 = p.

Das obere Vorkommen von R entspricht der Anwendung einer Produktion der Form R  →  YZ. Damit muss sich vor oder hinter dem Teilwort w, das vom unteren Vorkommen von R erzeugt wird, noch ein nichtleeres Teilwort v bzw. x befinden.

Damit sind die beiden Bedingungen |vx| > 0 und |vwx| ≤ p erfüllt.

Indem nun der Teilbaum, der vom oberen Vorkommen von R erzeugt wird, an die Stelle des Teilbaums, der vom unteren Vorkommen von R erzeugt wird, gesetzt wird, entsteht ein gültiger Ableitungsbaum für das Wort uvvwxxy = uv²wx²y (Bild 1c). Durch mehrfaches Wiederholen dieses Vorgangs lassen sich gültige Ableitungsbäume für alle Wörter der Form uv^kwx^ky mit k > 0 erzeugen.

Ein Ableitungsbaum für das Wort uwy = uv⁰wx⁰y lässt sich erzeugen, indem der Teilbaum, der vom unteren Vorkommen von R erzeugt wird, an die Stelle des Teilbaums, der vom oberen Vorkommen von R erzeugt wird, gesetzt wird.

Satz:  Die Sprache L  =  { aⁿbⁿcⁿ  |  n ∈ ℕ } ist nicht kontextfrei.

Beweis:  Angenommen, L wäre kontextfrei. Dann gilt das Pumping-Lemma, d.h. jedes Wort z ∈ L ab einer gewissen Pumping-Länge p lässt sich in der angegebenen Weise in uvwxy zerlegen und so aufpumpen, dass uv²wx²y ∈ L gilt.

Wir wählen z = a^pb^pc^p. Offenbar gilt z ∈ L und |z| ≥ p.

Wegen |vwx| ≤ p kann vwx nicht alle drei Zeichen a, b und c enthalten. Das fehlende Zeichen wird beim Aufpumpen zu uv²wx²y nicht vervielfältigt. Da aber vx ≠ ε, werden die Zeichen, die in vx enthalten sind, vervielfältigt. Somit hat uv²wx²y nicht mehr gleich viele a's, b's und c's und ist daher nicht Element der Sprache L, im Widerspruch zur Aussage des Pumping-Lemmas. Daher muss die Annahme falsch sein, d.h. L ist nicht kontextfrei.

Aufgabe 1:  Zeigen Sie durch Anwendung des Pumping-Lemmas für kontextfreie Sprachen: Die Sprache

L  =  { ww  |  w ∈ {a, b}* }

ist nicht kontextfrei.