Einfache Pumping-Eigenschaft
-
Danke Leute!
Die Antworten haben mich schon mal einiges weiter gebracht.
Nun möchte ich mit einem indirekten Beweis beweisen, dass $$ L = { 0^n 1^n | n \in \mathbb N} $$ nicht regulär ist.
Ich hab in diesem link http://imageshack.us/photo/my-images/69/92309610.jpg/ ein Bild von einem Beweis gepostet. Was ich hier nicht verstehe, ist,
1.) was $$ n_0$$ ist,
2.) warum es 3 Möglichkeiten gibt die Schleife zu legen,
3.) warum man das Eingabewort z in den 3 Fällen so aufteilen kann, wie es eben hier gemacht wurde...
Was aber dann wieder schlüssig ist, dass die 3 Aufteilungen das Wort aus der Sprache raushaun und somit die gegebene Sprache nicht pumpbar ist.
Könnt ihr mir helfen?
-
Schreib dir mal die Negation des Lemmas hin. Dann erhälst du folgendes Vorgehen:
Sei n0 eine natürliche Zahl.
Wähle z.
Sei uvw = z eine Zerlegung mit |v| ≠ 0 (oft sagt man auch |uv| ≤ n; das ist keine Einschränkung des Lemmas, aber hilft beim Beweisen).
Wähle i, sodass es zum Widerspruch kommt.Als Tipp bei der konkreten Sprache. Schau dir für ein gegebenes n das Wort 0n1n an. Klappt übrigens ziemlich oft, wenn man einzelne Bestandteile des Wortes so lang wie n macht.
-
Hm, sorry da hat sich jetzt ein Edit überschnitten. Ich hab einen Beweis in meinen Unterlagen gefunden. Ich denke es ist sinnvoller wenn wir den Beweis durchgehen und ich mir da erst mal das Grundprinzip erkläre...
-
Wie gesagt: Der Beweis wird leichter, wenn du zusätzlich |uv| <= n annimmst. Den Beweis findest du dann z. B. bei http://www.roeglin.org/teaching/WS2010/AuBI/AuB5.pdf auf Seite 17 (schön als Spiel verpackt
).
-
Mir ist das leider immer noch alles sehr schleierhaft... Ich weiß irgendwie nicht mehr so recht wo ich das alles anpacken soll... Ich hab darüber jetzt schon so viel gelesen aber nix hilft...
Weißt nicht; hat jemand noch eine Idee wie man mir helfen könnte?
-
Danke Leute!
Die Antworten haben mich schon mal einiges weiter gebracht.
Nun möchte ich mit einem indirekten Beweis beweisen, dass $$ L = { 0^n 1^n | n \in \mathbb N} $$ nicht regulär ist.
Ich hab in diesem link http://imageshack.us/photo/my-images/69/92309610.jpg/ ein Bild von einem Beweis gepostet. Was ich hier nicht verstehe, ist,
1.) was $$ n_0$$ ist,
2.) warum es 3 Möglichkeiten gibt die Schleife zu legen,
3.) warum man das Eingabewort z in den 3 Fällen so aufteilen kann, wie es eben hier gemacht wurde...
Was aber dann wieder schlüssig ist, dass die 3 Aufteilungen das Wort aus der Sprache raushaun und somit die gegebene Sprache nicht pumpbar ist.
Könnt ihr mir helfen?
Ich hab jetzt mal von oben nochmal mein eigenen Beitrag zitiert. Vielleicht mag mir ja noch einer die Fragen beantworten...
Danke!
-
OK, wenn dir mein Link nicht geholfen hat (sollte dir auch helfen, deinen Beweis zu verstehen), gehe ich mal auf deine Fragen ein.
vip@r schrieb:
1.) was $$ n_0$$ ist,
Du nimmst an, dass L regulär ist. Dann sagt dir das Pumping-Lemma, dass es n0 gibt, sodass usw. Ein solches n0 sei nun gegeben.
2.) warum es 3 Möglichkeiten gibt die Schleife zu legen,
3.) warum man das Eingabewort z in den 3 Fällen so aufteilen kann, wie es eben hier gemacht wurde...
Naja, das sind nun mal alle Möglichkeiten für v: Entweder ist v = 0i oder v = 1i oder v = 0i1j mit i, j >= 1.
-
-
n0 ist eine Untergrenze für die betrachteten Wortlängen - und afair für diese Aufgabe nicht so wichtig.
-
die Möglichkeiten stehen doch direkt darunter - entweder der Teil v besteht nur aus 0, nur aus 1 oder aus einer beidem.
-
du kannst jedes Wort (das lang genug ist), willkürlich in drei Teile u, v und w zerlegen. Dann mußt du nur noch beobachten, welche Möglichkeiten es gibt, den mittleren Teil unterzubringen.
-
-
Naja, das sind nun mal alle Möglichkeiten für v: Entweder ist v = 0i oder v = 1i oder v = 0i1j mit i, j >= 1.
Ok. Das hab ich nun verstanden. Den Zusammenhang hab ich irgendwie nicht erkannt...
Warum macht man diese Aufteilung aber NUR bei v und nicht auch u oder w?
-
vip@r schrieb:
Warum macht man diese Aufteilung aber NUR bei v und nicht auch u oder w?
Weil die Teile u und w nicht gepumpt werden.
-
In meinem geposteten Bild steht ja diese Zeile drin:
Jedes $$ z \in L $$ mit $$|z| \geq n_0 $$ hat die Form $$ z = 0k1k $$ mit $$ 2\cdot k \geq n_0 $$.
Ein paar Fragen dazu:
- $$ n_0 $$ wird ja anscheinend frei gewählt,
- warum muss $$ n_0 $$ größergleich der Länge von z sein?
- warum wird bei $$ z = 0k1k $$ das in der Aufgabenstellung verwendete n zu einem k gewechselt?
- was sagt mir $$ 2\cdot k \geq n_0 $$?
Weil die Teile u und w nicht gepumpt werden.
Ist das generell so? Es gibt ja anscheinend auch noch eine verschärfte Version PL...
-
vip@r schrieb:
In meinem geposteten Bild steht ja diese Zeile drin:
Jedes $$ z \in L $$ mit $$|z| \geq n_0 $$ hat die Form $$ z = 0k1k $$ mit $$ 2\cdot k \geq n_0 $$.
Ein paar Fragen dazu:
- $$ n_0 $$ wird ja anscheinend frei gewählt,
- warum muss $$ n_0 $$ größergleich der Länge von z sein?
falsch geguckt - n0 ist kleinergleich der Länge von z.
Dieses n0 wird klar, wenn du dir die Herleitung des PL aus endlichen Automaten ansiehst - dort kannst du als n0 die Größe des Automaten verwenden, dann können Wörter, die kürzer sind, häufig nicht gepumpt werden.
- warum wird bei $$ z = 0k1k $$ das in der Aufgabenstellung verwendete n zu einem k gewechselt?
- was sagt mir $$ 2\cdot k \geq n_0 $$?
weil da jemand allgemeiner werden wollte als es unbedingt notwendig ist.
Weil die Teile u und w nicht gepumpt werden.
Ist das generell so? Es gibt ja anscheinend auch noch eine verschärfte Version PL...
Eine verschärfte Version fällt mir atm nicht ein, nur ein weiteres Pumping-Lemma für kontextfreie Sprachen (dort zerlegt man das Wort in fünf Teile).
-
vip@r schrieb:
- $$ n_0 $$ wird ja anscheinend frei gewählt,
Nein, das wird dir vom Lemma gegeben: Angenommen, L sei regulär. Dann gilt das Pumping Lemma. Dann gibt es n_0.
-
Die erste Zeile der 3 Möglichkeiten lautet:
0^{k\_1} \underbrace{0^{k\_2}}_{v} 0^{k_3} 1^{k} $$ mit $$k_2 \geq 1 $$ und $$k\_1 + k\_2 + k_3 = k $$. Dann ist aber $$ u v^0 w = 0^{k\_1+k\_3}1^k \notin LWas ich hier nun noch nicht verstehe ist, warum v später dann zu $$ v^0 $$ wird, wenn doch $$k_2 \geq 1 $$ gilt...
-
Die Pumping-Eigenschaft besagt ja, daß du ein beliebiges i != 1 verwenden kannst und v i-mal wiederholst. Meistens klappt es, wenn du i=0 (v0=ε) oder i=2 (v2=vv) verwendest.
-
angnommen, die Sprache sei regulär
betrachte die Eingabe 0^n 1^n mit ausreichend großem n (z.B. so daß n größer als die Zustandsanzahl eines Automaten ist, der die Sprache akzeptiert)
Die Abarbeitung dieser Eingabe beginnt im Startzustand und endet in einem Endzustand des Automaten.
du weißt, daß du dann im Automaten einen Kreis laufen mußt.
Fall 1. Der Kreis wird durchlaufen beim Abarbeiten von 0^n. Damit kannst du also Wörter in der Sprache erzeugen von der Form 0^m 1^n mit m beliebig groß => Widerspruch
Fall 2. dito mit 1^n => Widerspruch
Fall 3. der Kreis verbraucht ein Teilwort 0^r 1^s mit irgendwelchen r > 0 und s > 0
Dann folgt durch mehrfaches Durchlaufen des kreises: es müßten Wörter von der Form
0.....0 0^r 1^s 0^r 1^s 1......1
in der Sprache enthalten sein => Widerspruchist also in allen Fällen nix => Annahme falsch => Die Sprache 0^n 1^n ist nicht regulär.
-
angnommen, die Sprache sei regulär
betrachte die Eingabe 0^n 1^n mit ausreichend großem n (z.B. so daß n größer als die Zustandsanzahl eines Automaten ist, der die Sprache akzeptiert)
Die Abarbeitung dieser Eingabe beginnt im Startzustand und endet in einem Endzustand des Automaten.
du weißt, daß du dann im Automaten einen Kreis laufen mußt.
Fall 1. Der Kreis wird durchlaufen beim Abarbeiten von 0^n. Damit kannst du also Wörter in der Sprache erzeugen von der Form 0^m 1^n mit m beliebig groß => Widerspruch
Fall 2. dito mit 1^n => Widerspruch
Fall 3. der Kreis verbraucht ein Teilwort 0^r 1^s mit irgendwelchen r > 0 und s > 0
Dann folgt durch mehrfaches Durchlaufen des kreises: es müßten Wörter von der Form
0.....0 0^r 1^s 0^r 1^s 1......1
in der Sprache enthalten sein => Widerspruchist also in allen Fällen nix => Annahme falsch => Die Sprache 0^n 1^n ist nicht regulär.
Irgendwie kann ich mir da trotzdem noch nicht so viel drunter vorstellen. Kann man diese Ausführung von dir mit einem Beispiel durchmachen? Z.B. für das Wort: 01101100?
-
was genau verstehst du denn nicht?
Mit einem einzelnen Wort 01101100 kann man in diesem Zusammenhang wenig widerlegen, zumal das Wort nicht in 0^n 1^n ist.
-
Das Problem das ich damit habe, ist, dass das alles für mich sehr wenig greifbar ist. Ich muss da Beispiele sehen für die das ganze funktioniert... Keine Ahnung wie ich es besser beschreiben soll.
Was soll ich mir denn unter der eingabe 0^n 1^n vorstellen? eine beliebig lange kette von nullen konkateniert mit einer beliebig langen kette von 1. wobei sich das beliebig natürlich auf die zahl beschränkt das hinter n steht, oder?
-
Vielleicht hilft es ja, wenn Du Dir http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS02/F2/uvw-web-Dateien/uvw-web1.html anschaust.
