next up previous contents index
Next: Äquivalenzrelation und Minimalautomat 42 Up: Reguläre Sprachen (Typ 3) Previous: Reguläre Ausdrücke 36   Contents   Index


Das Pumping Lemma 39

Das Pumping Lemma (Schleifenlemma, Lemma von Bar-Hillel, $ uvw$-Theorem) ist ein wichtiges Hilfsmittel, um zu Zeigen, das eine Sprache nicht regulär ist.

Sei $ L$ eine reguläre Sprache. Dann gibt es eine Zahl $ n$, so dass sich alle Wörter $ x\in L$ mit $ \left\vert x\right\vert\geq n$ zerlegen lassen in $ x=uvw$, so dass folgende Eigenschaften erfüllt sind:

Es gibt auch Sprachen die das Pumping Lemma erfüllen, und nicht regulär sind. Das bedeutet, das mit dem Pumping Lemma nur das nicht regulärsein von Sprachen gezeigt werden kann.

$\displaystyle L\in\mathcal{L}_{3}\Rightarrow\left[\exists_{\mathbb{N}}^{n}:\lef...
...eq n:\left(\forall i\geq0:\left(uv^{i}w\in L\right)\right)\right)\right)\right]$

Umgekehrt gilt:

$\displaystyle \left[\forall_{\mathbb{N}}^{n}:\left(\exists_{L}^{x}\left\vert x\...
...}w\notin L\right)\right)\right)\right)\right]\Rightarrow L\notin\mathcal{L}_{3}$



Marco Möller 18:11:27 24.10.2005