Pumping Lemma y^0?
Beim Pumping Lemma:
Das angeblich reguläre Wort wird in w = xyz zerlegt, dabei muss gemäß der ersten Bedingung |y| > 0 sein.
für alle i = 0,1,2... muss gelten W = xy^iz ist Element der Sprache L
y^i wird aufgepumpt.
Wenn man jetzt y^0 setzt, d. h. i = 0, kommt w = xz heraus. Klar soweit!
Allerdings, wenn y^0 = epsilon ist, das leere Wort,
dann wäre dies doch ein Widerspruch zur Bedingung |y| > 0 ???
2 Antworten
Allerdings, wenn y^0 = epsilon ist, das leere Wort,
dann wäre dies doch ein Widerspruch zur Bedingung |y| > 0 ???
Wieso das? Es wird ja nicht gefordert , dass |y^i| > 0 für alle i gilt, sondern dass |y| > 0 gilt. Somit ist hier kein Widerspruch.
Die kleinen Feinheiten machen es aus. Wenn man anfängt über die Dinge nachzudenken, dann kommen einem die Fragen erst.
:)
Anschaulich:
Du hast einen DEA, der die Sprache akzeptiert und damit auch dein Wort w=xyz, dann besagt das PL, dass ich y beliebig aufpumpen kann.
Irgendwo in der Mitte hast du einen Zustand qn, der einen Übergang zum Teilwort y hat und einen Übergang zu z. Wenn y akzeptiert wird, landen wir wieder in qn (also eine Schleife).
Dieser DEA akzeptiert das Wort xyz. Aber es akzeptiert auch xz. Das heißt aber nicht, dass man die "Schleife" im DEA weglassen darf, aber man kann sie überspringen (direkt zu z).
Alle Sprachen, die ein DEA akzeptiert sind auch regulär.
Edit: Oder kurzgefasst: Es muss etwas zum Aufpumpen dasein, aber ich kann auch die Luft rauslassen.
D. h. |y| ist |y^1| und dies muss > 0 sein. Richtig!