Pumpingeigenschaft für Kontextfreie Sprachen

Einfache Sprache

Def. Pumpingeigenschaft für Kontextfreie Sprachen

Eine Sprache $L\subseteq A^*$ besitzt die Pumpingeigenschaft für Kontextfreie Sprachen, falls es eine Zahl $n\in\mathbb N$ existiert so, dass folgendes gilt.

Jedes Wort $z \in A^*$ mit $|z|\geq n$ lässt sich schreiben als $z = uvwxy$ mit $|vwx| \leq n$ und $vx\not=\varepsilon$. Weiter muss für alle $i \in \mathbb N$ gelten, dass $uv^iwx^iy \in L$.

Besitzt eine Sprache die Eigenschaft, so werden die Zahlen $n \in \mathbb N$, für die obige Bedingung gilt, Pumpingkonstanten für $L$ genannt.

Beweisschablone: Beweis