Das Pumping Lemma (uvwxy-Theorem) 56

Sei $L$ eine reguläre Sprache. Dann gibt es eine Zahl $n\in\mathbb{N}$, sodass sich alle Wörter $z\in L$ mit $\left\vert z\right\vert\geq n$ zerlegen lassen als $x=uvwxy$ mit folgenden Eigenschaften:

1. $\left\vert vx\right\vert\geq1$
2. $\left\vert vwx\right\vert\leq n$
3. $\forall i\geq0:uv^{i}wx^{i}y\in L$

$$L\in\mathcal{L}_{2}\Rightarrow\left[\exists_{\mathbb{N}}^{n}:\lef... ...left(\forall i\geq0:\left(uv^{i}wx^{i}y\in L\right)\right)\right)\right)\right]$$

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

Die Kontraposition lautet wie folgt:

$$\left[\forall_{\mathbb{N}}^{n}:\left(\exists_{L}^{z}\left\vert z\... ...}y\notin L\right)\right)\right)\right)\right]\Rightarrow L\notin\mathcal{L}_{2}$$

Satz für einelementige Alphabete 62

Jede kontextfreie Sprache über einem einelementigen Alphabet ist bereits regulär.

Sprachen mit Wiederholungen

• Eine Sprache, bei der keine Exponenten in irgendwelchen Beziehungen zueinander stehen, sind (laut Pumping Lemma) regulär.
• Eine Sprache, bei der genau zwei Exponenten in irgendwelchen Beziehungen zueinander stehen, sind (laut Pumping Lemma) Kontext frei.
• Eine Sprache, bei der drei oder mehr Exponenten in irgendwelchen Beziehungen zueinander stehen, sind (laut Pumping Lemma) Kontext sensitiv.