Ψ Die Informatikseite

Menü
Informatik » Bachelor » Theoretische Informatik » Reguläre Sprachen » Pumping Lemma für reguläre Sprachen
Algorithmen zur Feststellung von Eigenschaften Reguläre Sprachen Reguläre Ausdrücke
Unterabschnitte

Pumping Lemma für reguläre Sprachen

Definition

Sei $L\subseteq\Sigma^{*}$ eine reguläre Sprache. Dann gibt es eine ganze Zahl $n\geq 1$, so daß jedes Wort $\vert x\vert\geq n$ wie folgt zerlegt werden kann:
$x:=uvw$ mit Wörtern $u,v,w\in\Sigma^{*}$, so daß
  1. $\vert v\vert\geq 1$
  2. $\vert uv\vert\leq n\vert$
  3. $uv^{k}w\in L$ für alle $k\in\mathbb{N}$

Kernaussage

Die Kernaussage des Pumping Lemmas ist es, daß Autmaten keinen unbeschränkten Speicher haben, mit welchem sie zählen könnten. Es ist nicht möglich Sprachen von Typ (oder ähnlichen Typs)

\begin{displaymath}L=\{a^{n}b^{n}:n\in\mathbb{N}\}\end{displaymath}

mit einem DFA zu entscheiden, da er nicht festhalten kann, wie groß $n$ ist.

Beweis

Sei $x=a_{1}a_{2}\ldots a_{m}$ mit $\vert x\vert=m>n$ ein Wort in $L$, wobei $n$ die Anzahl der Zustände des DFAs.

Dann ist $q_{0}q_{1}\ldots q_{m}$ der Lauf im DFA, wobei $q_{m}\in F$.

Da die Anzahl der Zustände $n$ ist und der Lauf größer ist, müssen Zustände mehrfach besucht werden. D.h. wir gehen eine Schleife im Graphen für das Teilwort $v$.

Es gibt Indizes, so daß gilt ($0<i<j<n$)

\begin{displaymath}u=a_{1},a_{2},\ldots, a_{i}\,\,\,v=a_{i+1},\ldots,a_{j}\,\,\,w=a_{j+1},\ldots,a_{n}\end{displaymath}

  1. Wegen $i<j$ gilt $\vert v\vert\geq 1$
  2. Wegen $j\leq n$ gilt $\vert uv\vert=\vert a_{1},\ldots,a_{j}\vert=j\leq n$
  3. Wir können das Wort in $uv^{k}w$ unterteilen, da der Zustand zu dem Zeichen $a_{i+1}$ gehörig, mehrfach besucht wird und wir beliebig häufig diesen besuchen können.
Wegen $q_{m}\in F$ ist jedes dieser Worte in der Sprache enthalten.

Beispiele


  1. \begin{displaymath}L=\{a^{k}:k\in\mathbb{N}\}\end{displaymath}

    Diese Sprache ist regulär, da wir

    \begin{displaymath}u=a\,\,\,v=a\,\,\,w=a\end{displaymath}

    wählen können und Regel 1 erfüllt ist, daß $\vert v\vert\geq 1$, Regel 2 erfüllt ist, da $\vert uv\vert\leq n$ (jedes Wort hat mindestens 3 Zeichen) und Regel 3 auch erfüllt ist, da wir das $a$ beliebig wiederholen dürfen und das zusammengesetzte Wort immer noch in der Sprache ist.

  2. \begin{displaymath}L=\{a^{k}b^{l}:k,l\in\mathbb{N}\}\end{displaymath}

    Diese Sprache ist regulär, da wir

    \begin{displaymath}u=a\,\,\,v=a\,\,\,w=b^{l}\end{displaymath}

    wählen können und alle Regeln wiederum nicht verletzt sind, ganz besonders die Regel 3 nicht verletzt ist.

  3. \begin{displaymath}L=\{a\}\end{displaymath}

    Diese Sprache ist auch regulär, jedoch ist das einzige Wort welches gebildet werden kann nur 1 Zeichen lang, weshalb diese Sprache nicht mit dem Pumping Lemma überprüft werden kann, ob sie denn wirklich regulär ist.

  4. \begin{displaymath}L=\{a^{n}b^{n}:n\in\mathbb{N}\}\end{displaymath}

    Diese Sprache ist nicht regulär, da wir sie nicht richtig unterteilen können.

    Sei $n$ die Zahl aus dem Pumping Lemma. Da $\vert uv\vert\leq n$ kann $u$ nur aus $a$s bestehen. Dann muß $w=b^{n}$ sein. Da aber auch $v=a$, können auch Wörter $a^{n+l}b^{n}:l>0$ gebildet werden. Dies ist ein Widerspruch zu den Eigenschaften der oben definierten Sprache $L$.
Algorithmen zur Feststellung von Eigenschaften Reguläre Sprachen Reguläre Ausdrücke