3. Einfache Pumping-Eigenschaft

Einfache Pumping-Eigenschaft

  • V

    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?

    0
  • S

    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!

    0
  • C

    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.

    0
  • V

    Kannst du genauer erklären was du mit "Mach z "gross genug", dass der Rest funktioniert)" meinst?

    0
  • V

    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...

    0
  • S

    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.

    0
  • V

    Geht dann z = a^n c^n a auch?

    0
  • S

    Nein, das ist ja (für n!=1) nicht in der betrachteten Sprache.

    0
  • V

    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?

    0
  • C

    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)

    0
  • C

    Mist, ich bin wohl zu langsam *grml*

    vip@r schrieb:

    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?

    Du hast doch deine Sprach-Definition gegeben, da findet man normalerweise recht schnell ein passendes Wort, das lang genug ist für das Pumping-Lemma.

    0
  • V

    In der Sprachdefinition steht, dass das Teilwort w aus {a,b}^* sein soll. Was ist dann das c? c hat ja in der Sprachdefinition anscheinend keine Einschränkende Eigenschaften, oder wie? Gehe ich richtig in der Annahme, dass das ^rev "reverse" bedeutet? Was hat das dann für eine Auswirkung?

    0
  • S

    vip@r schrieb:

    In der Sprachdefinition steht, dass das Teilwort w aus {a,b}^* sein soll. Was ist dann das c?

    Ein weiteres Zeichen.

    Gehe ich richtig in der Annahme, dass das ^rev "reverse" bedeutet? Was hat das dann für eine Auswirkung?

    Ja, genau. Das heisst, die Sprache besteht aus allen Palindromen (aus a's und b's), die "in der Mitte" ein einzelnes c haben.

    0
  • V

    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^n

    und 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...

    0
  • C

    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)

    0
  • S

    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^n

    und 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.

    0
  • V

    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?

    0
  • V

    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?

    0
  • ?

    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. ⚠

    0
  • S

    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.

    0
Anmelden zum Antworten