Hilfe zur Kontraproduktion mit dem Pumping Lemma |
| 07.12.2016, 01:56 | Auf diesen Beitrag antworten » |
| 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 |
|
|
|
|
|
