www.wikidata.de-de.nina.az

Pumping Lemma Das bzw Pumplemma auch Schleifensatz genannt beschreibt in der theoretischen Informatik eine Eigenschaft b

Pumping-Lemma

Das Pumping-Lemma bzw. Pumplemma (auch Schleifensatz genannt) beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nicht regulär bzw. nicht kontextfrei ist.

Seinen Namen hat das Lemma vom englischen Begriff to pump, zu deutsch aufpumpen. Es leitet sich davon ab, dass Teile von Wörtern aus Sprachen bestimmter Klassen vervielfacht (aufgepumpt) werden können, so dass die dabei entstehenden Wörter ebenfalls in der Sprache sind.

Man unterscheidet zunächst zwischen dem Pumping-Lemma für reguläre Sprachen und jenem für kontextfreie Sprachen. In der Literatur sind weiterhin Pumping-Lemmata für Erweiterungen der kontextfreien Sprachen anzutreffen. Mächtigere Sprachklassen in der Chomsky-Hierarchie wie die kontextsensitiven Sprachen und auch die wachsend kontextsensitiven Sprachen ermöglichen jedoch kein Pumping-Lemma.

Alternativ wird das Lemma bzw. seine Ausprägungen auch als uvw-Theorem, uvwxy-Theorem, Schleifenlemma, Iterationslemma oder Lemma von Bar-Hillel bezeichnet.

Reguläre Sprachen Bearbeiten

Pumping-Lemma für reguläre Sprachen Bearbeiten

Für jede reguläre Sprache gibt es eine natürliche Zahl , sodass gilt: Jedes Wort in mit Mindestlänge hat eine Zerlegung mit den folgenden drei Eigenschaften:

  1. Die beiden Wörter und haben zusammen höchstens die Länge .
  2. Das Wort ist nicht leer.
  3. Für jede natürliche Zahl (mit 0) ist das Wort in der Sprache , d. h. die Wörter , , , usw. sind alle in der Sprache .

Das kleinste , das diese Eigenschaften erfüllt, wird Pumping-Zahl der Sprache genannt.

Neben den regulären Sprachen gibt es auch nicht-reguläre Sprachen, die dieses Lemma erfüllen. Eine notwendige und hinreichende Bedingung für reguläre Sprachen liefern der Satz von Myhill-Nerode oder Jaffes Pumping-Lemma.

Das Pumping-Lemma enthält mehrere Wechsel zwischen universeller und existentieller Quantifizierung. Diese kann man gut anhand der folgenden formalen Formulierung des Lemmas erkennen. Darin bezeichnet die Menge aller regulärer Sprachen.

Beweis Bearbeiten

Die Gültigkeit des Lemmas basiert darauf, dass es zu jeder regulären Sprache einen deterministischen endlichen Automaten gibt, der die Sprache akzeptiert. Über einem endlichen Alphabet enthält eine reguläre Sprache mit unendlich vielen Wörtern auch solche Wörter, die mehr Zeichen enthalten als der Automat Zustände hat. Zum Akzeptieren solcher Wörter muss der Automat also einen Zyklus enthalten, der dann in beliebiger Häufigkeit durchlaufen werden kann. Die Buchstabenfolge, die beim Durchlaufen des Zyklus gelesen wird, kann also entsprechend beliebig oft in Wörtern der Sprache vorkommen.

Die Idee des Pumping-Lemmas ist, dass ein Wortteil durch einen Zyklus im deterministischen endlichen Automaten beliebig oft wiederholt werden kann.

Der folgende Beweis setzt die Mindestlänge aus dem Lemma mit der Anzahl der Zustände des Automaten gleich und zeigt, dass wegen der Existenz eines Zyklus jedes Wort mit dieser Mindestlänge die geforderte Zerlegung besitzt.

Sei eine reguläre Sprache. Ist endlich, dann gibt es ein Wort mit maximaler Länge . Sei , so ist für alle die Prämisse falsch und die Implikation damit wahr.

Ist unendlich, dann sei ein deterministischer endlicher Automat, der akzeptiert. Da regulär ist, existiert ein solcher Automat immer. Sei die Anzahl der Zustände dieses Automaten, und sei ein beliebiges Wort aus mit mindestens Zeichen. Bezeichne nun mit die Zustandsfolge, die beim Lesen von beginnend mit dem Startzustand durchläuft. Da in ist, muss von akzeptiert werden, d. h. muss ein akzeptierender Zustand sein. Da der Automat gerade Zustände hat, muss spätestens nach dem Lesen von Zeichen eine Zustandswiederholung eintreten. Das heißt, es existieren mit und . Der Automat durchläuft beim Lesen von also einen Zyklus.

Sei der Teil von , der beim Durchlaufen des Zyklus gelesen wird. Ferner sei der Teil von , der beim Durchlaufen der davor liegenden Zustandsfolge gelesen wird, und sei der Teil von , der beim Durchlaufen der dahinter liegenden Zustandsfolge gelesen wird. Mit dieser Wahl gilt .

Mit dieser Wahl von , und gelten die Aussagen aus dem Pumping-Lemma:

  1. Die Länge von ist und somit nicht größer als .
  2. Das Wort ist nicht leer, da gilt, so dass beim Durchlauf des Zyklus mindestens ein Zeichen gelesen wird.
  3. Für beliebiges durchläuft der Automat beim Lesen des Worts zunächst die Zustandsfolge , dann -mal den Zyklus und schließlich die Zustandsfolge . Am Ende befindet sich der Automat im akzeptierenden Zustand . Somit gilt für alle .

Beispiel Bearbeiten

Ist die Sprache regulär?

Angenommen, sei eine reguläre Sprache. Dann gibt es gemäß Pumping-Lemma eine Zahl , so dass sich alle Wörter mit wie beschrieben zerlegen lassen.

Insbesondere gibt es eine Zerlegung mit den beschriebenen Eigenschaften für das Wort . Da ein Präfix dieses Wortes ist und gemäß Eigenschaft 1 höchstens Länge hat, besteht und damit ausschließlich aus Buchstaben . Gemäß Eigenschaft 3 (für ) muss auch das Wort in liegen. Da aber (Eigenschaft 2), enthält dieses Wort mehr als , liegt also nicht in .

Also führt die Annahme, sei eine reguläre Sprache, zum Widerspruch und ist damit falsch.

Eine nicht-reguläre Sprache, die den Bedingungen des Pumping-Lemmas genügt Bearbeiten

Die Sprache ist nicht regulär. Allerdings erfüllt die Eigenschaften des Pumping-Lemmas, denn jedes Wort lässt sich so zerlegen , dass auch für alle . Dazu kann einfach als erster Buchstabe gewählt werden. Dieser ist entweder ein , die Anzahl von führenden s ist beliebig. Oder er ist ein oder , ohne führende s ist aber die Anzahl von führenden s oder s beliebig.

Jaffes Pumping-Lemma Bearbeiten

Jeffrey Jaffe hat ein verallgemeinertes Pumping-Lemma entwickelt, das äquivalent zur Definition der regulären Sprachen ist. Es ist also eine notwendige und hinreichende Bedingung zum Nachweis der Regularität einer Sprache.

Die Sprache ist regulär genau dann, wenn eine Konstante existiert, so dass es für alle , eine Zerteilung mit gibt, so dass für alle und Suffixe gilt:

Kontextfreie Sprachen Bearbeiten

Pumping-Lemma für kontextfreie Sprachen Bearbeiten

Für jede kontextfreie Sprache gibt es eine natürliche Zahl , sodass gilt: Jedes Wort in mit Mindestlänge hat eine Zerlegung mit den folgenden drei Eigenschaften:

  1. Die Wörter , und haben zusammen höchstens die Länge , d. h. .
  2. Eines der Wörter , ist nicht leer. Also .
  3. Für jede natürliche Zahl (mit 0) ist das Wort in der Sprache , d. h. die Wörter , , usw. liegen alle in .

Neben den kontextfreien Sprachen gibt es auch nicht kontextfreie Sprachen, die dieses Pumping-Lemma erfüllen. Die Umkehrung des Lemmas gilt im Allgemeinen also nicht. Eine Verallgemeinerung des Pumping-Lemmas für kontextfreie Sprachen ist Ogdens Lemma.

Beweis Bearbeiten

Gegeben sei eine kontextfreie Grammatik G in Chomsky-Normalform mit Variablen, für die gilt, dass sie gerade die gewünschte Sprache beschreibt. Sei nun ein Wort aus dieser Sprache gegeben, für das gilt: .

Die Idee des Pumping-Lemmas für kontextfreie Sprachen ist, dass ein Wortteil durch mehrfaches Ableiten derselben Variablen beliebig oft wiederholt werden kann.

Betrachten wir nun einen Ableitungsbaum T für mit Höhe h. Da unsere Sprache in CNF angegeben wurde, hat T die Form eines Binärbaumes. Daraus folgt für die Höhe von T . Es gibt also einen Pfad in T von der Wurzel zu einem Blatt, für den gilt, dass er Länge hat. Es existieren also zwei Knoten auf diesem Pfad mit , welche die gleichen Variablen von G repräsentieren.

Betrachtet man den Teilbaum , welcher von aus aufgespannt wird, so bilden dessen Blätter den Teilstring . Der Teilbaum , welcher von aufgespannt wird, besitzt als Teilbaum den Baum . Man kann also die Blätter von aufteilen in Blätter links von und Blätter rechts von und erhält somit eine Aufteilung der Blätter von der Form . Ebenso unterteilt der Teilbaum den gesamten Ableitungsbaum in drei Teile . Wir erhalten also als Aufteilung die Teilstrings , welche im Ableitungsbaum links bzw. rechts von dem von aufgespannten Teilbaum liegen, die Teilstrings , welche in dem Teilbaum liegen nicht jedoch in , und zu guter Letzt den Teilstring , welcher in liegt. Da und die gleichen Variablen unserer Grammatik repräsentieren, folgt daraus, dass der Pfad von nach beliebig oft wiederholt werden kann. Durch eine Wiederholung des Pfades würden wir Worte der Form erzeugen, ohne unsere Sprache zu verlassen. Womit wir das Pumping-Lemma für kontextfreie Sprachen bewiesen hätten.

Beispiel Bearbeiten

Das Wort enthält höchstens zwei verschiedene Buchstaben.

Ist die Sprache kontextfrei?

Wir nehmen an, sei kontextfrei. Sei dann die zugehörige Konstante aus dem Pumping-Lemma.

Wir betrachten das Wort . Es muss dann eine Zerlegung geben, so dass , , für alle ist. Da , enthält das Wort höchstens zwei verschiedene Buchstaben. Deshalb, und da gilt, enthält nicht von allen drei Buchstaben gleich viele, ist also nicht in enthalten. Das ist ein Widerspruch; die Annahme, sei kontextfrei, ist also falsch.

Eine nicht-kontextfreie Sprache, die dem Pumping-Lemma genügt Bearbeiten

Die Sprachen und sind nicht kontextfrei. Allerdings erfüllen und die Eigenschaften des Pumping-Lemmas: Enthält ein Wort nicht den Buchstaben , so gilt dies auch für alle Wörter . Ist der Buchstabe hingegen enthalten, gibt es eine Zerlegung mit ( bezeichne das leere Wort), und einem Suffix , sodass abermals alle Wörter in enthalten sind. Für lässt sich und wählen, und damit ist in enthalten.

Einzelnachweise Bearbeiten

  1. Skript (PDF; 1,1 MB) Humboldt-Universität Berlin
  2. Jeffrey Jaffe: A necessary and sufficient pumping lemma for regular languages. doi:10.1145/990524.990528
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das Pumping Lemma bzw Pumplemma auch Schleifensatz genannt beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen In vielen Fallen lasst sich anhand des Lemmas nachweisen dass eine formale Sprache nicht regular bzw nicht kontextfrei ist Seinen Namen hat das Lemma vom englischen Begriff to pump zu deutsch aufpumpen Es leitet sich davon ab dass Teile von Wortern aus Sprachen bestimmter Klassen vervielfacht aufgepumpt werden konnen so dass die dabei entstehenden Worter ebenfalls in der Sprache sind Man unterscheidet zunachst zwischen dem Pumping Lemma fur regulare Sprachen und jenem fur kontextfreie Sprachen In der Literatur sind weiterhin Pumping Lemmata fur Erweiterungen der kontextfreien Sprachen anzutreffen Machtigere Sprachklassen in der Chomsky Hierarchie wie die kontextsensitiven Sprachen und auch die wachsend kontextsensitiven Sprachen ermoglichen jedoch kein Pumping Lemma Alternativ wird das Lemma bzw seine Auspragungen auch als uvw Theorem uvwxy Theorem Schleifenlemma Iterationslemma oder Lemma von Bar Hillel bezeichnet Inhaltsverzeichnis 1 Regulare Sprachen 1 1 Pumping Lemma fur regulare Sprachen 1 2 Beweis 1 3 Beispiel 1 4 Eine nicht regulare Sprache die den Bedingungen des Pumping Lemmas genugt 1 5 Jaffes Pumping Lemma 2 Kontextfreie Sprachen 2 1 Pumping Lemma fur kontextfreie Sprachen 2 2 Beweis 2 3 Beispiel 2 4 Eine nicht kontextfreie Sprache die dem Pumping Lemma genugt 3 EinzelnachweiseRegulare Sprachen BearbeitenPumping Lemma fur regulare Sprachen Bearbeiten Fur jede regulare Sprache L displaystyle L nbsp gibt es eine naturliche Zahl n displaystyle n nbsp sodass gilt Jedes Wort z displaystyle z nbsp in L displaystyle L nbsp mit Mindestlange n displaystyle n nbsp hat eine Zerlegung z u v w displaystyle z uvw nbsp mit den folgenden drei Eigenschaften Die beiden Worter u displaystyle u nbsp und v displaystyle v nbsp haben zusammen hochstens die Lange n displaystyle n nbsp Das Wort v displaystyle v nbsp ist nicht leer Fur jede naturliche Zahl mit 0 i displaystyle i nbsp ist das Wort u v i w displaystyle uv i w nbsp in der Sprache L displaystyle L nbsp d h die Worter u w displaystyle uw nbsp u v w displaystyle uvw nbsp u v v w displaystyle uvvw nbsp u v v v w displaystyle uvvvw nbsp usw sind alle in der Sprache L displaystyle L nbsp Das kleinste n displaystyle n nbsp das diese Eigenschaften erfullt wird Pumping Zahl der Sprache L displaystyle L nbsp genannt 1 Neben den regularen Sprachen gibt es auch nicht regulare Sprachen die dieses Lemma erfullen Eine notwendige und hinreichende Bedingung fur regulare Sprachen liefern der Satz von Myhill Nerode oder Jaffes Pumping Lemma Das Pumping Lemma enthalt mehrere Wechsel zwischen universeller und existentieller Quantifizierung Diese kann man gut anhand der folgenden formalen Formulierung des Lemmas erkennen Darin bezeichnet L 3 displaystyle mathcal L 3 nbsp die Menge aller regularer Sprachen L L 3 n N z L z n u v w z u v w u v n v gt 0 i N 0 u v i w L displaystyle begin aligned forall L in mathcal L 3 exists n in mathbb N forall z in L z geq n implies exists u v w amp z u circ v circ w land amp uv leq n land amp v gt 0 land amp forall i in mathbb N 0 u circ v i circ w in L end aligned nbsp Beweis Bearbeiten Die Gultigkeit des Lemmas basiert darauf dass es zu jeder regularen Sprache einen deterministischen endlichen Automaten gibt der die Sprache akzeptiert Uber einem endlichen Alphabet enthalt eine regulare Sprache mit unendlich vielen Wortern auch solche Worter die mehr Zeichen enthalten als der Automat Zustande hat Zum Akzeptieren solcher Worter muss der Automat also einen Zyklus enthalten der dann in beliebiger Haufigkeit durchlaufen werden kann Die Buchstabenfolge die beim Durchlaufen des Zyklus gelesen wird kann also entsprechend beliebig oft in Wortern der Sprache vorkommen nbsp Die Idee des Pumping Lemmas ist dass ein Wortteil durch einen Zyklus im deterministischen endlichen Automaten beliebig oft wiederholt werden kann Der folgende Beweis setzt die Mindestlange n displaystyle n nbsp aus dem Lemma mit der Anzahl der Zustande des Automaten gleich und zeigt dass wegen der Existenz eines Zyklus jedes Wort mit dieser Mindestlange die geforderte Zerlegung besitzt Sei L displaystyle L nbsp eine regulare Sprache Ist L displaystyle L nbsp endlich dann gibt es ein Wort mit maximaler Lange k displaystyle k nbsp Sei n k 1 displaystyle n k 1 nbsp so ist fur alle z L displaystyle z in L nbsp die Pramisse z n displaystyle z geq n nbsp falsch und die Implikation damit wahr Ist L displaystyle L nbsp unendlich dann sei M displaystyle M nbsp ein deterministischer endlicher Automat der L displaystyle L nbsp akzeptiert Da L displaystyle L nbsp regular ist existiert ein solcher Automat M displaystyle M nbsp immer Sei n displaystyle n nbsp die Anzahl der Zustande dieses Automaten und sei z displaystyle z nbsp ein beliebiges Wort aus L displaystyle L nbsp mit mindestens n displaystyle n nbsp Zeichen Bezeichne nun mit q 1 q k displaystyle q 1 to dots to q k nbsp die Zustandsfolge die M displaystyle M nbsp beim Lesen von z displaystyle z nbsp beginnend mit dem Startzustand q 1 displaystyle q 1 nbsp durchlauft Da z displaystyle z nbsp in L displaystyle L nbsp ist muss z displaystyle z nbsp von M displaystyle M nbsp akzeptiert werden d h q k displaystyle q k nbsp muss ein akzeptierender Zustand sein Da der Automat M displaystyle M nbsp gerade n displaystyle n nbsp Zustande hat muss spatestens nach dem Lesen von n displaystyle n nbsp Zeichen eine Zustandswiederholung eintreten Das heisst es existieren i j 1 n 1 displaystyle i j in 1 dots n 1 nbsp mit i j displaystyle i neq j nbsp und q i q j displaystyle q i q j nbsp Der Automat M displaystyle M nbsp durchlauft beim Lesen von z displaystyle z nbsp also einen Zyklus Sei v displaystyle v nbsp der Teil von z displaystyle z nbsp der beim Durchlaufen des Zyklus q i q j displaystyle q i to dots to q j nbsp gelesen wird Ferner sei u displaystyle u nbsp der Teil von z displaystyle z nbsp der beim Durchlaufen der davor liegenden Zustandsfolge q 1 q i displaystyle q 1 to dots to q i nbsp gelesen wird und w displaystyle w nbsp sei der Teil von z displaystyle z nbsp der beim Durchlaufen der dahinter liegenden Zustandsfolge q j q k displaystyle q j to dots to q k nbsp gelesen wird Mit dieser Wahl gilt z u v w displaystyle z uvw nbsp Mit dieser Wahl von u displaystyle u nbsp v displaystyle v nbsp und w displaystyle w nbsp gelten die Aussagen aus dem Pumping Lemma Die Lange von u v displaystyle uv nbsp ist j 1 displaystyle j 1 nbsp und somit nicht grosser als n displaystyle n nbsp Das Wort v displaystyle v nbsp ist nicht leer da i j displaystyle i neq j nbsp gilt so dass beim Durchlauf des Zyklus mindestens ein Zeichen gelesen wird Fur beliebiges m 0 displaystyle m geq 0 nbsp durchlauft der Automat beim Lesen des Worts u v m w displaystyle uv m w nbsp zunachst die Zustandsfolge q 1 q i displaystyle q 1 to dots to q i nbsp dann m displaystyle m nbsp mal den Zyklus q i q j displaystyle q i to dots to q j nbsp und schliesslich die Zustandsfolge q j q k displaystyle q j to dots to q k nbsp Am Ende befindet sich der Automat im akzeptierenden Zustand q k displaystyle q k nbsp Somit gilt u v m w L displaystyle uv m w in L nbsp fur alle m 0 displaystyle m geq 0 nbsp Beispiel Bearbeiten Ist die Sprache L a m b m m 1 displaystyle L left a m b m mid m geq 1 right nbsp regular Angenommen L displaystyle L nbsp sei eine regulare Sprache Dann gibt es gemass Pumping Lemma eine Zahl n displaystyle n nbsp so dass sich alle Worter z L displaystyle z in L nbsp mit z n displaystyle left z right geq n nbsp wie beschrieben zerlegen lassen Insbesondere gibt es eine Zerlegung u v w displaystyle uvw nbsp mit den beschriebenen Eigenschaften fur das Wort a n b n L displaystyle a n b n in L nbsp Da u v displaystyle uv nbsp ein Prafix dieses Wortes ist und gemass Eigenschaft 1 hochstens Lange n displaystyle n nbsp hat besteht u v displaystyle uv nbsp und damit v displaystyle v nbsp ausschliesslich aus Buchstaben a displaystyle a nbsp Gemass Eigenschaft 3 fur i 2 displaystyle i 2 nbsp muss auch das Wort u v 2 w a n v b n displaystyle uv 2 w a n left v right b n nbsp in L displaystyle L nbsp liegen Da aber v gt 0 displaystyle left v right gt 0 nbsp Eigenschaft 2 enthalt dieses Wort mehr a displaystyle a nbsp als b displaystyle b nbsp liegt also nicht in L displaystyle L nbsp Also fuhrt die Annahme L displaystyle L nbsp sei eine regulare Sprache zum Widerspruch und ist damit falsch Eine nicht regulare Sprache die den Bedingungen des Pumping Lemmas genugt Bearbeiten Die Sprache L a m b n c n m n 1 b m c n m n 0 displaystyle L left a m b n c n mid m n geq 1 right cup b m c n mid m n geq 0 nbsp ist nicht regular Allerdings erfullt L displaystyle L nbsp die Eigenschaften des Pumping Lemmas denn jedes Wort z L displaystyle z in L nbsp lasst sich so zerlegen z u v w displaystyle z uvw nbsp dass auch fur alle i 0 displaystyle i geq 0 nbsp u v i w L displaystyle uv i w in L nbsp Dazu kann v displaystyle v nbsp einfach als erster Buchstabe gewahlt werden Dieser ist entweder ein a displaystyle a nbsp die Anzahl von fuhrenden a displaystyle a nbsp s ist beliebig Oder er ist ein b displaystyle b nbsp oder c displaystyle c nbsp ohne fuhrende a displaystyle a nbsp s ist aber die Anzahl von fuhrenden b displaystyle b nbsp s oder c displaystyle c nbsp s beliebig Jaffes Pumping Lemma Bearbeiten Jeffrey Jaffe hat ein verallgemeinertes Pumping Lemma entwickelt 2 das aquivalent zur Definition der regularen Sprachen ist Es ist also eine notwendige und hinreichende Bedingung zum Nachweis der Regularitat einer Sprache Die Sprache L S displaystyle L subseteq Sigma nbsp ist regular genau dann wenn eine Konstante n gt 0 n N displaystyle n gt 0 n in mathbb N nbsp existiert so dass es fur alle z S displaystyle z in Sigma nbsp z n displaystyle z n nbsp eine Zerteilung z u v w displaystyle z uvw nbsp mit u w S v S displaystyle u w in Sigma v in Sigma nbsp gibt so dass fur alle i 0 displaystyle i geq 0 nbsp und Suffixe x S displaystyle x in Sigma nbsp gilt z x L u v i w x L displaystyle zx in L iff uv i wx in L nbsp Kontextfreie Sprachen BearbeitenPumping Lemma fur kontextfreie Sprachen Bearbeiten Fur jede kontextfreie Sprache L displaystyle L nbsp gibt es eine naturliche Zahl n displaystyle n nbsp sodass gilt Jedes Wort z displaystyle z nbsp in L displaystyle L nbsp mit Mindestlange n displaystyle n nbsp hat eine Zerlegung z u v w x y displaystyle z uvwxy nbsp mit den folgenden drei Eigenschaften Die Worter v displaystyle v nbsp w displaystyle w nbsp und x displaystyle x nbsp haben zusammen hochstens die Lange n displaystyle n nbsp d h v w x n displaystyle vwx leq n nbsp Eines der Worter v displaystyle v nbsp x displaystyle x nbsp ist nicht leer Also v x 1 displaystyle vx geq 1 nbsp Fur jede naturliche Zahl mit 0 i displaystyle i nbsp ist das Wort u v i w x i y displaystyle uv i wx i y nbsp in der Sprache L displaystyle L nbsp d h die Worter u w y displaystyle uwy nbsp u v w x y displaystyle uvwxy nbsp u v v w x x y displaystyle uvvwxxy nbsp usw liegen alle in L displaystyle L nbsp Neben den kontextfreien Sprachen gibt es auch nicht kontextfreie Sprachen die dieses Pumping Lemma erfullen Die Umkehrung des Lemmas gilt im Allgemeinen also nicht Eine Verallgemeinerung des Pumping Lemmas fur kontextfreie Sprachen ist Ogdens Lemma Beweis Bearbeiten Gegeben sei eine kontextfreie Grammatik G in Chomsky Normalform mit N displaystyle N nbsp Variablen fur die gilt dass sie gerade die gewunschte Sprache beschreibt Sei nun ein Wort x displaystyle x nbsp aus dieser Sprache gegeben fur das gilt x 2 N n displaystyle left x right geq 2 left N right n nbsp nbsp Die Idee des Pumping Lemmas fur kontextfreie Sprachen ist dass ein Wortteil durch mehrfaches Ableiten derselben Variablen beliebig oft wiederholt werden kann Betrachten wir nun einen Ableitungsbaum T fur x displaystyle x nbsp mit Hohe h Da unsere Sprache in CNF angegeben wurde hat T die Form eines Binarbaumes Daraus folgt fur die Hohe von T h log n N displaystyle h geq log n left N right nbsp Es gibt also einen Pfad v 0 v h displaystyle v 0 ldots v h nbsp in T von der Wurzel zu einem Blatt fur den gilt dass er Lange h 1 gt N displaystyle h 1 gt left N right nbsp hat Es existieren also zwei Knoten v j v k displaystyle v j v k nbsp auf diesem Pfad mit 0 j lt k h displaystyle 0 leq j lt k leq h nbsp welche die gleichen Variablen von G A j A k displaystyle A j A k nbsp reprasentieren Betrachtet man den Teilbaum T k displaystyle T k nbsp welcher von v k displaystyle v k nbsp aus aufgespannt wird so bilden dessen Blatter den Teilstring w displaystyle w nbsp Der Teilbaum T j displaystyle T j nbsp welcher von v j displaystyle v j nbsp aufgespannt wird besitzt als Teilbaum den Baum T k displaystyle T k nbsp Man kann also die Blatter von T j displaystyle T j nbsp aufteilen in Blatter links von T k displaystyle T k nbsp und Blatter rechts von T k displaystyle T k nbsp und erhalt somit eine Aufteilung der Blatter von T j displaystyle T j nbsp der Form v w x displaystyle vwx nbsp Ebenso unterteilt der Teilbaum T j displaystyle T j nbsp den gesamten Ableitungsbaum in drei Teile u v w x y displaystyle u vwx y nbsp Wir erhalten also als Aufteilung die Teilstrings u y displaystyle u y nbsp welche im Ableitungsbaum links bzw rechts von dem von v j displaystyle v j nbsp aufgespannten Teilbaum liegen die Teilstrings v x displaystyle v x nbsp welche in dem Teilbaum T j displaystyle T j nbsp liegen nicht jedoch in T k displaystyle T k nbsp und zu guter Letzt den Teilstring w displaystyle w nbsp welcher in T k displaystyle T k nbsp liegt Da v j displaystyle v j nbsp und v k displaystyle v k nbsp die gleichen Variablen unserer Grammatik reprasentieren folgt daraus dass der Pfad von v j displaystyle v j nbsp nach v k displaystyle v k nbsp beliebig oft wiederholt werden kann Durch eine Wiederholung des Pfades wurden wir Worte der Form u v i w x i y displaystyle uv i wx i y nbsp erzeugen ohne unsere Sprache zu verlassen Womit wir das Pumping Lemma fur kontextfreie Sprachen bewiesen hatten Beispiel Bearbeiten nbsp Das Wort v w x displaystyle vwx nbsp enthalt hochstens zwei verschiedene Buchstaben Ist die Sprache L a m b m c m m 1 displaystyle L left a m b m c m mid m geq 1 right nbsp kontextfrei Wir nehmen an L displaystyle L nbsp sei kontextfrei Sei dann n displaystyle n nbsp die zugehorige Konstante aus dem Pumping Lemma Wir betrachten das Wort z a n b n c n displaystyle z a n b n c n nbsp Es muss dann eine Zerlegung z u v w x y displaystyle z uvwxy nbsp geben so dass v x 1 displaystyle left vx right geq 1 nbsp v w x n displaystyle left vwx right leq n nbsp u v i w x i y L displaystyle uv i wx i y in L nbsp fur alle i 0 displaystyle i geq 0 nbsp ist Da v w x n displaystyle left vwx right leq n nbsp enthalt das Wort v w x displaystyle vwx nbsp hochstens zwei verschiedene Buchstaben Deshalb und da v x 1 displaystyle left vx right geq 1 nbsp gilt enthalt u v 2 w x 2 y displaystyle uv 2 wx 2 y nbsp nicht von allen drei Buchstaben gleich viele ist also nicht in L displaystyle L nbsp enthalten Das ist ein Widerspruch die Annahme L displaystyle L nbsp sei kontextfrei ist also falsch Eine nicht kontextfreie Sprache die dem Pumping Lemma genugt Bearbeiten Die Sprachen L 1 a n b n n n N displaystyle L 1 a n b n n n in mathbb N nbsp und L 2 a k b l c m d n k l m n N k 0 oder l m n displaystyle L 2 left a k b l c m d n mid k l m n in mathbb N k 0 text oder l m n right nbsp sind nicht kontextfrei Allerdings erfullen L 1 displaystyle L 1 nbsp und L 2 displaystyle L 2 nbsp die Eigenschaften des Pumping Lemmas Enthalt ein Wort z L 2 displaystyle z in L 2 nbsp nicht den Buchstaben a displaystyle a nbsp so gilt dies auch fur alle Worter u v i w x i y displaystyle uv i wx i y nbsp Ist der Buchstabe a displaystyle a nbsp hingegen enthalten gibt es eine Zerlegung mit u v w e displaystyle u v w varepsilon nbsp e displaystyle varepsilon nbsp bezeichne das leere Wort x a displaystyle x a nbsp und einem Suffix y displaystyle y nbsp sodass abermals alle Worter u v i w x i y displaystyle uv i wx i y nbsp in L 2 displaystyle L 2 nbsp enthalten sind Fur L 1 displaystyle L 1 nbsp lasst sich v displaystyle v nbsp und x e displaystyle x varepsilon nbsp wahlen und damit ist u v i w x i y displaystyle uv i wx i y nbsp in L 1 displaystyle L 1 nbsp enthalten Einzelnachweise Bearbeiten Skript PDF 1 1 MB Humboldt Universitat Berlin Jeffrey Jaffe A necessary and sufficient pumping lemma for regular languages doi 10 1145 990524 990528 Abgerufen von https de wikipedia org w index php title Pumping Lemma amp oldid 227114708