Einfache Pumping-Eigenschaft
-
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.
-
Danke, ich werd die Seiten mal durcharbeiten...
-
Was ich auch immer noch nicht so wirklich verstanden habe, ist, warum es heißen muss:
|uv|≤n, |v|≥1
Könnt ihr mir das erklären? Was ist eigentlich die Variable "n"? Ist das eigentlich die Anzahl der Zustände die der Automat hat?
-
Wenn die Sprache regulär wäre, könntest du ein n finden, so daß du alle längeren Wörter pumpen kannst (die Größe eines Automaten für die Sprache). Also suchen wir uns ein beliebiges n und beweisen, daß wir keinen Automaten mit n Zuständen für die Sprache bauen können.
-
Ich wähle ein Wort z aus $$ L={wcw^{rev} | w \in { a,b }^\star }$$
z = a^n c a^n
Was ich nun bei der Zerlegung nicht verstehe ist, warum für v folgendes gilt:
v = a^l
das Teilwort v ist doch im gewählten Wort z eigentlich c, oder?
-
Nein. Das liegt zum einen an der Wahl von z (beliebter Trick beim Pumping-Lemma: Mach z "gross genug", dass der Rest funktioniert), zum anderen an der Einschränkung |uv| <= n im Pumping-Lemma. Wenn also für u und v zusammen nur die ersten n Zeichen von z zur Verfügung stehen, können beide für z = a^n c a^n nur aus a's bestehen.
Edit: Was heisst eigentlich z = a^n c a^n?
Das heisst: z besteht zuerst aus n a's, dann genau ein c, dann wieder n a's. Das heisst aber NICHT, dass a^n, c und a^n die einzig mögliche Unterteilung des Wortes ist!
-
Nein, die Zerlegung des gewählten Wortes hat nichts mit der Sprachstruktur zu tun. Du mußt dir nur zwei Punkte aussuchen, an denen du das Wort auseinanderschneidest.
-
Kannst du genauer erklären was du mit "Mach z "gross genug", dass der Rest funktioniert)" meinst?
-
Du mußt dir nur zwei Punkte aussuchen, an denen du das Wort auseinanderschneidest.
Gut, mit der Wortstruktur von z hat das also anscheinend nix zu tun.
Leichter gesagt als getan. Woher weiß ich denn welche die richtigen Punkte sind? Außerdem hat ja das Beispiel aus dem Link nur einen Punkt hergenommen, nämlich immer nur das a des Wortes...
-
vip@r schrieb:
Kannst du genauer erklären was du mit "Mach z "gross genug", dass der Rest funktioniert)" meinst?
Naja, man könnte statt z = a^n c a^n eventuell auch z = a^{n/2} c a^{n/2} (jeweils aufgerundet} betrachten. Das macht aber den Rest des Beweises deutlich komplizierter - eben weil man dann die Fallunterscheidung machen muss, ob das c im v enthalten ist oder nicht.
-
Geht dann z = a^n c^n a auch?
-
Nein, das ist ja (für n!=1) nicht in der betrachteten Sprache.