| mathishard |
Hilfe zur Kontraproduktion mit dem Pumping Lemma
Im Dateianhang befindet sich die Aufgabenstellung und zwar sollen wir das Pumping Lemma verwenden um mit Hilfe der Kontraproduktion ein Widerspruch zu ermitteln, so dass die Sprache nicht regulär ist.
Ich habe folgende Überlegung angestellt und würde mich freuen, wenn sich einer das angucken würde:
Unter der Voraussetzung, dass L regulär ist:
Mit dem Pumping Lemma muss es die Pumpenlänge p geben.
Also (a^p)*(b^p+1) ∈ L
-> a^p*b^p+1 = xyz mit |xy| < p und |y|>0
-> xy = a^q für 0<q<p also besteht xy nur aus a
-> y = a^r für 1<r<q
-> xy^2z = a^p+rb^p+1 ∈ L, was aber zu einem Widerspruch zu unser Sprache führt, weil p+r > p+1
mathishard hat dieses Bild (verkleinerte Version) angehängt:
|
