Zum Inhalt springen

Kontextfreie Grammatik

Aus FLBK-Wiki

Kontextfreie Grammatiken beschreiben verschachtelte Strukturen wie Klammern und Programmblöcke. Dafür reichen reguläre Sprachen nicht aus.

Definition

Eine kontextfreie Grammatik ist eine formale Grammatik [math]\displaystyle{ G = (N; T; P; S) }[/math], deren Regeln links genau ein Nichtterminal haben:

[math]\displaystyle{ A \to \beta }[/math] mit [math]\displaystyle{ A \in N }[/math] und [math]\displaystyle{ \beta \in (N \cup T)^* }[/math]

Die rechte Seite [math]\displaystyle{ \beta }[/math] ist eine beliebige, auch leere Folge aus Nichtterminalen und Terminalen. Weil links nur ein einzelnes Nichtterminal steht, ersetzt die Regel es unabhängig vom Umfeld, dem Kontext. Die erzeugten Sprachen heißen kontextfreie Sprachen. Sie bilden Typ 2 der Chomsky-Hierarchie. Passende Automaten sind die Kellerautomaten.

Jede reguläre und jede rechtslineare Grammatik ist auch kontextfrei, denn ihre Regeln haben ebenfalls die Form [math]\displaystyle{ A \to \beta }[/math].

Enthält eine Zeichenfolge mehrere Nichtterminale, lässt sich die Reihenfolge der Ersetzungen wählen. Zwei Reihenfolgen haben eigene Namen:

  • Die Linksableitung ersetzt in jedem Schritt das am weitesten links stehende Nichtterminal.
  • Die Rechtsableitung ersetzt in jedem Schritt das am weitesten rechts stehende Nichtterminal.

Ableitungsbaum

Ein Ableitungsbaum (auch Syntaxbaum) zeigt, wie ein Wort aus dem Startsymbol entsteht:

  • Die Wurzel ist das Startsymbol.
  • Jeder innere Knoten ist ein Nichtterminal. Seine Kinder sind, von links nach rechts, die Symbole der rechten Seite der angewendeten Regel. Bei einer Regel [math]\displaystyle{ A \to \varepsilon }[/math] ist [math]\displaystyle{ \varepsilon }[/math] das einzige Kind.
  • Die Blätter ergeben von links nach rechts gelesen das Wort.

Zu jedem Ableitungsbaum gibt es genau eine Linksableitung und genau eine Rechtsableitung. Sie unterscheiden sich nur in der Reihenfolge, in der die Knoten ersetzt werden. Auch der Artikel Syntax erklärt den Ableitungsbaum am Satzbau.

Mehrdeutigkeit

Eine kontextfreie Grammatik ist eindeutig, wenn jedes Wort ihrer Sprache genau einen Ableitungsbaum hat. Sie ist mehrdeutig, wenn es für mindestens ein Wort zwei verschiedene Ableitungsbäume gibt. Das ist gleichbedeutend damit, dass das Wort zwei verschiedene Linksableitungen hat. Eine Linksableitung und eine Rechtsableitung desselben Baums sind dagegen keine Mehrdeutigkeit.

Bei einem mehrdeutigen Wort legt die Grammatik nicht fest, welche Struktur gemeint ist. Mehrdeutigkeit ist eine Eigenschaft der Grammatik, nicht der Sprache: Dieselbe Sprache kann sowohl durch eine mehrdeutige als auch durch eine eindeutige Grammatik beschrieben werden. Oft lässt sich die Mehrdeutigkeit beseitigen, indem die Regeln eine feste Reihenfolge des Aufbaus erzwingen. Es gibt allerdings auch kontextfreie Sprachen, für die jede Grammatik mehrdeutig ist. Solche Sprachen heißen inhärent mehrdeutig.

Konstruktionsmuster

Beim Konstruieren einer kontextfreien Grammatik helfen wenige Muster, die sich kombinieren lassen:

  • Paare von außen nach innen: Eine Regel der Form [math]\displaystyle{ A \to aAb }[/math] erzeugt bei jeder Anwendung links und rechts je ein Zeichen. So entstehen auf beiden Seiten gleich viele Zeichen.
  • Abschluss: Eine Regel ohne Nichtterminal beendet die Ableitung. Sie legt fest, was in der Mitte steht und wie das kürzeste Wort aussieht.
  • Wiederholung: Eine Regel der Form [math]\displaystyle{ A \to aA }[/math] hängt beliebig viele Zeichen an, wie bei einer regulären Grammatik.
  • Hintereinander: Eine Regel der Form [math]\displaystyle{ S \to AB }[/math] setzt zwei Teile hintereinander, die unabhängig voneinander erzeugt werden.

Nach dem Konstruieren wird die Grammatik geprüft: Die kürzesten Wörter der Sprache müssen ableitbar sein, und es darf sich kein Wort ableiten lassen, das nicht zur Sprache gehört.

Grenzen regulärer Sprachen

Ein DEA hat endlich viele Zustände und kann deshalb nicht beliebig weit zählen. Der Grund:

  • Hat der DEA [math]\displaystyle{ k }[/math] Zustände, durchläuft er beim Lesen von [math]\displaystyle{ k }[/math] Zeichen [math]\displaystyle{ k + 1 }[/math] Zustände. Also kommt ein Zustand mindestens zweimal vor. Das ist das Schubfachprinzip: Verteilt man [math]\displaystyle{ k + 1 }[/math] Dinge auf [math]\displaystyle{ k }[/math] Fächer, liegen in mindestens einem Fach zwei Dinge.
  • Zwischen den beiden Besuchen desselben Zustands liest der DEA [math]\displaystyle{ j \geq 1 }[/math] Zeichen und kehrt dabei zu diesem Zustand zurück. Dieser Rundweg heißt hier Schleife, auch wenn er über mehrere Zustände führt. Er lässt sich beliebig oft durchlaufen oder ganz auslassen. Danach ist der Automat jedes Mal im selben Zustand.
  • Der DEA kann deshalb nicht unterscheiden, wie oft die Schleife durchlaufen wurde. Die gelesene Anzahl geht verloren.

Verlangt eine Sprache, dass eine unbegrenzte Anzahl mitgezählt wird, erkennt kein DEA sie: Die Sprache ist nicht regulär. Der Nachweis ist ein Widerspruchsbeweis. Man nimmt an, ein DEA mit [math]\displaystyle{ k }[/math] Zuständen erkenne die Sprache, und zeigt, dass er dann auch ein Wort akzeptiert, das nicht zur Sprache gehört. Je nach Sprache entsteht dieses Wort, indem die Schleife einmal mehr durchlaufen oder ausgelassen wird.

Eine kontextfreie Grammatik kann solche Anzahlen vergleichen, weil eine Regel das Nichtterminal in der Mitte der rechten Seite stehen lassen kann ([math]\displaystyle{ A \to \beta_1 A \beta_2 }[/math]). Dann entstehen links und rechts davon gleichzeitig neue Zeichen.

Jede reguläre Sprache ist kontextfrei. Die Umkehrung gilt nicht.

Pumping-Lemma

Das Pumping-Lemma beschreibt eine Eigenschaft, die jede reguläre Sprache hat. Ein Lemma ist ein Hilfssatz, also ein Satz, der vor allem als Werkzeug für andere Beweise dient. Zu jeder regulären Sprache [math]\displaystyle{ L }[/math] gibt es eine Zahl [math]\displaystyle{ k \geq 1 }[/math], sodass jedes Wort [math]\displaystyle{ w \in L }[/math] mit der Wortlänge [math]\displaystyle{ |w| \geq k }[/math] eine Zerlegung [math]\displaystyle{ w = xyz }[/math] hat mit

  • [math]\displaystyle{ |xy| \leq k }[/math],
  • [math]\displaystyle{ |y| \geq 1 }[/math] und
  • [math]\displaystyle{ xy^iz \in L }[/math] für alle [math]\displaystyle{ i \geq 0 }[/math].

Der Teil [math]\displaystyle{ y }[/math] lässt sich also beliebig oft wiederholen („aufpumpen“) oder weglassen ([math]\displaystyle{ i = 0 }[/math]), ohne dass das Wort die Sprache verlässt. [math]\displaystyle{ y^i }[/math] ist dabei eine Wortpotenz. Das Lemma fasst die Überlegung aus dem Abschnitt Grenzen regulärer Sprachen zusammen: [math]\displaystyle{ k }[/math] ist die Anzahl der Zustände eines DEA für [math]\displaystyle{ L }[/math], und [math]\displaystyle{ y }[/math] ist der Teil des Wortes, der in der Schleife gelesen wird.

Das Lemma dient dem Nachweis, dass eine Sprache nicht regulär ist. Es ist nur eine notwendige Bedingung: Erfüllt eine Sprache das Lemma, folgt daraus nicht, dass sie regulär ist. Der Nachweis verläuft so:

  1. Annahme: [math]\displaystyle{ L }[/math] ist regulär. Dann gibt es eine Zahl [math]\displaystyle{ k }[/math] wie im Lemma.
  2. Ein Wort [math]\displaystyle{ w \in L }[/math] mit [math]\displaystyle{ |w| \geq k }[/math] wählen, abhängig von [math]\displaystyle{ k }[/math].
  3. Das Lemma liefert eine Zerlegung [math]\displaystyle{ w = xyz }[/math], die nicht frei wählbar ist. Wegen [math]\displaystyle{ |xy| \leq k }[/math] liegt [math]\displaystyle{ y }[/math] im vorderen Teil von [math]\displaystyle{ w }[/math].
  4. Für jede solche Zerlegung ein [math]\displaystyle{ i }[/math] mit [math]\displaystyle{ xy^iz \notin L }[/math] zeigen. Das widerspricht dem Lemma. Also ist [math]\displaystyle{ L }[/math] nicht regulär.

Beispiele

Klammerausdrücke ableiten

Die Grammatik mit dem Startsymbol [math]\displaystyle{ S }[/math] und den Terminalen [math]\displaystyle{ ( }[/math] und [math]\displaystyle{ ) }[/math] erzeugt korrekt geklammerte Ausdrücke. Ihre Regeln:

[math]\displaystyle{ S \to (S)S \mid \varepsilon }[/math]

Die Regel [math]\displaystyle{ S \to (S)S }[/math] setzt ein Klammerpaar, in dem ein Ausdruck steht, und lässt einen weiteren Ausdruck folgen. Die Regel [math]\displaystyle{ S \to \varepsilon }[/math] lässt ein [math]\displaystyle{ S }[/math] verschwinden. Das Wort [math]\displaystyle{ ()() }[/math] wird einmal als Linksableitung und einmal als Rechtsableitung abgeleitet.

Die Linksableitung ersetzt immer das am weitesten links stehende [math]\displaystyle{ S }[/math]:

[math]\displaystyle{ S \Rightarrow (S)S \Rightarrow ()S \Rightarrow ()(S)S \Rightarrow ()()S \Rightarrow ()() }[/math]

Die Rechtsableitung ersetzt immer das am weitesten rechts stehende [math]\displaystyle{ S }[/math]:

[math]\displaystyle{ S \Rightarrow (S)S \Rightarrow (S)(S)S \Rightarrow (S)(S) \Rightarrow (S)() \Rightarrow ()() }[/math]
Ableitungsbaum des Wortes ()()

Der Ableitungsbaum entsteht Schritt für Schritt aus der Linksableitung. Jeder Ableitungsschritt hängt unter das ersetzte [math]\displaystyle{ S }[/math] die Zeichen der rechten Regelseite:

  1. [math]\displaystyle{ S \Rightarrow (S)S }[/math]: Die Wurzel [math]\displaystyle{ S }[/math] erhält die Kinder [math]\displaystyle{ ( }[/math], [math]\displaystyle{ S }[/math], [math]\displaystyle{ ) }[/math] und [math]\displaystyle{ S }[/math].
  2. [math]\displaystyle{ (S)S \Rightarrow ()S }[/math]: Das am weitesten links stehende [math]\displaystyle{ S }[/math] erhält das Kind [math]\displaystyle{ \varepsilon }[/math].
  3. [math]\displaystyle{ ()S \Rightarrow ()(S)S }[/math]: Das am weitesten links stehende [math]\displaystyle{ S }[/math] erhält die Kinder [math]\displaystyle{ ( }[/math], [math]\displaystyle{ S }[/math], [math]\displaystyle{ ) }[/math] und [math]\displaystyle{ S }[/math].
  4. [math]\displaystyle{ ()(S)S \Rightarrow ()()S }[/math]: Das am weitesten links stehende [math]\displaystyle{ S }[/math] erhält das Kind [math]\displaystyle{ \varepsilon }[/math].
  5. [math]\displaystyle{ ()()S \Rightarrow ()() }[/math]: Das am weitesten links stehende [math]\displaystyle{ S }[/math] erhält das Kind [math]\displaystyle{ \varepsilon }[/math].

Die Blätter ergeben von links nach rechts [math]\displaystyle{ ()() }[/math]. Die Rechtsableitung führt zu demselben Baum, sie ersetzt die Knoten nur in anderer Reihenfolge. Zwei Ableitungen mit demselben Baum sind keine Mehrdeutigkeit. Einen zweiten Baum gibt es für [math]\displaystyle{ ()() }[/math] nicht: Jede öffnende Klammer entsteht zusammen mit ihrer schließenden aus derselben Regel, und welche Klammern zusammengehören, steht im Wort fest.

Nichtzugehörigkeit begründen

Gehört das Wort [math]\displaystyle{ (() }[/math] zur Sprache der Grammatik [math]\displaystyle{ S \to (S)S \mid \varepsilon }[/math]? Nein. Die Regel [math]\displaystyle{ S \to (S)S }[/math] erzeugt je eine öffnende und eine schließende Klammer, die Regel [math]\displaystyle{ S \to \varepsilon }[/math] keine. Jede Ableitung erzeugt deshalb gleich viele öffnende und schließende Klammern. Das Wort [math]\displaystyle{ (() }[/math] hat zwei öffnende und nur eine schließende Klammer. Es gehört nicht zur Sprache.

Kontextfreie Grammatik konstruieren

Gesucht ist eine kontextfreie Grammatik für die Sprache [math]\displaystyle{ L = \{K^n E^{n+1} \mid n \geq 0\} }[/math] über [math]\displaystyle{ \Sigma = \{K; E\} }[/math]: erst [math]\displaystyle{ n }[/math]-mal [math]\displaystyle{ K }[/math], danach ein [math]\displaystyle{ E }[/math] mehr.

Schritt 1: Kürzeste Wörter aufschreiben. Für [math]\displaystyle{ n = 0 }[/math], [math]\displaystyle{ n = 1 }[/math] und [math]\displaystyle{ n = 2 }[/math] entstehen [math]\displaystyle{ E }[/math], [math]\displaystyle{ KEE }[/math] und [math]\displaystyle{ KKEEE }[/math].

Schritt 2: Aufbau erkennen. Von einem Wort zum nächsten kommt vorn ein [math]\displaystyle{ K }[/math] und hinten ein [math]\displaystyle{ E }[/math] hinzu. In der Mitte bleibt immer ein einzelnes [math]\displaystyle{ E }[/math]. Das passt zum Muster „Paare von außen nach innen“ mit dem Abschluss [math]\displaystyle{ E }[/math].

Schritt 3: Regeln aufstellen.

[math]\displaystyle{ S \to KSE \mid E }[/math]

Schritt 4: Prüfen. Das kürzeste Wort [math]\displaystyle{ E }[/math] entsteht direkt aus der zweiten Regel. Für [math]\displaystyle{ KKEEE }[/math] gilt:

[math]\displaystyle{ S \Rightarrow KSE \Rightarrow KKSEE \Rightarrow KKEEE }[/math]

Jede Anwendung der ersten Regel erzeugt genau ein [math]\displaystyle{ K }[/math] und ein [math]\displaystyle{ E }[/math], die zweite Regel erzeugt das zusätzliche [math]\displaystyle{ E }[/math]. Andere Wörter als die der Sprache lassen sich nicht ableiten. Die Grammatik ist kontextfrei, aber nicht rechtslinear, weil in [math]\displaystyle{ S \to KSE }[/math] das Nichtterminal in der Mitte steht.

Grammatik aus Teilen zusammensetzen

Gesucht ist eine kontextfreie Grammatik für die Sprache [math]\displaystyle{ L = \{K^n E^n K^m \mid n \geq 1 \text{ und } m \geq 0\} }[/math] über [math]\displaystyle{ \Sigma = \{K; E\} }[/math]: zuerst gleich viele [math]\displaystyle{ K }[/math] und [math]\displaystyle{ E }[/math], danach beliebig viele [math]\displaystyle{ K }[/math]. Zur Sprache gehören zum Beispiel [math]\displaystyle{ KE }[/math], [math]\displaystyle{ KEK }[/math] und [math]\displaystyle{ KKEEKKK }[/math].

Schritt 1: Wort in Teile zerlegen. Jedes Wort besteht aus zwei Teilen, die unabhängig voneinander sind: Der vordere Teil [math]\displaystyle{ K^n E^n }[/math] braucht gleich viele [math]\displaystyle{ K }[/math] und [math]\displaystyle{ E }[/math]. Der hintere Teil [math]\displaystyle{ K^m }[/math] ist eine beliebige Wiederholung.

Schritt 2: Für jeden Teil ein Nichtterminal wählen. [math]\displaystyle{ A }[/math] erzeugt den vorderen Teil nach dem Muster „Paare von außen nach innen“ mit dem Abschluss [math]\displaystyle{ KE }[/math]. [math]\displaystyle{ B }[/math] erzeugt den hinteren Teil nach dem Muster „Wiederholung“ mit dem Abschluss [math]\displaystyle{ \varepsilon }[/math].

Schritt 3: Teile hintereinandersetzen. Das Startsymbol setzt beide Teile mit der Regel [math]\displaystyle{ S \to AB }[/math] hintereinander:

[math]\displaystyle{ S \to AB }[/math]
[math]\displaystyle{ A \to KAE \mid KE }[/math]
[math]\displaystyle{ B \to KB \mid \varepsilon }[/math]

Schritt 4: Prüfen. Das kürzeste Wort [math]\displaystyle{ KE }[/math] entsteht so:

[math]\displaystyle{ S \Rightarrow AB \Rightarrow KEB \Rightarrow KE }[/math]

Für [math]\displaystyle{ KKEEK }[/math] gilt:

[math]\displaystyle{ S \Rightarrow AB \Rightarrow KAEB \Rightarrow KKEEB \Rightarrow KKEEKB \Rightarrow KKEEK }[/math]

Der vordere Teil entsteht nur aus [math]\displaystyle{ A }[/math], dort kommt mit jedem [math]\displaystyle{ K }[/math] auch ein [math]\displaystyle{ E }[/math] hinzu. Der hintere Teil entsteht nur aus [math]\displaystyle{ B }[/math] und enthält nur [math]\displaystyle{ K }[/math]. Andere Wörter als die der Sprache lassen sich deshalb nicht ableiten.

Mehrdeutigkeit nachweisen

Bedingte Anweisungen lassen sich mit einer Grammatik beschreiben: [math]\displaystyle{ i }[/math] steht für if (...) (wenn), [math]\displaystyle{ e }[/math] für else (sonst) und [math]\displaystyle{ a }[/math] für eine Anweisung. Die Regeln:

[math]\displaystyle{ S \to iS \mid iSeS \mid a }[/math]

Die Regel [math]\displaystyle{ S \to iS }[/math] beschreibt ein if ohne else, die Regel [math]\displaystyle{ S \to iSeS }[/math] ein if mit else. Das Wort [math]\displaystyle{ iiaea }[/math] hat zwei Ableitungsbäume:

Zwei Ableitungsbäume für iiaea
  • Linker Baum: Die Wurzel verwendet [math]\displaystyle{ S \to iS }[/math], das innere [math]\displaystyle{ S }[/math] verwendet [math]\displaystyle{ S \to iSeS }[/math]. Das else gehört zum inneren if.
  • Rechter Baum: Die Wurzel verwendet [math]\displaystyle{ S \to iSeS }[/math], das erste [math]\displaystyle{ S }[/math] darunter verwendet [math]\displaystyle{ S \to iS }[/math]. Das else gehört zum äußeren if.

Das Wort hat zwei verschiedene Bäume, die Grammatik ist also mehrdeutig. Java legt zusätzlich fest: Das else gehört zum nächstgelegenen if davor. Das entspricht dem linken Baum.

Mehrdeutigkeit beseitigen

Die folgende Grammatik über [math]\displaystyle{ \Sigma = \{K; E\} }[/math] erzeugt alle Wörter aus mindestens einem [math]\displaystyle{ K }[/math], gefolgt von beliebig vielen [math]\displaystyle{ E }[/math] (auch keinem), zum Beispiel [math]\displaystyle{ K }[/math], [math]\displaystyle{ KKE }[/math] und [math]\displaystyle{ KEEE }[/math]. Ihre Sprache ist [math]\displaystyle{ L = \{K^n E^m \mid n \geq 1 \text{ und } m \geq 0\} }[/math]:

[math]\displaystyle{ S \to KS \mid SE \mid K }[/math]

Schritt 1: Zwei Linksableitungen finden. Das Wort [math]\displaystyle{ KKE }[/math] hat zwei verschiedene Linksableitungen und damit zwei verschiedene Ableitungsbäume:

[math]\displaystyle{ S \Rightarrow KS \Rightarrow KSE \Rightarrow KKE }[/math]
[math]\displaystyle{ S \Rightarrow SE \Rightarrow KSE \Rightarrow KKE }[/math]

Im ersten Baum hat die Wurzel die Kinder [math]\displaystyle{ K }[/math] und [math]\displaystyle{ S }[/math], im zweiten die Kinder [math]\displaystyle{ S }[/math] und [math]\displaystyle{ E }[/math]. Die Grammatik ist mehrdeutig, weil sie nicht festlegt, ob zuerst vorn ein [math]\displaystyle{ K }[/math] oder zuerst hinten ein [math]\displaystyle{ E }[/math] hinzukommt.

Schritt 2: Reihenfolge des Aufbaus festlegen. Die neue Grammatik baut jedes Wort von links nach rechts auf. [math]\displaystyle{ S }[/math] erzeugt zuerst alle [math]\displaystyle{ K }[/math], danach erzeugt das neue Nichtterminal [math]\displaystyle{ T }[/math] alle [math]\displaystyle{ E }[/math]:

[math]\displaystyle{ S \to KS \mid KT \mid K }[/math]
[math]\displaystyle{ T \to ET \mid E }[/math]

Schritt 3: Prüfen. Das Wort [math]\displaystyle{ KKE }[/math] hat jetzt nur noch eine Linksableitung:

[math]\displaystyle{ S \Rightarrow KS \Rightarrow KKT \Rightarrow KKE }[/math]

Welche Regel anzuwenden ist, legt das Wort fest: Folgt auf ein [math]\displaystyle{ K }[/math] ein weiteres [math]\displaystyle{ K }[/math], passt nur [math]\displaystyle{ S \to KS }[/math]. Folgt auf das [math]\displaystyle{ K }[/math] ein [math]\displaystyle{ E }[/math], passt nur [math]\displaystyle{ S \to KT }[/math]. Danach passt [math]\displaystyle{ T \to ET }[/math], solange weitere [math]\displaystyle{ E }[/math] folgen. Beim letzten Zeichen des Wortes passt nur [math]\displaystyle{ S \to K }[/math] oder [math]\displaystyle{ T \to E }[/math]. Jedes Wort hat deshalb genau einen Ableitungsbaum.

Die Sprache ist dieselbe geblieben: [math]\displaystyle{ S }[/math] erzeugt beliebig viele [math]\displaystyle{ K }[/math] und schließt mit [math]\displaystyle{ K }[/math] oder mit [math]\displaystyle{ KT }[/math] ab, [math]\displaystyle{ T }[/math] erzeugt mindestens ein [math]\displaystyle{ E }[/math]. Das sind genau die Wörter [math]\displaystyle{ K^n E^m }[/math] mit [math]\displaystyle{ n \geq 1 }[/math] und [math]\displaystyle{ m \geq 0 }[/math].

Nicht-Regularität begründen

Die Sprache [math]\displaystyle{ L = \{0^n 1^n \mid n \geq 1\} }[/math] ist nicht regulär:

  1. Annahme: Ein DEA mit [math]\displaystyle{ k }[/math] Zuständen erkennt [math]\displaystyle{ L }[/math].
  2. Das Wort [math]\displaystyle{ 0^k 1^k }[/math] gehört zu [math]\displaystyle{ L }[/math]. Beim Lesen von [math]\displaystyle{ 0^k }[/math] durchläuft der DEA [math]\displaystyle{ k + 1 }[/math] Zustände. Ein Zustand wiederholt sich (Schubfachprinzip). Die Schleife dazwischen hat die Länge [math]\displaystyle{ j \geq 1 }[/math].
  3. Der DEA kann die Schleife einmal mehr durchlaufen. Nach [math]\displaystyle{ 0^{k+j} }[/math] ist er im selben Zustand wie nach [math]\displaystyle{ 0^k }[/math].
  4. Danach liest er [math]\displaystyle{ 1^k }[/math] und endet im selben Endzustand wie bei [math]\displaystyle{ 0^k 1^k }[/math]. Er akzeptiert also [math]\displaystyle{ 0^{k+j} 1^k }[/math].
  5. Dieses Wort hat mehr Nullen als Einsen und gehört nicht zu [math]\displaystyle{ L }[/math]. Das ist ein Widerspruch. Also gibt es keinen DEA für [math]\displaystyle{ L }[/math].

Pumping-Lemma an einer regulären Sprache nachvollziehen

DEA für Wörter mit mindestens einem E

Die Sprache [math]\displaystyle{ L }[/math] aller Wörter über [math]\displaystyle{ \{K; E\} }[/math], die mindestens ein [math]\displaystyle{ E }[/math] enthalten, ist regulär. Der DEA im Bild erkennt sie mit [math]\displaystyle{ k = 2 }[/math] Zuständen, siehe Akzeptierte Sprache eines DEA beschreiben. An ihr lässt sich beobachten, was das Lemma aussagt.

  1. Wort wählen: [math]\displaystyle{ w = KE }[/math] gehört zu [math]\displaystyle{ L }[/math] und hat die Länge [math]\displaystyle{ |w| = 2 \geq k }[/math].
  2. Lauf betrachten: Der DEA durchläuft [math]\displaystyle{ q_0 \xrightarrow{K} q_0 \xrightarrow{E} q_1 }[/math]. Der Zustand [math]\displaystyle{ q_0 }[/math] kommt zweimal vor: am Anfang und nach dem ersten Zeichen.
  3. Zerlegung ablesen: Zwischen den beiden Besuchen von [math]\displaystyle{ q_0 }[/math] liest der DEA [math]\displaystyle{ y = K }[/math]. Davor steht [math]\displaystyle{ x = \varepsilon }[/math], dahinter [math]\displaystyle{ z = E }[/math]. Es gilt [math]\displaystyle{ |xy| = 1 \leq k }[/math] und [math]\displaystyle{ |y| = 1 \geq 1 }[/math].
  4. Pumpen: Für [math]\displaystyle{ i = 0 }[/math] entsteht [math]\displaystyle{ xz = E }[/math], für [math]\displaystyle{ i = 2 }[/math] entsteht [math]\displaystyle{ xy^2z = KKE }[/math], für [math]\displaystyle{ i = 3 }[/math] entsteht [math]\displaystyle{ xy^3z = KKKE }[/math]. Alle diese Wörter enthalten ein [math]\displaystyle{ E }[/math] und gehören zu [math]\displaystyle{ L }[/math].

Der Grund: [math]\displaystyle{ y = K }[/math] führt den DEA von [math]\displaystyle{ q_0 }[/math] wieder nach [math]\displaystyle{ q_0 }[/math]. Wie oft dieser Rundweg durchlaufen wird, ändert nichts daran, dass das [math]\displaystyle{ E }[/math] danach in den Endzustand führt. Bei einer regulären Sprache hat jedes genügend lange Wort eine solche Zerlegung, bei der das Pumpen in der Sprache bleibt. Die folgenden Beispiele zeigen Sprachen, in denen sich ein passend gewähltes Wort findet, bei dem jede erlaubte Zerlegung für ein [math]\displaystyle{ i }[/math] aus der Sprache herausführt. Solche Sprachen können nicht regulär sein.

Pumping-Lemma anwenden

Für dieselbe Sprache [math]\displaystyle{ L = \{0^n 1^n \mid n \geq 1\} }[/math] gilt:

  1. Annahme: [math]\displaystyle{ L }[/math] ist regulär, und [math]\displaystyle{ k }[/math] ist die Zahl aus dem Pumping-Lemma.
  2. Gewählt wird [math]\displaystyle{ w = 0^k 1^k }[/math]. Es gilt [math]\displaystyle{ w \in L }[/math] und [math]\displaystyle{ |w| = 2k \geq k }[/math].
  3. Das Lemma liefert eine Zerlegung [math]\displaystyle{ w = xyz }[/math] mit [math]\displaystyle{ |xy| \leq k }[/math] und [math]\displaystyle{ |y| \geq 1 }[/math]. Die ersten [math]\displaystyle{ k }[/math] Zeichen von [math]\displaystyle{ w }[/math] sind Nullen. Also besteht [math]\displaystyle{ y }[/math] nur aus Nullen und enthält mindestens eine.
  4. Für [math]\displaystyle{ i = 2 }[/math] hat [math]\displaystyle{ xy^2z }[/math] mehr als [math]\displaystyle{ k }[/math] Nullen, aber nur [math]\displaystyle{ k }[/math] Einsen. Das Wort gehört nicht zu [math]\displaystyle{ L }[/math]. Das widerspricht [math]\displaystyle{ xy^iz \in L }[/math] für alle [math]\displaystyle{ i \geq 0 }[/math]. Also ist [math]\displaystyle{ L }[/math] nicht regulär.

Pumping-Lemma durch Weglassen anwenden

Die Sprache [math]\displaystyle{ L }[/math] enthält alle Wörter über [math]\displaystyle{ \Sigma = \{0; 1\} }[/math], in denen mehr Nullen als Einsen vorkommen. Wiederholen hilft hier nicht weiter: Kommen Nullen hinzu, bleibt das Wort in der Sprache. Zum Widerspruch führt das Weglassen.

  1. Annahme: [math]\displaystyle{ L }[/math] ist regulär, und [math]\displaystyle{ k }[/math] ist die Zahl aus dem Pumping-Lemma.
  2. Gewählt wird [math]\displaystyle{ w = 0^{k+1} 1^k }[/math]. Das Wort hat eine Null mehr als Einsen, also gilt [math]\displaystyle{ w \in L }[/math], und [math]\displaystyle{ |w| = 2k + 1 \geq k }[/math].
  3. Das Lemma liefert eine Zerlegung [math]\displaystyle{ w = xyz }[/math] mit [math]\displaystyle{ |xy| \leq k }[/math] und [math]\displaystyle{ |y| \geq 1 }[/math]. Die ersten [math]\displaystyle{ k }[/math] Zeichen von [math]\displaystyle{ w }[/math] sind Nullen. Also besteht [math]\displaystyle{ y }[/math] nur aus Nullen und enthält mindestens eine.
  4. Für [math]\displaystyle{ i = 0 }[/math] fällt [math]\displaystyle{ y }[/math] weg. Das Wort [math]\displaystyle{ xz }[/math] hat höchstens [math]\displaystyle{ k }[/math] Nullen, aber weiterhin [math]\displaystyle{ k }[/math] Einsen. Es enthält nicht mehr Nullen als Einsen und gehört nicht zu [math]\displaystyle{ L }[/math]. Das widerspricht dem Lemma. Also ist [math]\displaystyle{ L }[/math] nicht regulär.

Dieselbe Überlegung lässt sich ohne das Lemma direkt am DEA führen, wie im Beispiel Nicht-Regularität begründen: Beim Lesen der ersten [math]\displaystyle{ k }[/math] Nullen wiederholt sich ein Zustand. Lässt der DEA die Schleife aus [math]\displaystyle{ j \geq 1 }[/math] Nullen aus, endet er im selben Zustand wie vorher und akzeptiert deshalb auch [math]\displaystyle{ 0^{k+1-j} 1^k }[/math]. Dieses Wort hat höchstens [math]\displaystyle{ k }[/math] Nullen und gehört nicht zu [math]\displaystyle{ L }[/math].