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 - 33121 x read [Outline] Printable version Printer-friendly version -  Choose language   
InformatikThis is the outline view of the article [Show content view]

 

 

Section Kopf
Title Das Pumping-Lemma für reguläre Sprachen
Created 2005-03-18 14:17:36 by Yggdrasil [Änderungshistorie]
contains 273 Bytes


Section 10
Title Defintion
Created 2005-03-18 01:27:01 by Yggdrasil [Änderungshistorie]
contains 1053 Bytes

1326 charactes in tolal


Section 30
Title Reg. Sprachen sind pumpbar
Created 2005-03-18 01:28:11 by Yggdrasil [Änderungshistorie]
contains 2778 Bytes

4104 charactes in tolal


Section 80
Title Beispiele
Created 2005-03-18 01:24:50 by Yggdrasil [Änderungshistorie]
contains 2783 Bytes

6887 charactes in tolal


Section 99
Title Nütliche Links zum Thema PL
Created 2005-05-02 18:17:44 by Yggdrasil [Änderungshistorie]
contains 342 Bytes

7229 charactes in tolal

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 33121
 
Aufrufstatistik des Artikels
Insgesamt 2849 externe Seitenaufrufe zwischen 2012.01 und 2021.12 [Anzeigen]
DomainAnzahlProz
https://matheplanet.com30.1%0.1 %
https://google.com200.7%0.7 %
http://matheplanet.com10%0 %
http://google.de231981.4%81.4 %
http://google.fr1314.6%4.6 %
https://google.de2338.2%8.2 %
https://duckduckgo.com270.9%0.9 %
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.org80.3%0.3 %
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 5 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2021.12.02-2021.12.06 (3x)viewtopic.php?topic=135399
2021.12.04-2021.12.05 (2x)https://google.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 2799 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 (130x)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...
2020-2021 (27x)https://duckduckgo.com/
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
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
2020-2021 (8x)https://www.ecosia.org/
201310-10 (7x)http://google.de/url?sa=t&rct=j&q=primzahlen reguläre sprache
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]