moin,
kann mir mal jemand in verstaendlichen worten das pumping lemma erklaeren? ich habe das skript dazu gelesen und auch den quicktime film studiert.. ich scheitere immer daran, zu verstehen, wo jetzt genau bewiesen wird, dass die Sprache nicht regulaer ist. Konkret: z.b. fuer i=0 ist uv^iw nicht element L -> L ist nicht regulaer..
das kann ich immer nicht so ganz nachvollziehen.. hat jemand vielleicht die musse mir das zu erklaeren?
dakira
WIe du weißt, oder zumindest wissen solltest, lässt sich jede reguläre Sprache durch einen DFA erzeugen. Jeder DFA hat endlich viele Zustände (normalerweise das n des Lemmas). Hast du nun ein Wort, welches länger ist, als die Anzahl der Zustände, dann weißt du, dass mindestens ein Zustand mehrfach angelaufen wurde. Es ist also möglich, von einem Zustand über die Kanten wieder zu sich selbst zu kommen. Wenn man das einmal machen kann, kann man das auch beliebig oft machen. Oder auch einfach weglassen. Man hat also eine Schleife im Automaten, die man beliebig oft durchläuft, bevor man einen Endzustand ansteuert. Wenn jetzt ein beliebiges Wort in der Sprache enthalten ist, welches eine Länge größer n hat, der DFA also eine Schleife (das v im P-Lemma) enthält, dann müssen auch alle Wörter in der Sprache enthalten sein, welche die Schleife beliebig häufig durchlaufen haben. Also muss auch uv^iw in der Sprache enthalten sein, für alle i E N. Dabei muss man natürlich aufpassen, dass man für das v auch die Schleife auswählt.. sonst klappt das nicht…
Zappi
(alles klar?)
[img]
http://images.rapidforum.com/images/i6.gif[/img]
Ich war vorhin bei ihm, um zusammen das Pumping-lemma zu üben *ggg* aber, faul wie ich bin, wollte ich mich nicht bei ihm einloggen, aber natürlich konnte ich ihm auch nicht die Lorbeeren dieses Beitrages überlassen *gggg*
Zappi
kann mir mal jemand in verstaendlichen worten das pumping lemma erklaeren?
Hier mal ne ganz gute Website:
http://www.f-seidel.de/kla/dvspump.htmlUnd noch was gut geschriebenes zu regulären Ausdrücken:
http://www.iti.fh-flensburg.de/lang/compbau/regular.htm
hab noch mal ne frage zum pumping lemma´bzw zu einem teil davon :-)
wenn ich wie in aufgabenblatt F2 zettel 7 Aufgabe 7.2 (2)
beweisen soll dass es nich regulär ist.
und ich dort das ausgesuchte wort zerlegen möchte
das wort wäre bei mir: x= a^1 b^n
muß ich die reinfolge beibehalten? oder kann ich genauso gut:
u= E(leeres Wort) v=b^n und w=a^1 nehmen??
danke schon mal für ne antwort :-)
ne Reihenfolge darf nicht verändert werden ;)
dein Wort ist übrigens auch nicht doll gewählt,
denn die Bedingung n <= 2m <= 3n ist nicht unbedingt erfüllt
