Einfache Pumping-Eigenschaft
-
Danke an euch. Ich hab jetzt mal so für mich ein jedes Prolemchen aus dem Weg geräumt. Irgendwie richtig verstanden habe ich es trotzdem nicht, so dass ich sagen könnte, jawohl, dass kann anders gar nicht sein.
Noch eine Frage zu Seite 15 des Links:
Die haben ja die Zerlgung so gemacht:
1.) u = a^k
2.) v = a^l
3.) w = a^(n-k-l) c a^nund dann schreiben die: Dann ist aber für i=0 das Wort u v^i w nicht in L was ein Widerspruch zum PL ist.
Wie folgert man nun daraus, dass das Wort nicht mehr in L ist? Muss man das pro Zerlegung dann prüfen? Also ich hab das ja mal in 1.), 2.) und 3.) Zerlegung untergliedert...
Ich denke, ich werd dazu morgen wohl noch ein paar Fragen stellen. Muss jetzt dann weg...
-
Bilde doch mal das Wort u v^0 w (= u w) - dann kannst du ja anhand der Sprachdefinition prüfen, ob das Ergebnis noch zur Sprache gehört. (Hinweis: die Bedingung, daß l>0 ist, gehört auch zum Pumping-Lemma)
-
vip@r schrieb:
Die haben ja die Zerlgung so gemacht:
1.) u = a^k
2.) v = a^l
3.) w = a^(n-k-l) c a^nund dann schreiben die: Dann ist aber für i=0 das Wort u v^i w nicht in L was ein Widerspruch zum PL ist.
Wie folgert man nun daraus, dass das Wort nicht mehr in L ist?
Naja, wie sieht dann u v^0 w aus? Einfach die Werte von oben einsetzen:
[edit: mach das mal selber ^^]Muss man das pro Zerlegung dann prüfen?
Ja. Aber in diesem Fall gibt es ja praktischerweise nur eine Art von Zerlegung - und die kann man alle auf einmal abhandeln.
-
Naja, wie sieht dann u v^0 w aus?
Ich würd so sagen:
a^k a^(n-k) c a^n
Wenn ich das jetzt von vorne und von hinten lese, dann ist es nicht mehr das Gleich. Ist das quasi nun nicht mehr in der Sprache?
-
Hier nochmal ein kleines Beispiel, ob ich das jetzt mal soweit verstanden hab. Gegeben sie folgende Sprache:
L={a^k | k \in N}
Da ich u=a, v=a und w=a wählen kann, ist die Sprache regulär. Stimmts?
Da die erste Regel |v|≥1 erfüllt ist, die zweite Regel |uv|≤n erfüllt ist und die dritte Regel auch erfüllt ist, da ich das Wort beliebig lange wiederholen darf und ich in der Sprache bleibe, ist somit auch das gesamte PL erfüllt. Soweit richtig?
Ich versuch jetzt mal selber das alles in eigene Worte zu fassen:
1.) Suche geeignete Zerlegung des Wortes
2.) Prüfe die Zerlegung auf die 3 Regeln des PL
3.) Falls alle 3 Regeln erfüllt sind ist das gesamte PL erfüllt und die Sprache ist regulär
4.) Wenn eine der 3 Regeln nicht erfüllt werden ist das gesame PL nicht erfüllt und die Sprache fliegt raus.Ist das soweit alles richtig?
-
png schrieb:
Bei dem einfache Pumping-Lemma muss man aber auch aufpassen, da es nicht-reguläre Sprachen gibt, die das Lemma erfüllen. D.h. du kannst nur Nicht-Regularität mit dem einfachen Pumping-Lemma beweisen(wenn das P-Lemma nicht erfüllt wird), jedoch keine Regularität der Sprache(wenn das P-Lemma erfüllt wird).
Deine dritte Aussage stimmt also nicht.
-
vip@r schrieb:
Naja, wie sieht dann u v^0 w aus?
Ich würd so sagen:
a^k a^(n-k) c a^n
Nein. a^k a^(n-l-k) c a^n.
Wenn ich das jetzt von vorne und von hinten lese, dann ist es nicht mehr das Gleich.
Für Deine Lösung IST das sogar gleich. a^k a^(n-k) = a^n.
-
vip@r schrieb:
Hier nochmal ein kleines Beispiel, ob ich das jetzt mal soweit verstanden hab. Gegeben sie folgende Sprache:
L={a^k | k \in N}
Da ich u=a, v=a und w=a wählen kann
Du kannst jedes Wort der Sprache so zerlegen? Dann wäre ja aaa das einzige Wort in L!
ist die Sprache regulär. Stimmts?
Nein. Du kannst nur nicht mit dem PL zeigen, dass die Sprache nicht regulär ist.
-
Du kannst jedes Wort der Sprache so zerlegen? Dann wäre ja aaa das einzige Wort in L!
Hm, dann hab ich die Zerlegung noch immer nicht verstanden. Wie zerlegt man dann richtig? Ich hab ja a^k; und das will ich jetzt in ein Wort z=uvw zerlegen. Wie macht man das dann?
Dann ist ja dann quasi aaaaaaa auch ein Wort der Sprache...
Stimmt dann die Zerlegung: u=a, v=a^k, w=a. Jetzt sollte ich doch jedes Wort rausbringen, oder? Aber dann passt doch die 2. Regel nicht mehr, oder? Dann wäre ja quasi die Teilwortlänge von uv nicht mehr kleinergleich der Anzahl der Zustände n des Automaten, oder?
-
Was willst Du denn überhaupt zeigen? Oben versuchst Du zu zeigen, dass das PL auf eine Sprache anwendbar ist. Dazu musst Du:
* Ein n angeben.
* Jedes Wort aus der Sprache, das mindestens n Zeichen hat, entsprechend zerlegen.Normalerweise will man aber genau das Gegenteil: Zeigen, dass sich das PL NICHT anwenden lässt (und die Sprache also nicht regulär ist.) Dazu muss man:
* Zu jedem n ein Wort aus der Sprache suchen, das mindestens n Zeichen hat (das schreibt man dann kurz als "ich betrachte z = a^n c a^n" und meint: "Falls n=1, betrachte ich aca. Falls n=2, betrachte ich aacaa. Falls n=3, betrachte ich aaacaaa. usw.")
* Und dann jeweils alle denkbaren Zerlegungen betrachten - und für jede zeigen, dass sie nicht den Bedingungen des PL genügt.
-
vip@r schrieb:
Du kannst jedes Wort der Sprache so zerlegen? Dann wäre ja aaa das einzige Wort in L!
Hm, dann hab ich die Zerlegung noch immer nicht verstanden. Wie zerlegt man dann richtig? Ich hab ja a^k; und das will ich jetzt in ein Wort z=uvw zerlegen. Wie macht man das dann?
Dann ist ja dann quasi aaaaaaa auch ein Wort der Sprache...
Ja, so hast Du die Sprache doch definiert. Alle Worte beliebiger Länge, die nur aus a's bestehen.
Stimmt dann die Zerlegung: u=a, v=a^k, w=a. Jetzt sollte ich doch jedes Wort rausbringen, oder? Aber dann passt doch die 2. Regel nicht mehr, oder? Dann wäre ja quasi die Teilwortlänge von uv nicht mehr kleinergleich der Anzahl der Zustände n des Automaten, oder?
Naja, erstmal müsstest Du überhaupt ein n angeben, mit dem man vergleichen kann. Aber versuchs mal mit u=a, v=a, w=a^k-2
-
Ich möchte zeigen, dass die Sprache regulär ist. Also muss doch das PL erfüllt sein.
-
Um zu zeigen, daß eine Sprache regulär ist, gibt es auch einfachere Möglichkeiten als das Pumping-Lemma
(z.B. einen Automaten bauen, der diese Sprache akzeptiert)
-
vip@r schrieb:
Ich möchte zeigen, dass die Sprache regulär ist.
Dabei hilft Dir aber das PL nicht.
-
Ich möchte nun für die Sprache L={0n1n |n != m} regularität widerlegen oder beweisen. Das Pumping-Lemma soll aber nicht verwendet werden. Aus welcher Menge n bzw. m stammt ist nicht angegeben. Also gehe ich mal davon aus, dass n,m aus N stammt. Muss ich dafür jetzt einen Automaten bauen? Das sollte aber schwierig werden, da man da mit dem zeichnen nicht mehr fertig wird. Wie soll man dann die evtl. regularität dann widerlegen? Denn ich denke nicht, dass es für diese Sprachen einen Automaten gibt, der die Sprache akzeptiert...
-
Tippfehler in der Sprachdefinition? Das einzelne m sieht strange aus.
-
Oh Sorry! Ja, da is ein Tippfehler. So sieht's aus: L={0n1m |n != m}
-
Was für eine Funktion hat denn das m in dieser Sprachdefinition?Ansonsten kannst du eventuell davon ausgehen, daß 0n1n nicht regulär ist und die regulären Sprachen über Vereinigung und Komplement abgeschlossen sind.(oder du versuchst tatsächlich einen Automaten zu bauen, der die Sprache akzeptiert)
-
Das m gibt doch an wie viele 1 in der Sprache sind und n ist eben ungleich diesem m, wobei das nicht darüber aussagt, ob m kleiner oder größer dem n ist.
-
die regulären Sprachen über Vereinigung und Komplement abgeschlossen sind.
Meinst du damit die Abschlusseigenschaften von regulären Sprachen? Wenn ja, dann sollte mir hier aber die Vereinigung nich so allzuviel bringen weil ich ja keine 2. Sprache hab mit der ich vereinigen könnte. Also bleibt mir nur noch das Komplement.
Also quasi (L)^c.