Pumping Lemma

Wir stellen uns nun die Frage, ob es auch Sprachen gibt, die nicht durch einen Automaten akzeptiert werden können. Tatsächlich gibt es sehr viele Sprachen, die nicht von Automaten akzeptiert werden können. Sprachen, die von einem automaten akzeptiert werden, heißen reguläre Sprachen. Das Pumping Lemma gibt ein Kriterium an, das reguläre Sprachen erfüllen müssen.

Lemma: Für jede reguläre Sprache $L$ gibt es eine natürliche Zahl $n$, sodass für alle $z\in L$ mit $|z|>n$ eine Zerlegung $z=uvw$, sodass $|u|+|w|\le n$, $v\neq\varepsilon$ und für alle $i\in\mathbb{N}$ die Wörter $uv^iw\in L$ sind.

Beweis: Sei $L$ gegeben und regulär. Ist $L$ endlich, so erfüllt $n = 1 + \max\{|z|\mid z\in L\}$ die Prämisse bereits, da kein solches Wort existiert. Sei also $L$ unendlich und regulär und werde vom deterministischen endlichen Automaten $M$ mit Startzustand $q_0$ und Zustandsmenge $q_1,\ldots,q_{n-1}$ akzeptiert. Sei ein Wort $z\in L$ gegeben, sodass $|z|>n$. Werde nun $z$ akzeptiert durch den Lauf $q_{i_1}\rightarrow \ldots \rightarrow q_{i_{|z|}}$, wobei $q_{i_{|z|}}$ ein Endzustand ist. Da es nur $n$ Zustände gibt, muss in diesem Lauf mindestens ein Zustand doppelt vorkommen, also müssen $k,l$ mit $k<l$ existieren, sodass $q_{i_k} = q_{i_l}$.

Das heißt, wir haben einen Lauf der Form $\underbrace{q_{i_1}\rightarrow\ldots\rightarrow}_u \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v\underbrace{\rightarrow\ldots\rightarrow q_{i_{|z|}}}_w$. Dann ist aber auch der Lauf $\underbrace{q_{i_1}\rightarrow\ldots\rightarrow}_u q_{i_k} \underbrace{\rightarrow\ldots\rightarrow q_{i_{|z|}}}_w$ korrekt, und Läufe der Form $\underbrace{q_{i_1}\rightarrow\ldots\rightarrow}_u \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v \ldots \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v\underbrace{\rightarrow\ldots\rightarrow q_{i_{|z|}}}_w$. QED.