Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Nachweis der Regularität - Pumping Lemma
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Nachweis der Regularität - Pumping Lemma
 
Autor Nachricht
Haase
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 17.04.2006
Beiträge: 135
Wohnort: Hamburg

BeitragVerfasst am: 10 März 2008 - 13:12:34    Titel: Nachweis der Regularität - Pumping Lemma

Guten Tag Allerseits,

wäre super wenn Ihr mir helfen könntet. Ich soll mit Pumping Lemma beweisen das {0^n | n ist Kubikzahl} keine reguläre Sprache ist.

Wenn ich n = 8 nehme und damit ist das Wort 0^8 = 0...0
und x,y,z existiert mit y != epsilon, |xy| <=n, k>=0
sei k =? dann ist w' = xy^(k)z = 0...0 }8+|y| = länge von 0...0 was ist dann z?

Ist jetzt schon ein Widerspruch, da z hier nicht zugeteilt werden kann? Oder ist |z| = 0 und damit müsste |y| = -8 werden und damit ist der Widerspruch da |y| nicht negativ werden darf?

Nebenbei: Wie ist das mit dem xyz, wie werden die immer zugeteilt? Und muss man ein k wählen?

Vielen Dank im Voraus
Gruß Haase
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 10 März 2008 - 14:38:11    Titel:

Ich habe nicht verstanden, was du da tust.

Du musst zeigen: Für jedes beliebige n gibt es ein Wort mit mindestens der Länge n, das sich unter keiner Zerlegung aufpumpen lässt.

Nehmen wir also ein beliebiges Wort 0^n mit n=m^3. Jede beliebige Zerlegung des Wortes sieht so aus:

0^a0^b0^c mit a+b+c = n = m^3, b>0 und a+b<n.

Pumpen wir es nun einmal auf haben wir dieses Wort: 0^a0^(2b)0^c.

Jetzt müssen wir nur noch beweisen, dass für jede mögliche Belegung von a, b und c gilt:

n = m^3 = a+b+c < a+2b+c < (m+1)^3

d.h. die Länge des aufgepumpten Wortes liegt echt zwischen zwei aufeinanderfolgenden Kubikzahlen. Damit hat man dann bewiesen, dass das aufgepumpte Wort nicht in der Sprache liegen kann.
Haase
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 17.04.2006
Beiträge: 135
Wohnort: Hamburg

BeitragVerfasst am: 11 März 2008 - 11:24:57    Titel:

Danke Dir. Jetzt habe ich es glaub ich verstanden.

Also wenn ich L = {0^n 1^n |n>=1} habe
dann ist der Widerspruch mit w=xyz da mit:
0.....0 1.....1
n+|y| z
Widerspruch: Es gibt mehr 0en als 1en.
2ter Widerspruch: |y| darf nicht 0 werden?, richtig?
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 11 März 2008 - 12:07:13    Titel:

Du denkst vielleicht richtig, kannst es dann aber nicht formal korrekt aufschreiben.

Du nimmst zu einem beliebigen n das Wort 0^n1^n. Die Besonderheit ist hier, dass für jede Zerlegung xyz wegen |xy|<=n gelten muss: xy = 0^m, m<=n und y = 0^r, r>0. Damit fügt man durch Aufpumpen in jeder Zerlegung mindestens eine 0 hinzu, aber keine 1 und man erhält das Wort

0^(m-r)0^(2r)0^(n-m)1^n mit
m-r + 2r + n-m = n+r > n wegen r>0.
Haase
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 17.04.2006
Beiträge: 135
Wohnort: Hamburg

BeitragVerfasst am: 11 März 2008 - 12:55:33    Titel:

ok danke dir armin.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Nachweis der Regularität - Pumping Lemma
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum