Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Pumping-Lemma, ich verstehe es nicht
Autor
Ausbildung Pumping-Lemma, ich verstehe es nicht
mantonio
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.02.2010
Mitteilungen: 28
  Themenstart: 2010-02-01

hallo, ich beschäftige mich gerade im zuge einer klausur mit u.a. mit den formalen sprachen. ich habe hier 6 bücher liegen und bin langsam am verzweifeln, weil ich das pumping lemma einfach nicht verstehe. diese mathematische erklärungsweise macht es einfach nicht verständlich. ich verstehe nur, dass man im zusammenhang mit regulären sprachen zeigen kann, ob eine gegebene sprache regulär ist, oder nicht. dann hörts aber schon auf. kann mir denn bitte mal jemand "auf deutsch" erklären, was es damit auf sich hat und wie man es anwendet? oder weiß vielleicht jemand eine quelle, wo ich solche eine verständliche erklärung finden kann? das wäre mir eine riesen hilfe. grüße, mantonio


   Profil
wenigraffer
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.10.2009
Mitteilungen: 265
  Beitrag No.1, eingetragen 2010-02-01

Hi. Hm. Ich glaube, (vielleicht erklärt es ja jemand so toll, dass ich das zurücknehmen muss) dass es besser ist wenn du aus einem Buch oder wie auch immer das Vorgehen hier aufschreibst und dann explizit eine Stelle nennst, ab der du nicht mehr folgst. 1) macht das weniger Mühe für deine Helfer 2) hast du dann nach der Klärung den formalen Aufschrieb verstanden, das hilft dir dann beim nächsten Kapitel Ich habe mir gerade den Wikipedia Artikel durchgelesen, der Beweis ist wirklich sehr ausführlich und klar. de.wikipedia.org/wiki/Pumping-Lemma


   Profil
Otis
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.10.2007
Mitteilungen: 955
Wohnort: München
  Beitrag No.2, eingetragen 2010-02-01

\quoteon(2010-02-01 10:23 - mantonio im Themenstart) dass man im zusammenhang mit regulären sprachen zeigen kann, ob eine gegebene sprache regulär ist, oder nicht. \quoteoff Hi, Soweit ich mich erinnern kann, kann man mit dem Pumping-Lemmas nur nachweisen, dass eine Sprache nicht regulär ist. Die Pumping-Lemmas sind nicht dazu da um zu beweisen, dass die Sprache regulär ist. mfg Otis [Die Antwort wurde vor Beitrag No.1 begonnen.]


   Profil
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2032
  Beitrag No.3, eingetragen 2010-02-01

Hallo zusammen, es gibt auf dem Matheplaneten übrigens auch einen  Artikel zum Pumping-Lemma. Vielleicht hilft der ein wenig? Grüße, Thorsten


   Profil
Hans-Juergen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.03.2003
Mitteilungen: 1498
Wohnort: Henstedt-Ulzburg
  Beitrag No.4, eingetragen 2010-02-01

Hallo mantonio, ich versteh's zwar auch nicht (und muß es zum Glück auch nicht verstehen), aber hier steht wenigstens etwas in Worten (und nicht nur in abstrakten Zeichenfolgen), das das Ganze vielleicht ein wenig klarer macht. Mit freundlichem Gruß, Hans-Jürgen


   Profil
xycolon
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 11.11.2004
Mitteilungen: 2643
Wohnort: Herten
  Beitrag No.5, eingetragen 2010-02-01

der artikel zum pumping-lemma ist sehr gut. das lemma ist auch nicht schwer zu verstehen, man wird halt einfach von der mathematischen schreibweise geschockt, wenn man es das erste mal sieht ^^ mal in ganz kurz und auf deutsch: zunächst mal sollte man sich die alternierenden quantoren klarmachen. für alle regulären sprachen --> also eine aussage für jede sprache existiert ein n --> dies wird im beweis zur anzahl der zustände eines automaten für die sprache lassen sich alle wörter mit mehr als n zeichen zerlegen --> ist klar, wenn der automat nur n zustände hat aber mehr als n zeichen ausgibt, muss er eine schleife durchlaufen kann man für alle i die schleife pumpen. man kann also diesen kreis im automaten beliebig oft durchlaufen. was man damit macht, ist das gegenteil zu zeigen: wenn man eine sprache hat, so dass man einen wortteil nicht pumpen kann, kann kann es auch gar keine reguläre sprache gewesen sein. gruß, xycolon


   Profil
uhnlareewomkm
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 30.01.2010
Mitteilungen: 19
  Beitrag No.6, eingetragen 2010-02-01

Ja das ging mir genauso, aber ich denke, ich habs mittlerweile kapiert. So stell ich mir das vor: Das Schubfachprinzip ist Dir sicher bekannt. Du hast 5 Schubfächer und mehr als 5 Gegenstände, die Du auf alle Schubfächer aufteilen willst. Nun weißt Du, dass in mindestens einer Schublade mehr als ein Gegenstand liegt. Du hast dieses Fach also mehrmals benutzt. In dem Pumping-Lemma kommt eine Pumping-Konstante vor, die je nach Literatur meist n oder k oder ... heißt. Das ist quasi die Anzahl der Schubfächer, die Du benutzt. Jetzt siehst Du zu, dass Du mehr Gegenstände als Schubfächer auftreibst und definierst irgendwie, welche Gegenstände Du in Deinem mehrfach benutzen Schubfach aussehen sollen (das passiert über die Bedingungen im Lemma) Hier kann man dann sehen, dass von einer Grammatik bestimmte Symbole rekursiv sich selbst wieder erzeugen. Deswegen kann man in einem Wort auch Teile "pumpen", weil die eben durch so eine Art Zyklus entstehen. Wenn Du jetzt noch wissen willst, wie Du am Ende die Bedingungen für das Pumping-Lemma für eine konkrete Sprache zusammenlegst, kann ich Dir schwer S. 138 vom Hopcroft [1] empfehlen. Dort gibts "Das Pumping-Lemma als Zwei-Personen-Spiel" und gute Beispiele. Das ist in sofern cool, weil es ein bisschen ans Schiffe-Versenken errinnert ^^ ... wenn Du erst ein paar Beispiele damit hinter Dir hast, dann verstehst Du auch das Lemma an sich. Enjoy!  biggrin [1] books.google.com/books?id=WYRsAAAACAAJ [ Nachricht wurde editiert von uhnlareewomkm am 01.02.2010 19:06:34 ]


   Profil
mantonio
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.02.2010
Mitteilungen: 28
  Beitrag No.7, vom Themenstarter, eingetragen 2010-02-02

danke euch allen für die zahlreichen antworten! mir ist jetzt zumindest mal logisch klar, dass bei einem dfa zwischen 5 zuständen nur 4 kanten sein können und ein wort mit einer länge > 4 zwangsläufig mindestens 1 zustand mittels einer schleife 4 + mind. 1 durchläuft. auch ist mir klar, dass wenn das wort x nach aufteilung in die drei teile uvw einen dfa erfolgreich passiert, dann auch ein wort uvw, bei welchem in v z.b. 3-mal eine schleife über demselben zeichen durchlaufen wird, den automaten erfolgreich passieren muss - die beiden wörter also zur selben sprachen gehören. zwei fragen stellen sich mir ab hier, bzw. hört das verständnis dann hier auf: 1. warum kann es nicht sein, dass 2 zustände zweimal durchlaufen werden (dasselbe zeichen führt dabei entweder in eine schleife in einem zustand oder zum nächsten zustand und dort bei erneuter eingabe in eine schleife)? dadurch würde dann zweimal gepumpt? 2. warum ist es relevant, den ersten teil 'u' und den mittelteil 'v' eines wortes (x = uvw) in beziehung zu setzen, wenn doch immer nur der mittelteil v gepumpt wird? warum ist es also wichtig, dass der betrag von u und v zusammen ( |uv| ) kleiner ist als die anzahl der wiederholungsdurchläufe in v? ( \v^i )? ab der stelle, wo man eine geeignete aufteilung des wortes x in uvw finden muss, wirds für mich unlogisch und nicht mehr verständlich. @uhnlareewomkm das buch hab ich mir gestern bestellt, in der hoffnung, dass es mir bis zum 17.02. (klausurtermin) noch erleuchtung bringt. gruß, mantonio


   Profil
xycolon
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 11.11.2004
Mitteilungen: 2643
Wohnort: Herten
  Beitrag No.8, eingetragen 2010-02-02

hi, \quoteon(2010-02-02 12:32 - mantonio in Beitrag No. 7) danke euch allen für die zahlreichen antworten! 1. warum kann es nicht sein, dass 2 zustände zweimal durchlaufen werden (dasselbe zeichen führt dabei entweder in eine schleife in einem zustand oder zum nächsten zustand und dort bei erneuter eingabe in eine schleife)? dadurch würde dann zweimal gepumpt? \quoteoff es kann durchaus sein, dass es zwei schleifen gibt. das ist auch durch das lemma nicht verboten. \quoteon(2010-02-02 12:32 - mantonio in Beitrag No. 7) 2. warum ist es relevant, den ersten teil 'u' und den mittelteil 'v' eines wortes (x = uvw) in beziehung zu setzen, wenn doch immer nur der mittelteil v gepumpt wird? warum ist es also wichtig, dass der betrag von u und v zusammen ( |uv| ) kleiner ist als die anzahl der wiederholungsdurchläufe in v? ( \v^i )? ab der stelle, wo man eine geeignete aufteilung des wortes x in uvw finden muss, wirds für mich unlogisch und nicht mehr verständlich. \quoteoff wenn du einen kreis hast, dann muss der innerhalb der ersten n zeichen auftreten. das wort uvw ist so aufgeteilt, dass erst u zeichen gelesen werden, dann ein kreis der länge v (evtl. mehrmals) und anschließend nochmal ein paar zeichen. gruß, xycolon


   Profil
mantonio hat die Antworten auf ihre/seine Frage gesehen.
mantonio wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 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]