Informatik

Die Pumpeigenschaft (Pumping Lemma) besagt, dass für jede reguläre Sprache $L$ eine natürliche Zahl $n$ (die Pump-Länge) existiert, für die jedes Wort $w \in L$, dessen Länge $|w| \ge n$ ist, in drei Teile $w = xyz$ zerlegt werden kann, sodass die folgenden Bedingungen erfüllt sind:

1. $|xy| \le n$
   ($xy$ ist nicht länger als die Pump-Länge)
2. $|y| \ge 1$
   ($y$ ist nicht leer)
3. Für alle $k \ge 0$ ist $xy^kz \in L$
   ($y$ kann beliebig oft gepumpt werden, und das resultierende Wort bleibt in $L$)

Erklärung

Die Pumpeigenschaft ist ein wichtiges Werkzeug in der theoretischen Informatik, um zu beweisen, dass eine gegebene Sprache nicht regulär ist. Dies geschieht in der Regel durch einen Widerspruchsbeweis:

1. Man nimmt an, dass die Sprache $L$ regulär ist.
2. Aufgrund der Pumpeigenschaft muss dann eine Pump-Länge $n$ existieren.
3. Man wählt ein geeignetes Wort $w \in L$ mit $|w| \ge n$, dessen Struktur einen Widerspruch beim Pumpen ermöglicht.
4. Man zeigt, dass das Pumpen des Wortes $w$ (d.h., die Erzeugung von $xy^kz$ für ein geeignetes $k$) ein Wort erzeugt, das nicht in $L$ enthalten ist.
5. Da dies ein Widerspruch zur Annahme ist, muss die ursprüngliche Annahme falsch sein, und die Sprache $L$ ist folglich nicht regulär.

Beispiel

Die Sprache $L = \{a^k b^k \mid k \ge 0\}$ ist nicht regulär.

Beweis (skizziert):

1. Angenommen, $L$ ist regulär. Dann existiert eine Pump-Länge $n$.
2. Wähle das Wort $w = a^n b^n \in L$. Offensichtlich ist $|w| = 2n \ge n$.
3. Gemäß der Pumpeigenschaft kann $w$ in $xyz$ zerlegt werden mit $|xy| \le n$ und $|y| \ge 1$.
4. Da $|xy| \le n$ und $w = a^n b^n$, muss der Teil $xy$ vollständig aus $a$'s bestehen. Das bedeutet, $y$ besteht ebenfalls nur aus $a$'s ($y = a^m$ für $m \ge 1$).
5. Betrachte nun das Wort $xy^2z$. Dies würde bedeuten, wir fügen weitere $a$'s zum Wort hinzu. Das neue Wort hat die Form $a^{n+m} b^n$.
6. Da $m \ge 1$, ist $n+m \ne n$. Somit ist die Anzahl der $a$'s ungleich der Anzahl der $b$'s.
7. Das Wort $a^{n+m} b^n$ ist nicht in $L$. Dies ist ein Widerspruch zur Pumpeigenschaft.

Daher ist die Sprache $L = \{a^k b^k \mid k \ge 0\}$ nicht regulär.