Theoretische Informatik

Pumping-Lemma für kontextfreie Sprachen

 aufwärts

Um zu zeigen, dass eine Sprache kontextfrei ist, genügt es, eine kontextfreie Grammatik anzugeben, die sie erzeugt, oder einen Stack­automaten, der sie erkennt. Wie aber kann man zeigen, dass eine Sprache nicht kontextfrei ist?

Im Bereich der regulären Sprachen erweist sich das Pumping-Lemma für reguläre Sprachen als wichtiges Hilfsmittel für derartige Beweise. Ein ähnliches Pumping-Lemma gibt es auch für die kontext­freien Sprachen; es wird auch als uvwxy-Theorem bezeichnet.

Pumping-Lemma für kontextfreie Sprachen

Satz:  (Pumping-Lemma, uvwxy-Theorem)

Sei A ein Alphabet und L enthalten in A* eine kontextfreie Sprache. Dann lassen sich alle Wörter z Element L ab einer gewissen Länge |zgrößer gleich p (der Pumping-Länge) darstellen als

z  =  uvwxy

mit

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

|vx| > 0

|vwxkleiner gleich p

so dass gilt

uvkwxky Element L   für alle k Element natürliche Zahlen0.

Alle Wörter ab einer gewissen Länge p (der Pumping-Länge) enthalten also Teilwörter v und x, von denen mindestens eines nicht leer ist, die sich "aufpumpen" lassen – daher die Bezeichnung Pumping Lemma.

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

In einer kontext­freien Grammatik in Chomsky-Normalform hat jede Produktion die Form

Xgeht über nachYZ    oder
Xgeht über nacha

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

Der Ableitungs­baum für ein Wort z Element 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 Ableitungs­baum 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 = 2m+1. Dann hat jedes Wort z Element L der Länge |z|größer gleichp einen Ableitungs­baum mit einer Tiefe von mindestens m+2.

Wir betrachten nun einen Pfad maximaler Länge von der Wurzel des Ableitungs­baums 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
Bild 1: Ableitungsbaum für ein Wort der Länge größer gleichp

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 2m+1 = p.

Das obere Vorkommen von R entspricht der Anwendung einer Produktion der Form R  Pfeil nach rechts  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|kleiner gleichp 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 Ableitungs­baum für das Wort uvvwxxy = uv2wx2y (Bild 1c). Durch mehrfaches Wiederholen dieses Vorgangs lassen sich gültige Ableitungs­bäume für alle Wörter der Form uvkwxky mit k>0 erzeugen.

Ein Ableitungs­baum für das Wort uwy = uv0wx0y 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.

Anwendung

Satz:  Die Sprache L  =  { anbncn  |  n Element natürliche Zahlen } ist nicht kontextfrei.

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

Wir wählen z = apbpcp. Offenbar gilt z Element L und |z|größer gleichp.

Wegen |vwx|kleiner gleichp kann vwx nicht alle drei Zeichen a, b und c enthalten. Das fehlende Zeichen wird beim Aufpumpen zu uv2wx2y nicht verviel­fältigt. Da aber vx ≠ ε, werden die Zeichen, die in vx enthalten sind, verviel­fältigt. Somit hat uv2wx2y 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.

Aufgaben

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

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

ist nicht kontextfrei.

 

Weiter:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 26.01.2003   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik