Pumpinglemma für Kontextfreie Sprachen

Einfache Sprache

Für die Anwendung hilf die Anwendung Pumpinglemma für Kontextfreie Sprachen

Def. Pumpinglemma für Kontextfreie Sprachen

Sei $A$ ein Alphabet und $L\subseteq A^*$ eine Sprache. Dann sind die beiden folgenden Aussagen äquivalent:

1. Die Sprache $L$ ist kontextfrei.
2. Die Sprache $L$ besitzt die Pumpingeigenschaft für Kontextfreie Sprachen.

Beweis: Sei $\mathcal G=(T,V,S,P)$ ein KFG in CNF (Chomsky-Normalform) mit $L-\{\varepsilon\}=L(\mathcal G)$ und $m = |V|$. Setze $n = 2^m$. Sei $z\in L$ mit $|z|\geq n$. Nach dem Satz Größe eines Syntaxbaum muss der Syntaxbaum von $z$, der einen Ertrag $z$ hat, also der Länge $|z|\geq n$, einen längsten Kantenzug mindestens $m+1$ haben. Dieser Kantenzug besteht aus den Knoten $A_0,\ldots,A_k,a$ mit $k\geq m$, $\forall i\in [0,k]:A_i\in V$ und $a\in T$. Da $k\geq m$ muss ein $i,j\in\mathbb N$ mit $k-m\leq i

Bemerke, dass $v$ und $x$ nicht beide gleichzeitig $\varepsilon$ sein können, da $\mathcal G$ in Chomsky-Normalform ist, genauer weil es kein unit-Produktionsregeln gibt.

Da nun $A_i = A_j = A$ können wir weitere Syntaxbäume aus dem Syntaxbaum von $z$, hier graphisch dargestellt #TODO insert images konstruieren.

So können wir beispielsweise den den Baum von $A_i$ durch den von $A_j$ ersetzen und erhalten folgenen Syntaxbaum , dessen Ertrag $uwy$ ist.

Andererseits können wir auch die Ableitung von $A$ nach $A$ beliebig oft wiederholen und erhalten beispielsweise den Syntaxbaum für 2 Wiederholungen , dessen Ertrag $uv^2wx^2y$ ist.

Es existieren also Syntaxbäume für alle Wörter der Form $uv^iwx^iy$ mit $i\in\mathbb N$.

Jetzt müssen wir noch zeigen, dass $|vwx|\leq n$. Da wir $i$ bzw. $A_i$ so gewählt haben, dass es nah an der Krone des Baumes ist, also $k-i \leq m$, wissen wir, dass der längste Kantenzug im Teilsyntaxbaum mit $A_i$ als Wurzel nicht länger als $m+1$ ist. Nach dem Satz Größe eines Syntaxbaum hat der $A_i$ also einen Ertrag kleiner als $2^{m}=n$.