Welche Stelle darf ich zum Aufpumpen des Pumping Lemma verwenden?
Laut Lösungen sei diese Sprache aufpumpbar mit dem Pumping Lemma.
Wenn ich z. B. das Wort
(1^k)1(1^n)0(1^n)(1^j) habe
und ich zerlege das Wort in uvw
wobei v>=1 und uv<n
nun sage ich mein v sei das erste 1^n, was da abgebildet ist, ich kann doch das wegen dem 1^n kommt, nicht beliebig aufpumpen, also wäre es zumindest laut pumping lemma nicht regulär oder?
Aber laut unseren Lösungen sei das Wort aufpumpbar.
Warum?
Darf v, bei der Wortzerlegung uvw auch= 1^k sein, dann wäre es ja aufpumpbar, aber wenn ja, warum darf ich einfach aussuchen, dass mein v= 1^k ist und dass es nicht v=1^n sein müsste?
1 Antwort
Um zu zeigen, dass die Sprache die Pumping-Eigenschaft erfüllt, musst du eine konkrete Pumping-Lemma-Zahl n > 0 angeben. Außerdem brauchst du eine immer funktionierende Strategie, wie du ein beliebiges Wort zerlegen kannst, sodass die bekannten Eigenschaften erfüllt sind.
Ich formuliere das hier mal etwas informell. Sagen wir mal, n = 5 sei eine Pumping-Lemma-Zahl. Da i > 0 sein muss, fängt jedes Wort mit mindestens zwei Einsen an. Wir unterscheiden zwei Fälle:
- Das Wort fängt mit mehr als zwei Einsen an: Wir zerlegen das Wort so, dass u leer ist, v die erste Eins umfasst und w den Rest. Dann können wir pumpen, denn i sei immer 1, heißt alle Worte müssen mit k Einsen beginnen, dann folgt 1101 und abschließend j Einsen, wobei k und j beliebig sind. Wir rühren die 1101 und alles danach nicht an, sondern nur die führenden Einsen, was beliebig viele sein dürfen, sodass Pumpen hier keine Probleme verursacht.
- Das Wort fängt mit genau zwei Einsen an, also mit 1101 gefolgt von j Einsen. Da n = 5 ist, muss das Wort mindestens Länge 5 haben, also muss j > 0 sein. Wir zerlegen das Wort so, dass u = 1101, v die erste Eins danach und w der Rest (ggf. leer) ist. Dann können wir pumpen, denn hier sei i immer 1, k immer 0 und j beliebig. Wir rühren die 1101 auch hier nicht an und somit ist es egal, wie viele abschließende Einsen wir erzeugen.
In beiden möglichen Fällen gibt es also eine Strategie für die Zerlegung eines beliebigen Wortes, also ist die Eigenschaft des Pumping-Lemmas erfüllt. Dies bedeutet jedoch nicht unbedingt, dass die Sprache regulär ist, weil es sich lediglich um eine notwendige, jedoch nicht um eine hinreichende Bedingung handelt.
----------
Zurück zu deinem Beispiel (1^k)1(1^n)0(1^n)(1^j). Das ist jetzt kein präzises Beispiel. Vielmehr könnte man sich konkrete Wörter anschauen. 1111011 könnte man nach der obigen Strategie zerlegen in u = leer, v = 1 und w = 111011. Dann wäre uw = 111011 in der Sprache (z. B. mit i = 2, j = 0, k = 0), ebenso uvvw = 11111011 (z. B. mit i = 2, j = 0, k = 2).
Das Wort 11011 könnte man in u = 1101, v = 1, w = leer zerlegen. Hier wäre uw = 1101 in der Sprache (z. B. mit i = 1, j = 0, k = 0), ebenso uvvw = 110111 (z. B. mit i = 1, j = 2, k = 0).
Ich denke, es wird auch deutlich, dass die Sprache identisch zu folgender Sprache ist:
Du kannst also vorne mit irgendeiner Eins pumpen, solange du die 1101 in Ruhe lässt. Wenn es davor keine Eins gibt, pumpst du entsprechend mit der ersten Eins nach 1101.
VIELEN DANK HAST MIR MEGA GEHOLFEN!