Martin Thoma

Reguläre Sprachen können von endlichen Automaten erkannt werden. Das bedeutet, dass eine endliche Anzahl an Zuständen ausreicht, um ein Wort der Sprache zu akzeptieren. Wenn also eine Sprache \(L = \{a^i b^{2i} | i \in \mathbb{N}\}\) beschrieben wird, müsste gezählt werden, wie oft a vorkommt. a kann aber beliebig oft vorkommen. Das ist ein Indiz dafür, dass es sich nicht um eine reguläre Sprache handelt.

Das Pumping-Lemma ist ein notwendiges, aber kein hinreichendes Kriterium für reguläre Sprachen. Daraus folgt, dass eine nicht-reguläre Sprache eventuell durch das Lemma entlarvt werden kann. Allerdings muss nicht jede Sprache, die das Pumping-Lemma erfüllt, regulär sein.

Dies kann man durch einen Widerspruchsbeweis zeigen. Dabei nimmt man an, dass die Behauptung falsch ist. Dann zeigt man, dass man durch die Annahme zu einem Widerspruch kommt.

Beispiel

Voraussetzung:

\(L_2 = \{a^i b^j c^k | i \lt j \lt k\}\).

Behauptung: \(L_2\) ist nicht regulär.

Beweis: (durch Widerspruch)

Annahme: \(L_2\) sei regulär.

Aus dem Pumping-Lemma folgt:
\(\exists n \in \mathbb{N}: \forall w \in \{w \in L_2 | |w| \geq n\}: \)
\(\exists \text{ Darstellung } uvx = w \text{ mit } v \neq \varepsilon \land |uv| \leq n\) für die gilt:

In Worten: Wenn man ein Wort in L hat, dass mindestens so lang ist wie ein bestimmtes n, dann kann man dieses Wort in Teilworte u, v und x zerlegen. Bei dieser Zerlegung ist v niemals leer. Wenn man nun den Teil des Wortes, der in v steckt wiederholt, muss das Wort immer noch in \(L_2\) sein.

Sei \(n \in \mathbb{N}\) die Konstante aus dem Pumping-Lemma.

Betrachte nun \(w = a^n b^{n+1} c^{n+2}\). Offensichtlich gilt \(w \in L_2\). Da \(|uv| \leq n\) muss in v mindestens ein a sein.

\(\Rightarrow uv^2 x = a^{n+2 \cdot i} b^{n+1} c^{n+2}, i \geq 1 \)
\(\Rightarrow uv^2x \notin L_2 \)
\(\Rightarrow \text{Widerspruch} \)
\(\Rightarrow \text{Die Annahme war falsch.} \)
\(\Rightarrow L_2\) ist nicht regulär.

Bemerkung: Eigentlich ist es ein Beweis durch Kontraposition. Man weiß, es gilt:
\(L \in {\cal L_3} \Rightarrow \) L erfüllt das Pumping-Lemma.
Daraus folgt:
L erfüllt nicht das Pumping-Lemma \(\Rightarrow L \notin {\cal L_3}\).
Um zu beweisen, dass L das Pumping-Lemma nicht erfüllt, benutzt man meist einen Widerspruchsbeweis wie oben.

Material

Ich habe mal ein paar Beispiele für Ogdens Lemma und das Pumping-Lemma gesammelt.

Be Sociable, Share!

•