Einfache Pumping-Eigenschaft
-
Hi Leute!
Ich hab mich heute über die einfache Pumping-Eigenschaft von regulären Sprachen gemacht. Aber irgendwie verstehe ich das ganze so gar nicht...
Hier mal kurz die Definition bzw. Gedanken dazu:
Sei L eine reguläre Sprache. Dann gibt es ein $$ n_0 \in \mathbb N$$ mit $$n_0 \geq 1$$, so dass man für alle $$z \in L$$ mit $$|z| \geq n_0$$ eine Zerlegung $$z=uvw$$ finden kann, welche die Pumping-Eigenschaft erfüllt.
1. $$v \neq \epsilon$$
2. $$ \forall i \in \mathbb N:$$ $$uv^iw \in L$$-> L ist einfach pumpbar.
Es wäre sehr nett, wenn mir das jemand hier jetzt nicht ganz so mathematische erklären könnte, denn so verstehe ich das irgendwie nicht. Es hängt aber nicht an der Mathematik oder, dass ich nicht weiß was die einzelnen Buchstaben (hier ja Wörter) bedeuten, sondern eher so ein bisschen was das bringen soll!
Danke für eure Hilfe!
-
Die Hauptanwendung ist sicherlich die Negation: Wenn du ein Wort findest, sodass die genannte Eigenschaft nicht gilt, dann ist die Sprache nicht regulär.
-
nimm einen endlichen Automat A, der die reguläre Sprache akzeptiert. A hat nur endlich viele mögliche Zustände.
wenn du nun mit einem Eingabewort z durch den Automaten fährst, und z ist länger als die Anzahl der Zustände von A, dann muß irgendeiner der Zustände zweimal (oder öfter) besucht werden.
Du fährst also unvermeidlich einen Kreis im Automaten.
Diesen Kreis kannst du nun beliebig oft durchlaufen, und bleibst trotzdem innerhalb der regulären Sprache.
Formal:
wenn z = z1 z2 z3, wobei z1 der Wortteil bis zum Kreis, z3 der Wortteil nach dem Kreis ist, dann sind alle Wörter z1 z2^n z3 (n = 1, 2, ..., oo) in der regulären Sprache.
-
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).
-
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?
