Einfache Pumping-Eigenschaft
-
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.
-
Genau da liegt ein weiteres Problem bei mir. Wie erkennst du nun, dass das nicht mehr in der Sprache liegt? Anders herum gefragt: Wie kommt man daraufn ein Wort zu konstruieren, welches in der Sprache liegt?
-
vip@r schrieb:
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...
Prinzipiell scheitert das Pumpen bei jeder Zerlegung des Wortes, das heißt du müsstest alle Zerlegungen betrachten (für deine Sprache: v liegt komplett im vorderen a-Block, v liegt komplett im hinteren a-Block oder v enthält das c). Der Trick ist die Einschränkung |uv|<=n, dadurch ist hier nur der erste Fall möglich.
(wir sind davon ausgegangen, daß wir einen Automaten mit n Zuständen für die Sprache haben, also wäre nach spätestens n Zeichen ein Zustand mehrfach erreicht - der Weg dazwischen entspricht dann dem Wortteil v)