Pumping Lemma reguläre Sprache?
ich soll mit Pumping-Lemma beweisen, dass die folgende Sprache nicht regulär ist: L={0^m1^n|n!=m}
ist mein ansatz richtig so? :
sei n element N,
sei k >= 1 und setze w = 0^n1^(n-k) mit w element L und |w|>=n,
zerlegung w = xyz mit |xy|<=n und y nicht leer,
dann xy= 0^p mit p<=n, y=0^k mit k>=1,
setze i=0 --> xy^0z=0^(n-k)1^(n-k)
somit ist xy^0z nicht in L und L nicht regulär
1 Antwort
Du hast für eine bestimmte Zerlegung bewiesen, dass es nicht klappt. Du musst es aber für JEDE passende Zerlegung zeigen.
Das Gegenbeispiel, welches du für den Beweis nutzen musst, muss etwas komplezierter aussehen.
Tipp: das Wort, welches die Konstante k widerlegen soll, muss die Form 0^k 1^m haben, wobei du m so wählen musst, dass jede Zerlegung von 0^k so gepumpt werden kann, dass du dann m Nullen hast.
Nein. Du musst zuerst m passend wählen. Und das i hängt dann von der Zerlegung ab.
Was ist jetzt bei dir die Pumping konstante die du widerlegen willst?
m=0 kann nicht sein, weil du dann immer eine Zerlegung finden kannst, die du pumpen kannst.
danke aber hab es aber leider immer noch nicht verstanden... soll i=m/k ? aber dann wär i nicht mehr natürlich