Kontextfreie Grammatik: Unterschied zwischen den Versionen

Die Seite wurde neu angelegt: „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>G = (N, T, P, S)</math>, deren Regeln links genau ein Nichtterminal haben: :<math>A \to \beta</math> mit <math>A \in N</math> und <math>\beta \in (N \cup T)^*</math> Die rechte Seite <ma…“
 
Keine Bearbeitungszusammenfassung
 
Zeile 2: Zeile 2:


==Definition==
==Definition==
Eine '''kontextfreie Grammatik''' ist eine [[Formale Grammatik|formale Grammatik]] <math>G = (N, T, P, S)</math>, deren Regeln links genau ein Nichtterminal haben:
Eine '''kontextfreie Grammatik''' ist eine [[Formale Grammatik|formale Grammatik]] <math>G = (N; T; P; S)</math>, deren Regeln links genau ein Nichtterminal haben:


:<math>A \to \beta</math> mit <math>A \in N</math> und <math>\beta \in (N \cup T)^*</math>
:<math>A \to \beta</math> mit <math>A \in N</math> und <math>\beta \in (N \cup T)^*</math>


Die rechte Seite <math>\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 [[Kellerautomat|Kellerautomaten]].
Die rechte Seite <math>\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 [[Kellerautomat|Kellerautomaten]].
Jede reguläre und jede rechtslineare Grammatik ist auch kontextfrei, denn ihre Regeln haben ebenfalls die Form <math>A \to \beta</math>.


==Links- und Rechtsableitung==
==Links- und Rechtsableitung==
Zeile 24: Zeile 26:


==Mehrdeutigkeit==
==Mehrdeutigkeit==
Eine kontextfreie Grammatik ist '''mehrdeutig''', wenn es für mindestens ein Wort zwei verschiedene Ableitungsbäume gibt. Zwei Ableitungen desselben Baums, etwa eine Links- und eine Rechtsableitung, sind keine 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>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>A \to aA</math> hängt beliebig viele Zeichen an, wie bei einer [[Reguläre Grammatik|regulären Grammatik]].
* '''Hintereinander:''' Eine Regel der Form <math>S \to AB</math> setzt zwei Teile hintereinander, die unabhängig voneinander erzeugt werden.


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.
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==
==Grenzen regulärer Sprachen==
Ein [[Deterministischer endlicher Automat|DEA]] hat endlich viele Zustände und kann deshalb nicht beliebig weit zählen. Der Grund:
Ein [[Deterministischer endlicher Automat|DEA]] hat endlich viele Zustände und kann deshalb nicht beliebig weit zählen. Der Grund:


* Hat der DEA <math>n</math> Zustände, durchläuft er beim Lesen von <math>n</math> Zeichen <math>n + 1</math> Zustände. Also wiederholt sich ein Zustand (Schubfachprinzip), und es entsteht eine Schleife.
* Hat der DEA <math>k</math> Zustände, durchläuft er beim Lesen von <math>k</math> Zeichen <math>k + 1</math> Zustände. Also kommt ein Zustand mindestens zweimal vor. Das ist das Schubfachprinzip: Verteilt man <math>k + 1</math> Dinge auf <math>k</math> Fächer, liegen in mindestens einem Fach zwei Dinge.
* Die Schleife lässt sich beliebig oft durchlaufen. Nach jedem Durchlauf ist der Automat im selben Zustand.
* Zwischen den beiden Besuchen desselben Zustands liest der DEA <math>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 mehr unterscheiden, wie oft die Schleife durchlaufen wurde. Die gelesene Anzahl geht verloren.
* 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>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.


Verlangt eine Sprache, dass eine unbegrenzte Anzahl mitgezählt wird, erkennt kein DEA sie: Die Sprache ist nicht regulär. Eine kontextfreie Grammatik kann solche Anzahlen vergleichen, weil eine Regel das Nichtterminal in der Mitte der rechten Seite stehen lassen kann (<math>A \to \beta_1 A \beta_2</math>). Dann entstehen links und rechts davon gleichzeitig neue Zeichen.
Eine kontextfreie Grammatik kann solche Anzahlen vergleichen, weil eine Regel das Nichtterminal in der Mitte der rechten Seite stehen lassen kann (<math>A \to \beta_1 A \beta_2</math>). Dann entstehen links und rechts davon gleichzeitig neue Zeichen.


Jede reguläre Sprache ist kontextfrei, denn reguläre Regeln haben auch die Form <math>A \to \beta</math>. Die Umkehrung gilt nicht.
Jede reguläre Sprache ist kontextfrei. Die Umkehrung gilt nicht.


==Pumping-Lemma==
==Pumping-Lemma==
Das '''Pumping-Lemma''' beschreibt eine Eigenschaft, die jede reguläre Sprache hat. Zu jeder regulären Sprache <math>L</math> gibt es eine Zahl <math>n \geq 1</math>, sodass jedes Wort <math>w \in L</math> mit <math>|w| \geq n</math> eine Zerlegung <math>w = xyz</math> hat mit
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>L</math> gibt es eine Zahl <math>k \geq 1</math>, sodass jedes Wort <math>w \in L</math> mit der [[Wort#Wortlänge|Wortlänge]] <math>|w| \geq k</math> eine Zerlegung <math>w = xyz</math> hat mit


* <math>|xy| \leq n</math>,
* <math>|xy| \leq k</math>,
* <math>|y| \geq 1</math> und
* <math>|y| \geq 1</math> und
* <math>xy^iz \in L</math> für alle <math>i \geq 0</math>.
* <math>xy^iz \in L</math> für alle <math>i \geq 0</math>.


Der Teil <math>y</math> lässt sich also beliebig oft wiederholen („aufpumpen“) oder weglassen, ohne dass das Wort die Sprache verlässt.
Der Teil <math>y</math> lässt sich also beliebig oft wiederholen („aufpumpen“) oder weglassen (<math>i = 0</math>), ohne dass das Wort die Sprache verlässt. <math>y^i</math> ist dabei eine [[Wort#Wortpotenz|Wortpotenz]]. Das Lemma fasst die Überlegung aus dem Abschnitt [[#Grenzen regulärer Sprachen|Grenzen regulärer Sprachen]] zusammen: <math>k</math> ist die Anzahl der Zustände eines DEA für <math>L</math>, und <math>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:
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:


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


==Beispiele==
==Beispiele==
===Klammerausdrücke ableiten===
===Klammerausdrücke ableiten===
Die Grammatik mit dem Startsymbol <math>S</math> und den Terminalen <code>(</code> und <code>)</code> erzeugt korrekt geklammerte Ausdrücke. Ihre Regeln:
Die Grammatik mit dem Startsymbol <math>S</math> und den Terminalen <math>(</math> und <math>)</math> erzeugt korrekt geklammerte Ausdrücke. Ihre Regeln:


:<math>S \to (S)S \mid \varepsilon</math>
:<math>S \to (S)S \mid \varepsilon</math>


Die Regel <math>S \to (S)S</math> setzt ein Klammerpaar, in dem ein Ausdruck steht, und lässt einen weiteren Ausdruck folgen. Die Regel <math>S \to \varepsilon</math> beendet die Ableitung. Das Wort <code>()()</code> lässt sich auf zwei Arten ableiten.
Die Regel <math>S \to (S)S</math> setzt ein Klammerpaar, in dem ein Ausdruck steht, und lässt einen weiteren Ausdruck folgen. Die Regel <math>S \to \varepsilon</math> lässt ein <math>S</math> verschwinden. Das Wort <math>()()</math> wird einmal als Linksableitung und einmal als Rechtsableitung abgeleitet.


Die Linksableitung ersetzt immer das am weitesten links stehende <math>S</math>:
Die Linksableitung ersetzt immer das am weitesten links stehende <math>S</math>:
Zeile 72: Zeile 85:


[[Datei:Ableitungsbaum Klammerausdruck.png|mini|Ableitungsbaum des Wortes ()()]]
[[Datei:Ableitungsbaum Klammerausdruck.png|mini|Ableitungsbaum des Wortes ()()]]
Der Ableitungsbaum zeigt die Struktur. Die Wurzel <math>S</math> hat die Kinder <code>(</code>, <math>S</math>, <code>)</code> und <math>S</math>. Das erste innere <math>S</math> wird zu <math>\varepsilon</math>. Das letzte <math>S</math> hat wieder die Kinder <code>(</code>, <math>S</math>, <code>)</code> und <math>S</math>, und beide <math>S</math> werden zu <math>\varepsilon</math>. Die Blätter ergeben von links nach rechts <code>()()</code>. Links- und Rechtsableitung gehören zu demselben Baum.
Der Ableitungsbaum entsteht Schritt für Schritt aus der Linksableitung. Jeder Ableitungsschritt hängt unter das ersetzte <math>S</math> die Zeichen der rechten Regelseite:
 
# <math>S \Rightarrow (S)S</math>: Die Wurzel <math>S</math> erhält die Kinder <math>(</math>, <math>S</math>, <math>)</math> und <math>S</math>.
# <math>(S)S \Rightarrow ()S</math>: Das am weitesten links stehende <math>S</math> erhält das Kind <math>\varepsilon</math>.
# <math>()S \Rightarrow ()(S)S</math>: Das am weitesten links stehende <math>S</math> erhält die Kinder <math>(</math>, <math>S</math>, <math>)</math> und <math>S</math>.
# <math>()(S)S \Rightarrow ()()S</math>: Das am weitesten links stehende <math>S</math> erhält das Kind <math>\varepsilon</math>.
# <math>()()S \Rightarrow ()()</math>: Das am weitesten links stehende <math>S</math> erhält das Kind <math>\varepsilon</math>.
 
Die Blätter ergeben von links nach rechts <math>()()</math>. Die Rechtsableitung führt zu demselben Baum, sie ersetzt die Knoten nur in anderer Reihenfolge. Zwei Ableitungen mit demselben Baum sind keine [[#Mehrdeutigkeit|Mehrdeutigkeit]]. Einen zweiten Baum gibt es für <math>()()</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===
===Nichtzugehörigkeit begründen===
Gehört das Wort <code>(()</code> zur Sprache der Grammatik <math>S \to (S)S \mid \varepsilon</math>? Nein. Die Regel <math>S \to (S)S</math> erzeugt je eine öffnende und eine schließende Klammer, die Regel <math>S \to \varepsilon</math> keine. Jede Ableitung erzeugt deshalb gleich viele <code>(</code> und <code>)</code>. Das Wort <code>(()</code> hat zwei <code>(</code> und nur eine <code>)</code>. Es gehört nicht zur Sprache.
Gehört das Wort <math>(()</math> zur Sprache der Grammatik <math>S \to (S)S \mid \varepsilon</math>? Nein. Die Regel <math>S \to (S)S</math> erzeugt je eine öffnende und eine schließende Klammer, die Regel <math>S \to \varepsilon</math> keine. Jede Ableitung erzeugt deshalb gleich viele öffnende und schließende Klammern. Das Wort <math>(()</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>L = \{K^n E^{n+1} \mid n \geq 0\}</math> über <math>\Sigma = \{K; E\}</math>: erst <math>n</math>-mal <math>K</math>, danach ein <math>E</math> mehr.
 
'''Schritt 1: Kürzeste Wörter aufschreiben.''' Für <math>n = 0</math>, <math>n = 1</math> und <math>n = 2</math> entstehen <math>E</math>, <math>KEE</math> und <math>KKEEE</math>.
 
'''Schritt 2: Aufbau erkennen.''' Von einem Wort zum nächsten kommt vorn ein <math>K</math> und hinten ein <math>E</math> hinzu. In der Mitte bleibt immer ein einzelnes <math>E</math>. Das passt zum Muster „Paare von außen nach innen“ mit dem Abschluss <math>E</math>.
 
'''Schritt 3: Regeln aufstellen.'''
 
:<math>S \to KSE \mid E</math>
 
'''Schritt 4: Prüfen.''' Das kürzeste Wort <math>E</math> entsteht direkt aus der zweiten Regel. Für <math>KKEEE</math> gilt:
 
:<math>S \Rightarrow KSE \Rightarrow KKSEE \Rightarrow KKEEE</math>
 
Jede Anwendung der ersten Regel erzeugt genau ein <math>K</math> und ein <math>E</math>, die zweite Regel erzeugt das zusätzliche <math>E</math>. Andere Wörter als die der Sprache lassen sich nicht ableiten. Die Grammatik ist kontextfrei, aber nicht rechtslinear, weil in <math>S \to KSE</math> das Nichtterminal in der Mitte steht.
 
===Grammatik aus Teilen zusammensetzen===
Gesucht ist eine kontextfreie Grammatik für die Sprache <math>L = \{K^n E^n K^m \mid n \geq 1 \text{ und } m \geq 0\}</math> über <math>\Sigma = \{K; E\}</math>: zuerst gleich viele <math>K</math> und <math>E</math>, danach beliebig viele <math>K</math>. Zur Sprache gehören zum Beispiel <math>KE</math>, <math>KEK</math> und <math>KKEEKKK</math>.
 
'''Schritt 1: Wort in Teile zerlegen.''' Jedes Wort besteht aus zwei Teilen, die unabhängig voneinander sind: Der vordere Teil <math>K^n E^n</math> braucht gleich viele <math>K</math> und <math>E</math>. Der hintere Teil <math>K^m</math> ist eine beliebige Wiederholung.
 
'''Schritt 2: Für jeden Teil ein Nichtterminal wählen.''' <math>A</math> erzeugt den vorderen Teil nach dem Muster „Paare von außen nach innen“ mit dem Abschluss <math>KE</math>. <math>B</math> erzeugt den hinteren Teil nach dem Muster „Wiederholung“ mit dem Abschluss <math>\varepsilon</math>.
 
'''Schritt 3: Teile hintereinandersetzen.''' Das Startsymbol setzt beide Teile mit der Regel <math>S \to AB</math> hintereinander:
 
:<math>S \to AB</math>
:<math>A \to KAE \mid KE</math>
:<math>B \to KB \mid \varepsilon</math>
 
'''Schritt 4: Prüfen.''' Das kürzeste Wort <math>KE</math> entsteht so:
 
:<math>S \Rightarrow AB \Rightarrow KEB \Rightarrow KE</math>
 
Für <math>KKEEK</math> gilt:
 
:<math>S \Rightarrow AB \Rightarrow KAEB \Rightarrow KKEEB \Rightarrow KKEEKB \Rightarrow KKEEK</math>
 
Der vordere Teil entsteht nur aus <math>A</math>, dort kommt mit jedem <math>K</math> auch ein <math>E</math> hinzu. Der hintere Teil entsteht nur aus <math>B</math> und enthält nur <math>K</math>. Andere Wörter als die der Sprache lassen sich deshalb nicht ableiten.


===Mehrdeutigkeit nachweisen===
===Mehrdeutigkeit nachweisen===
Bedingte Anweisungen lassen sich mit einer Grammatik beschreiben: <code>i</code> steht für <code>if (...)</code> (wenn), <code>e</code> für <code>else</code> (sonst) und <code>a</code> für eine Anweisung. Die Regeln:
Bedingte Anweisungen lassen sich mit einer Grammatik beschreiben: <math>i</math> steht für <code>if (...)</code> (wenn), <math>e</math> für <code>else</code> (sonst) und <math>a</math> für eine Anweisung. Die Regeln:


:<math>S \to iS \mid iSeS \mid a</math>
:<math>S \to iS \mid iSeS \mid a</math>


Die Regel <math>S \to iS</math> beschreibt ein <code>if</code> ohne <code>else</code>, die Regel <math>S \to iSeS</math> ein <code>if</code> mit <code>else</code>. Das Wort <code>iiaea</code> hat zwei Ableitungsbäume:
Die Regel <math>S \to iS</math> beschreibt ein <code>if</code> ohne <code>else</code>, die Regel <math>S \to iSeS</math> ein <code>if</code> mit <code>else</code>. Das Wort <math>iiaea</math> hat zwei Ableitungsbäume:


[[Datei:Mehrdeutigkeit Wenn-dann-sonst.png|mini|Zwei Ableitungsbäume für iiaea]]
[[Datei:Mehrdeutigkeit Wenn-dann-sonst.png|mini|Zwei Ableitungsbäume für iiaea]]
Zeile 89: Zeile 150:


Das Wort hat zwei verschiedene Bäume, die Grammatik ist also mehrdeutig. Java legt zusätzlich fest: Das <code>else</code> gehört zum nächstgelegenen <code>if</code> davor. Das entspricht dem linken Baum.
Das Wort hat zwei verschiedene Bäume, die Grammatik ist also mehrdeutig. Java legt zusätzlich fest: Das <code>else</code> gehört zum nächstgelegenen <code>if</code> davor. Das entspricht dem linken Baum.
===Mehrdeutigkeit beseitigen===
Die folgende Grammatik über <math>\Sigma = \{K; E\}</math> erzeugt alle Wörter aus mindestens einem <math>K</math>, gefolgt von beliebig vielen <math>E</math> (auch keinem), zum Beispiel <math>K</math>, <math>KKE</math> und <math>KEEE</math>. Ihre Sprache ist <math>L = \{K^n E^m \mid n \geq 1 \text{ und } m \geq 0\}</math>:
:<math>S \to KS \mid SE \mid K</math>
'''Schritt 1: Zwei Linksableitungen finden.''' Das Wort <math>KKE</math> hat zwei verschiedene Linksableitungen und damit zwei verschiedene Ableitungsbäume:
:<math>S \Rightarrow KS \Rightarrow KSE \Rightarrow KKE</math>
:<math>S \Rightarrow SE \Rightarrow KSE \Rightarrow KKE</math>
Im ersten Baum hat die Wurzel die Kinder <math>K</math> und <math>S</math>, im zweiten die Kinder <math>S</math> und <math>E</math>. Die Grammatik ist mehrdeutig, weil sie nicht festlegt, ob zuerst vorn ein <math>K</math> oder zuerst hinten ein <math>E</math> hinzukommt.
'''Schritt 2: Reihenfolge des Aufbaus festlegen.''' Die neue Grammatik baut jedes Wort von links nach rechts auf. <math>S</math> erzeugt zuerst alle <math>K</math>, danach erzeugt das neue Nichtterminal <math>T</math> alle <math>E</math>:
:<math>S \to KS \mid KT \mid K</math>
:<math>T \to ET \mid E</math>
'''Schritt 3: Prüfen.''' Das Wort <math>KKE</math> hat jetzt nur noch eine Linksableitung:
:<math>S \Rightarrow KS \Rightarrow KKT \Rightarrow KKE</math>
Welche Regel anzuwenden ist, legt das Wort fest: Folgt auf ein <math>K</math> ein weiteres <math>K</math>, passt nur <math>S \to KS</math>. Folgt auf das <math>K</math> ein <math>E</math>, passt nur <math>S \to KT</math>. Danach passt <math>T \to ET</math>, solange weitere <math>E</math> folgen. Beim letzten Zeichen des Wortes passt nur <math>S \to K</math> oder <math>T \to E</math>. Jedes Wort hat deshalb genau einen Ableitungsbaum.
Die Sprache ist dieselbe geblieben: <math>S</math> erzeugt beliebig viele <math>K</math> und schließt mit <math>K</math> oder mit <math>KT</math> ab, <math>T</math> erzeugt mindestens ein <math>E</math>. Das sind genau die Wörter <math>K^n E^m</math> mit <math>n \geq 1</math> und <math>m \geq 0</math>.


===Nicht-Regularität begründen===
===Nicht-Regularität begründen===
Zeile 94: Zeile 180:


# Annahme: Ein DEA mit <math>k</math> Zuständen erkennt <math>L</math>.
# Annahme: Ein DEA mit <math>k</math> Zuständen erkennt <math>L</math>.
# Das Wort <math>0^k 1^k</math> gehört zu <math>L</math>. Beim Lesen von <math>0^k</math> durchläuft der DEA <math>k + 1</math> Zustände. Ein Zustand wiederholt sich (Schubfachprinzip). Die Schleife dazwischen hat die Länge <math>m \geq 1</math>.
# Das Wort <math>0^k 1^k</math> gehört zu <math>L</math>. Beim Lesen von <math>0^k</math> durchläuft der DEA <math>k + 1</math> Zustände. Ein Zustand wiederholt sich (Schubfachprinzip). Die Schleife dazwischen hat die Länge <math>j \geq 1</math>.
# Der DEA kann die Schleife einmal mehr durchlaufen. Nach <math>0^{k+m}</math> ist er im selben Zustand wie nach <math>0^k</math>.
# Der DEA kann die Schleife einmal mehr durchlaufen. Nach <math>0^{k+j}</math> ist er im selben Zustand wie nach <math>0^k</math>.
# Danach liest er <math>1^k</math> und endet im selben Endzustand wie bei <math>0^k 1^k</math>. Er akzeptiert also <math>0^{k+m} 1^k</math>.
# Danach liest er <math>1^k</math> und endet im selben Endzustand wie bei <math>0^k 1^k</math>. Er akzeptiert also <math>0^{k+j} 1^k</math>.
# Dieses Wort hat mehr Nullen als Einsen und gehört nicht zu <math>L</math>. Das ist ein Widerspruch. Also gibt es keinen DEA für <math>L</math>.
# Dieses Wort hat mehr Nullen als Einsen und gehört nicht zu <math>L</math>. Das ist ein Widerspruch. Also gibt es keinen DEA für <math>L</math>.
===Pumping-Lemma an einer regulären Sprache nachvollziehen===
[[Datei:DEA Mindestens ein E.png|mini|DEA für Wörter mit mindestens einem E]]
Die Sprache <math>L</math> aller Wörter über <math>\{K; E\}</math>, die mindestens ein <math>E</math> enthalten, ist regulär. Der DEA im Bild erkennt sie mit <math>k = 2</math> Zuständen, siehe [[Deterministischer endlicher Automat#Akzeptierte Sprache eines DEA beschreiben|Akzeptierte Sprache eines DEA beschreiben]]. An ihr lässt sich beobachten, was das Lemma aussagt.
# '''Wort wählen:''' <math>w = KE</math> gehört zu <math>L</math> und hat die Länge <math>|w| = 2 \geq k</math>.
# '''Lauf betrachten:''' Der DEA durchläuft <math>q_0 \xrightarrow{K} q_0 \xrightarrow{E} q_1</math>. Der Zustand <math>q_0</math> kommt zweimal vor: am Anfang und nach dem ersten Zeichen.
# '''Zerlegung ablesen:''' Zwischen den beiden Besuchen von <math>q_0</math> liest der DEA <math>y = K</math>. Davor steht <math>x = \varepsilon</math>, dahinter <math>z = E</math>. Es gilt <math>|xy| = 1 \leq k</math> und <math>|y| = 1 \geq 1</math>.
# '''Pumpen:''' Für <math>i = 0</math> entsteht <math>xz = E</math>, für <math>i = 2</math> entsteht <math>xy^2z = KKE</math>, für <math>i = 3</math> entsteht <math>xy^3z = KKKE</math>. Alle diese Wörter enthalten ein <math>E</math> und gehören zu <math>L</math>.
Der Grund: <math>y = K</math> führt den DEA von <math>q_0</math> wieder nach <math>q_0</math>. Wie oft dieser Rundweg durchlaufen wird, ändert nichts daran, dass das <math>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>i</math> aus der Sprache herausführt. Solche Sprachen können nicht regulär sein.


===Pumping-Lemma anwenden===
===Pumping-Lemma anwenden===
Für dieselbe Sprache <math>L = \{0^n 1^n \mid n \geq 1\}</math> gilt:
Für dieselbe Sprache <math>L = \{0^n 1^n \mid n \geq 1\}</math> gilt:


# Annahme: <math>L</math> ist regulär, und <math>n</math> ist die Zahl aus dem Pumping-Lemma.
# Annahme: <math>L</math> ist regulär, und <math>k</math> ist die Zahl aus dem Pumping-Lemma.
# Gewählt wird <math>w = 0^n 1^n</math>. Es gilt <math>w \in L</math> und <math>|w| = 2n \geq n</math>.
# Gewählt wird <math>w = 0^k 1^k</math>. Es gilt <math>w \in L</math> und <math>|w| = 2k \geq k</math>.
# Das Lemma liefert eine Zerlegung <math>w = xyz</math> mit <math>|xy| \leq n</math> und <math>|y| \geq 1</math>. Die ersten <math>n</math> Zeichen von <math>w</math> sind Nullen. Also besteht <math>y</math> nur aus Nullen und enthält mindestens eine.
# Das Lemma liefert eine Zerlegung <math>w = xyz</math> mit <math>|xy| \leq k</math> und <math>|y| \geq 1</math>. Die ersten <math>k</math> Zeichen von <math>w</math> sind Nullen. Also besteht <math>y</math> nur aus Nullen und enthält mindestens eine.
# Für <math>i = 2</math> hat <math>xy^2z</math> mehr als <math>n</math> Nullen, aber nur <math>n</math> Einsen. Das Wort gehört nicht zu <math>L</math>. Das widerspricht <math>xy^iz \in L</math> für alle <math>i \geq 0</math>. Also ist <math>L</math> nicht regulär.
# Für <math>i = 2</math> hat <math>xy^2z</math> mehr als <math>k</math> Nullen, aber nur <math>k</math> Einsen. Das Wort gehört nicht zu <math>L</math>. Das widerspricht <math>xy^iz \in L</math> für alle <math>i \geq 0</math>. Also ist <math>L</math> nicht regulär.
 
===Pumping-Lemma durch Weglassen anwenden===
Die Sprache <math>L</math> enthält alle Wörter über <math>\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.
 
# Annahme: <math>L</math> ist regulär, und <math>k</math> ist die Zahl aus dem Pumping-Lemma.
# Gewählt wird <math>w = 0^{k+1} 1^k</math>. Das Wort hat eine Null mehr als Einsen, also gilt <math>w \in L</math>, und <math>|w| = 2k + 1 \geq k</math>.
# Das Lemma liefert eine Zerlegung <math>w = xyz</math> mit <math>|xy| \leq k</math> und <math>|y| \geq 1</math>. Die ersten <math>k</math> Zeichen von <math>w</math> sind Nullen. Also besteht <math>y</math> nur aus Nullen und enthält mindestens eine.
# Für <math>i = 0</math> fällt <math>y</math> weg. Das Wort <math>xz</math> hat höchstens <math>k</math> Nullen, aber weiterhin <math>k</math> Einsen. Es enthält nicht mehr Nullen als Einsen und gehört nicht zu <math>L</math>. Das widerspricht dem Lemma. Also ist <math>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|Nicht-Regularität begründen]]: Beim Lesen der ersten <math>k</math> Nullen wiederholt sich ein Zustand. Lässt der DEA die Schleife aus <math>j \geq 1</math> Nullen aus, endet er im selben Zustand wie vorher und akzeptiert deshalb auch <math>0^{k+1-j} 1^k</math>. Dieses Wort hat höchstens <math>k</math> Nullen und gehört nicht zu <math>L</math>.


[[Kategorie:Formale Sprachen]]
[[Kategorie:Formale Sprachen]]
[[Kategorie:AHR I Informatik LK]]
[[Kategorie:AHR I Informatik LK]]