Informatik: Das Pumping-Lemma für reguläre Sprachen
Released by matroid on Fr. 18. März 2005 14:17:36 [Statistics]
Written by Yggdrasil - 33113 x read [Outline] Printable version Printer-friendly version -  Choose language   
Informatik

\(\begingroup\) Das Pumping-Lemma für reguläre Sprachen Das Pumping-Lemma (PL) hat schon für viel Verwirrung unter angehenden Informatikstudenten gesorgt. Zu unrecht wie ich finde! Deshalb will ich es in diesem Artikel einmal genauer erläutern...

\stress\ Definition: \normal\ Eine Sprache L heißt pumpbar__, falls es eine Zahl k gibt, so dass für alle x \el L mit abs(x) >= k eine Zerlegung x=uvw mit den Eigenschaften 1) abs(v) > 0 2) abs(uv) <= k 3) uv^i\.w \el L \forall i=0,1,2,... existiert. \stress\ Bemerkung: \- Das kleinstmögliche k wird Pumping\-Zahl__ genannt. \- In Quantorenschreibweise könnte man es so formulieren: L pumpbar <=> \exists k\>0 \forall x\el\ L (abs(x)>=k -> \exists u,v,w \el\ \Sigma^\* (x\=uvw \and\ abs(v)\> 0 \and\ abs(uv)<=k \and\ \forall i>=0 ( uv^i\.w \el\ L) Die folgende Umformulierung habe ich mir ausgedacht. \stress\ Definition: \normal\ Ein Wort x einer Sprache L heißt pumpbar__ zur__ Konstanten__ k, falls abs(x)\ 0 2) abs(uv) <= k 3) uv^i\.w \el L \forall i\=0,1,2,... Dann könnte man alternativ formulieren: \stress\ Definition: \normal\ Eine Sprache L heißt pumpbar__, falls ein k existiert, dass alle x\el L pumpbar zur Konstanten k sind.
\stress\ Lemma: \normal\ Alle endlichen Sprachen sind pumpbar. Beweis: Es genügt k:= ma\.x\.menge(abs(x)+1 |x \el L ) zu setzen. Dann ist die Teilmenge L' = menge(x \el L| abs(x) >= k) leer und damit sind die Bedingungen des PL trivialerweise erfüllt.\ \bigbox \stress\ Satz: \normal\ Alle regulären Sprachen sind pumpbar. Beweis: \ Sei L eine reg. Sprache, \ M ein DFA\/NFA, der L erkennt und \ z die Anzahl der Zustände von M Wähle k:=z und sei x=x_1\....x_n ein beliebiges Wort mit abs(x)>=k. Die Zustände, die M nacheinander beim Lesen von x annimmt, will ich mit q_0\.,q_1\.,...,q_n bezeichnen. Weil die Folge (q_i) mehr Folgenglieder als M Zustände hat, muss es zwei Indizies i \ Wählen wir nun u=x_1\....x_i\., v=x_i\+1\....x_j\., w=x_j\+1\....x_n Dann ist abs(v)=j\-i>0 und abs(uv)=j<=k. Nach dem Lesen von u befindet sich M im Zustand q_i. Nach dem Lesen von v erreicht der Automat wieder diesen Zustand, was man dann beliebig oft wiederholen kann. Daher führt das Lesen von uv^i\.w, i\el \IN in den Endzustand q_n. Folglich sind alle uv^i\.w \el L und damit die Bedingungen des PL erfüllt.\ \bigbox \stress\ Bemerkung: - Das PL ist ein mächtiges Werkzeug, wenn es darum geht die Irregularität einer Sprache zu beweisen. Dazu nutzt man die Contraposition der Aussage, die z.B. so formuliert werden kann: L ist nicht pumpbar <=> \forall k\>0 \exists x\el\ L ( abs(x)>=k -> \forall u,v,w \el\ \Sigma^\* ( x\=uvw \and\ v!\=\epsilon \and\ abs(uv)<=k -> \exists i>=0 ( uv^i\.w \notel\ L))) Anders ausgedrückt: L ist nicht pumpbar, wenn für jedes k ein Wort x nicht zur Konstanten k pumpbar ist. Darauf basiert dann auch die grundlegende Struktur aller Irregularitätsbeweise mit PL: Man konstruiert eine Folge (x(k))_(k\el \IN) und zeigt, dass x(k) nicht pumpbar mit Konstante k ist. Wichtig ist dabei, dass man für x(k) alle__ möglichen__ Zerlegungen betrachtet, denn x(k) wäre ja pumpbar, wenn es eine korrekte Zerlegung gibt. Nimmt man dann an, dass die Sprache pumpbar ist, erzeugt es sofort einen Widerspruch. - Die Aussage "Jede pumpbare Sprache ist regulär" gilt nicht__, da es Sprachen gibt, die zwar pumpbar aber nicht regulär sind. Siehe dazu auch das vierte Beispiel.
\stress\ Beispiel 1 L_1 = menge(a^n\.b^n | n>=0) ist nicht regulär. Beweis: Nehmen wir einmal an, dass eine Pumping\-Zahl k existiert und betrachten das Wort x=a^k\.b^k. \small\Bem.: Das gewählte Wort muss__ von k abhängen. Wegen abs(x) = 2k >= k müsste es pumpbar sein, wenn unsere Annahme stimmt. Es muss also eine Zerlegung x=uvw existieren, die das PL erfüllt. Aber für alle Zerlegungen, die Bedingungen 1 und 2 erfüllen gilt: v= a^j, 0 uv^2\.w = a^(k\+j)\.b^k \notel L \small\ Achtung, häufig wird der Fehler begangen nicht alle Zerlegungen betrachtet zu haben. \small\ Das sind u=a^i, v=a^j, w=a^k\-j\-i\.b^k und nicht nur \small\ u=a^k\-j, v=a^j, w=b^k. Unsere Annahme war falsch und es gibt keine Pumping\-Zahl. => L_1 ist nicht pumpbar. => L_1 ist nicht regulär. \stress\ Beispiel 2 L_2 = menge( xx' | x\el {0,1}^\* , x' ist die Spiegelung von x) ist nicht pumpbar. Beweis: Annahme es ex. eine Pumping\-Zahl k. Schauen wir uns die Zerlegungen von x = uvw = 1^k\.001^k an, für die abs(v)>0 und abs(uv)=1,u+v<=k zerlegen lassen, so dass u+i*v+w für alle i prim ist. (x = a^u\.a^v\.a^w) Im Fall i=(u+w) wäre u+(u+w)v + w = (u+w)(v+1) prim, was nicht stimmt. \small\Bem.: (u+w) und (v+1) sind beide >1. \stress\ Beispiel 4 L_4 = menge(a^i\.b^j\.c^k | i=0 oder j=k ) ist nicht regulär, aber pumpbar. Beweis: Wähle z=1. Für alle x=x_1\....x_n \el L mit abs(x)>=z ex. die Zerlegung u=\epsilon, v=x_1, w=x_2\....x_n. => v= fdef(a, falls i!\=0;b, falls i\=0\,j!\=0;c, falls i=j=0) Alle diese Fälle erfüllen die Pumping\-Bedingungen: v!=\epsilon, abs(uv) = 1<=z, uv^i\.w \el L. \small\ Bem.: Im "kritischen" Fall i!=0, in dem j=k gelten muss, wird der b\-c\-Teil nicht verändert. Um nun nachzuweisen, dass L_4 nicht regulär ist, greife ich auf das Prinzip der Äquivalenzklassen zurück, ohne das hier weiter zu erläutern. Da eine Sprache L genau dann regulär ist, wenn die Relation R_L endlich viele Äquivalenzklassen hat, reicht es zu zeigen, dass R_L unendlichen Index hat. Für i=0, j=k, m!=n gilt: L_(b^m) != L_(b^n), da c^m \el L_(b^m) und c^m \notel L_(b^n) \small\ Bem.: Zwei Wörter liegen in unterschiedlichen Äquivalenzklassen, falls ein Wort zu einem Wort der Sprache \small\ ergänzt werden kann, das Andere bei gleicher Ergänzung aber nicht. (b^m\.c^m \el L, b^n\.c^m \notel L) => Es gibt unendlich viele Äquivalenzklassen (n=1,2,...). => L ist nicht regulär.
Hier finden sich einige Threads aus dem Forum zum Thema PL. Der Artikel orientiert sich an diesem Skript, was ich als Einstieg in die Automatentheorie empfehlen kann.
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Grundstudium Informatik :: Informatik :: Automatentheorie :
Das Pumping-Lemma für reguläre Sprachen [von Yggdrasil]  
Anschaulicher Beweis des Pumping-Lemmas für reguläre Sprachen mit zahlreichen Anwendungsbeispielen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 33113
 
Aufrufstatistik des Artikels
Insgesamt 2854 externe Seitenaufrufe zwischen 2012.01 und 2021.11 [Anzeigen]
DomainAnzahlProz
https://matheplanet.com120.4%0.4 %
https://google.com341.2%1.2 %
https://duckduckgo.com270.9%0.9 %
https://google.de2177.6%7.6 %
http://google.de231981.3%81.3 %
http://google.fr1314.6%4.6 %
http://diaet.abnehmen-forum.com250.9%0.9 %
http://google.it140.5%0.5 %
https://www.bing.com120.4%0.4 %
http://www.delta-search.com100.4%0.4 %
https://www.ecosia.org70.2%0.2 %
http://www.bing.com301.1%1.1 %
https://deref-gmx.net20.1%0.1 %
http://www.facebook.com20.1%0.1 %
http://google.com20.1%0.1 %
http://search.conduit.com10%0 %
https://www.startpage.com10%0 %
http://suche.web.de10%0 %
http://de.search.yahoo.com20.1%0.1 %
http://de.ask.com10%0 %
http://ecosia.org10%0 %
https://startpage.com10%0 %
http://www.benefind.de10%0 %
http://r.duckduckgo.com10%0 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 26 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2021.11.04-2021.11.26 (7x)viewtopic.php?topic=135399
2021.11.13-2021.11.26 (2x)viewtopic.php?topic=89413
2021.11.01-2021.11.25 (16x)https://google.com/
2021.11.24 21:13viewtopic.php?topic=38359

Häufige Aufrufer in früheren Monaten
Insgesamt 2777 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
201206-06 (233x)http://google.de/url?sa=t&rct=j&q=zeige pumping lemma
201211-11 (230x)http://google.de/url?sa=t&rct=j&q=zeigen sprache pumpbar
2013-2018 (216x)http://google.de/url?sa=t&rct=j&q=
201205-05 (199x)http://google.de/url?sa=t&rct=j&q=zeigen sie keine reguläre sprache primza...
201207-07 (151x)http://google.de/url?sa=t&rct=j&q=was ist ein pumping lemma?
201209-09 (137x)http://google.de/url?sa=t&rct=j&q=pumping lemma reguläre sprachen erklä...
201201-01 (131x)http://google.fr/url?sa=t&rct=j&q=sprachen die pumping lemma erfüllen aber...
2020-2021 (113x)https://google.de/
201301-01 (112x)http://google.de/url?sa=t&rct=j&q=pumping-lemma
201208-08 (110x)http://google.de/url?sa=t&rct=j&q=pumping lrmma
201202-02 (100x)http://google.de/url?sa=t&source=web&cd=5&ved=0CEwQFjAE
2013-2014 (94x)http://google.de/url?sa=t&rct=j&q=pumping lemma p ist prim
201302-02 (91x)http://google.de/url?sa=t&rct=j&q=pumping-lemma beweis für reguläre spr...
201305-05 (88x)http://google.de/url?sa=t&rct=j&q=sprache regulär pumping lemma
201203-03 (88x)http://google.de/url?sa=t&rct=j&q=tipps pumping lemma
201212-12 (78x)http://google.de/url?sa=t&rct=j&q=theoretische informatik pumping-lemma
202005-05 (65x)https://google.de/url?sa=t
201311-11 (59x)http://google.de/url?sa=t&rct=j&q=zeigen dass sprache nicht regulär ist a^...
201406-06 (51x)http://google.de/url?sa=t&rct=j&q=kontraposition pumping lemma
201204-04 (46x)http://google.de/url?sa=t&rct=j&q=teilmengen regulärer sprachen regulär
201303-03 (34x)http://google.de/url?sa=t&rct=j&q=wie pumpkonstante wählen?
201304-04 (33x)http://google.de/url?sa=t&rct=j&q=pumping lemma reguläre sprachen beispiel
201401-01 (29x)http://google.de/url?sa=t&rct=j&q=pumping lemma für dummies
201306-06 (29x)http://google.de/url?sa=t&rct=j&q=pumping lemma primzahlpotenz
201307-07 (29x)http://google.de/url?sa=t&rct=j&q=viele beispiel pumping lemma kontextfreie s...
201210-10 (26x)http://google.de/url?sa=t&rct=j&q=pumping lemma primzahl
2014-2017 (25x)http://diaet.abnehmen-forum.com/gequassel/184913-pumping-lemma.html
2020-2021 (23x)https://duckduckgo.com/
202105-05 (22x)https://google.de/http://www.bing.com/search?q=pumping lemma
2020-2021 (18x)https://google.com/
202103-08 (16x)https://google.de
201407-07 (14x)http://google.it/url?sa=t&rct=j&q=
201308-08 (13x)http://google.de/url?sa=t&rct=j&q=pumping lemma beispiel
2020-2021 (10x)https://www.bing.com/
201503-03 (10x)http://google.de/url?sa=t&source=web&cd=1&ved=0CBwQFjAA
201307-08 (10x)http://www.delta-search.com/?q=pumping lemma für reguläre sprachen beis...
201412-12 (9x)http://google.de/url?sa=t&source=web&cd=2&ved=0CB4QFjAB
201310-10 (7x)http://google.de/url?sa=t&rct=j&q=primzahlen reguläre sprache
2020-2021 (7x)https://www.ecosia.org/
201403-03 (7x)http://google.de/url?sa=t&rct=j&q=pumping lemma
2014-2018 (5x)http://www.bing.com/search?q=matheplanet pumpinglemma&go=&qs=n&form=QBLH&filt...
201511-11 (5x)http://google.de/url?sa=t&source=web&cd=4&rct=j&q=pumpbar beweisen
201306-07 (4x)http://www.bing.com/search?q=pumping lemma&form=IE10TR&src=IE10TR&pc=MASMJS

[Top of page]

"Informatik: Das Pumping-Lemma für reguläre Sprachen" | 8 Comments
The authors of the comments are responsible for the content.

Re: Das Pumping-Lemma für reguläre Sprachen
von: wasseralm am: Fr. 18. März 2005 15:25:07
\(\begingroup\)Hallo Yggdrasil, ein schöner Text, der in Zukunft die "Arbeit" in den entsprechenden Threads deutlich reduziert, weil man immer auf ihn verweisen kann. Eine winzige Anmerkung habe ich noch (wie immer): Beim Beweis des Satzes "Alle regulären Sprachen sind pumpbar" kann man darauf verzichten, dass der Automat deterministisch sein muss. Dadurch kann man die Pump-Konstante manchmal noch verkleinern. Gruß von Helmut \(\endgroup\)
 

Re: Das Pumping-Lemma für reguläre Sprachen
von: Yggdrasil am: Fr. 18. März 2005 16:10:47
\(\begingroup\)Hallo Wasseralm, du hast recht, es können im Beweis auch NFAs zugelassen werden. Es wird ja nur beweisen, dass die Anzahl der Zustände eine obere Schranke für die Pumping-Zahl ist. Somit ist irrelevant, ob M minimal, DFA oder NFA ist. Den Artikel hab ich geschrieben weil es ja noch keinen Einzigen zur theoretischen Informatik auf dem MP gab. Dem gegenüber stehen aber sehr viele Fragen im Forum, wo immer wieder die selben Hinweise gegeben werden müssen. Das muss geändert werden :)\(\endgroup\)
 

Re: Das Pumping-Lemma für reguläre Sprachen
von: matroid am: Fr. 18. März 2005 17:13:29
\(\begingroup\)Hi Yggdrasil, genau das finde ich auch, die theor. Informatik muß auch mal Flagge zeigen. Du hast dein Thema aus meiner Sicht prima gewählt und auch sehr verständlich ausgeführt. Gruß Matroid\(\endgroup\)
 

Re: Das Pumping-Lemma für reguläre Sprachen
von: wasseralm am: Fr. 18. März 2005 21:16:45
\(\begingroup\)Hallo Yggdrasil und Matroid, zur theoretischen Informatik gab es bereits einen Artikel, und zwar Fixpunkte und eine Semantik für Rekursion von Lochi. Die Resonanz war allerdings nicht so groß, weil das Thema wohl etwas speziell ist. Auch ein sehr schöner Beitrag! Gruß von Helmut\(\endgroup\)
 

Re: Das Pumping-Lemma für reguläre Sprachen
von: shredhead am: Sa. 19. März 2005 18:30:33
\(\begingroup\)Hi Yggdrasil Sehr schöner Artikel. Den Link hierhin werde ich mir merken, denn das erklären des PL im Forum ist doch sehr mühselig - deswegen werden die Fragen die das PL betreffen wohl immer nur sehr kurz beantwortet. Dieser Artikel vereinfacht uns das jetzt! *g* Gruß Jörg\(\endgroup\)
 

Re: Das Pumping-Lemma für reguläre Sprachen
von: wasseralm am: So. 17. April 2005 20:06:31
\(\begingroup\)Hallo Yggdrasil, mir ist noch eine Verbesserungsmöglichkeit eingefallen: Bei der Definition von "pumpbar" lautet die 3. Bedingung uv^i\.w \el L Dabei ist der Wertebereich für i nicht angegeben, er sollte 0, 1, 2, ... sein. Das geht auch aus deiner nachfolgenden Bemerkung über die Kontraposition hervor. Ich finde es aber gut, es hinzuschreiben, weil vielen nicht klar ist, dass man v nicht nur aufpumpen, sondern auch ausschneiden darf. Eine Formulierung der Bedingung, die das auch ganz klar macht, und die man öfters sieht, ist: uv^\*\.w \subsetequal L Gruß von Helmut \(\endgroup\)
 

Artikel aktualisiert
von: Yggdrasil am: Mo. 02. Mai 2005 17:32:25
\(\begingroup\)Hallo Wasseralm, Habe den Artikel deinen Vorschlägen entsprechend verbessert. (Allerdings ist mir dein Kommentar erst heute aufgefallen :)\(\endgroup\)
 

Re: Das Pumping-Lemma für reguläre Sprachen
von: Ex_Mitglied_40174 am: Mo. 19. Dezember 2011 19:39:16
\(\begingroup\)ich raffs trotzdem nicht :( ich kann mir das 100 mal durchlesen. die ganzen indizes etc ich komm einfach nicht auf den punkt. \(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]