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.

Beispiele

• Die Sprache $\{a^kb^k\mid k\in\mathbb{N}\}$ ist nicht regulär, wie man leicht mit dem Pumpinglemma sieht.
• Die Sprache $\{a^p\mid p \mbox{ Prim}\}$ ist nicht regulär, denn sonst müsste es zu jeder Primzahl $p$ zahlen $q,r<p$ geben, sodass alle $q+nr$ ebenfalls prim sind.
• Das Pumpinglemma ist eine notwendige, aber keine hinreichende Bedingung, damit eine Sprache regulär ist. Die Sprache der korrekten Klammerungen sei rekursiv definiert durch
  • $()$ ist eine korrekte Klammerung
  • Ist $k$ eine korrekte Klammerung, so auch $(k)$
  • Sind $k$ und $l$ korrekte Klammerungen, so auch $kl$

Jedes Wort enthält die Teilzeichenkette $()$, die beliebig oft wiederholbar ist. Also erfüllt diese Sprache das Pumping-Lemma. Sie ist aber trotzdem nicht regulär: Angenommen ein Automat $M$ mit $n$ Zuständen akzeptiere genau diese Sprache. Dann muss $M$ auch $(^{n+1})^{n+1}$ akzeptieren. Dann muss es, analog zum Beweis des Pumpinglemma, einen Lauf geben, der $(^{n+1}$ matcht (aber nicht in einem Endzustand endet), und dieser muss mindestens eine Wiederholung enthalten. Diese Wiederholung matcht dann auf einen Ausdruck $(^k$, und das bedeutet, dass dann auch das Wort $(^{n+1+k})^{n+1}$ gematcht wird, welches kein korrekt geklammerter Ausdruck mehr ist. Die Sprache kann also nicht regulär sein.