Pumpingeigenschaft

Einfache Sprache

Def. Pumpingeigenschaft

Eine Sprache $L\subseteq A^*$ besitzt die Pumpingeigenschaft, falls es eine Zahl $m\in\mathbb N$ gibt, für die Folgendes gilt.

Jedes Wort $w \in A^m$ lässt sich schreiben als $w = xyz$ mit $x,z \in A^*$ und $y \in A^+$, sodass für alle $i \in \mathbb N$ und alle $v \in A^*$ gilt: $xyzv \in L$ genau dann, wenn $xy^izv \in L$.

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

Um zu Beweisen das eine Sprache nicht regulär ist, muss man die Negation der Pumpingeigenschaft beweisen.