Finde ein Wort für das Pumping Lemma

Question

Ich sitze gerade vor einer Sprache:

L(A)={a^n b^m c^k | n,m,k aus N und n mod 2=0=m mod 2 und m<k}

Nun möchte ich ein Wort finden sodass ich das Pumping Lenma anwenden kann ohne eine Fallunterscheindung durchführen zu müssen.

Ich habe erst an das Wort w=c^n gedacht.

Das Problem hier ist, dass es die Bedingung immer erfüllt egal wie ich aufpumpe.

Hat Jemand eine Idee?

Ich Frage mich gerade was man nun zeigen muss, damit es scheitert? Bzw. was soll eigentlich scheitern: n+m>=z? Wie kommt man darauf?

Answer 1

n mod 2=0=m mod 2

Das ist kein Problem für Automaten.

m<k

Das ist ein Problem für Automaten.

Nun möchte ich ein Wort finden

Zuerste legt man die Pumping-Zahl fest. Sei diese z.

Erst dann ist es sinnvoll, sich auf die Suche nach einem Wort zu begeben.

Sei w = b^mc^k ∈ L(A) mit m ≥ z.

Comments

Hallo Oswald

Du schreibst das man die Pumping-Zahl festlegen soll, aber ist diese nicht immer vorgegeben mit |w|>z?

Ich dachte man müsste mit Hilfe des Aufpumpen zeigen, dass die Bedingung von A nicht mehr gilt, in dem Fall das m!<k ist?

Ich glaube ich habe das Lemma überhaupt nicht verstanden, es ist aber auch schwierig.

Also wir haben diese Definition gelernt, vlt scheitere ich ja dort:
Für alle n ∈ N gibt es ein Wort w der Sprache mit |w| > n, so dass es für alle Zerlegungen
w = xyz mit y != λ und |xy| <= n ein k ∈ N gibt, so dass xy^kz nicht in der Sprache liegt.

Was ist dort die Sache die ich wiederlegen muss?
Muss ich wiederlegen, dass das Wort nicht mehr den Bedingungen der Sprach entspricht oder muss ich zeigen, dass das Eigenschaften des Lemmas nicht mehr zutreffen

---

Für alle n ∈ N gibt es ein Wort w der Sprache mit |w| > n, so dass es für alle Zerlegungen w = xyz mit y != λ und |xy| <= n ein k ∈ N gibt, so dass xy^kz nicht in der Sprache liegt.

Wenn das erfüllt ist, dann ist die Sprache nicht regulär. Du musst also zeigen, dass L(A) diese Eigenschaft erfüllt.

ist diese nicht immer vorgegeben mit |w|>z

Nein. Eine Egenschaft von w ist durch z vorgegeben, nämlich dass |w|>z ist.

---

Also muss ich nichts wiederlegen, sondern nur zeigen, dass die Eigenschaften gelten.

Ich dachte bisher immer, man müsste schlussendlich das k so wählen, dass w nicht mehr in der Sprache liegt, nur wie sehe ich sowas?

An |W|<z? Dann wäre die Frage, wie an z immer wählen soll.

---

Vlt sollte ich mich etwas klarer Ausdrücken, bzw klarere Fragen stellen.

Also mein Problem ist, dass ich nicht weiß was ich zeigen soll und wie ich ein Wort zu wählen habe.

Ich dachte bisher immer, dass ich eine Sprache wählen muss, die durch das Aufpummpen nicht mehr in der Sprache liegt. Und das sie nicht mehr in der Sprache liegt, sehe ich an den Eigenschaften der Sprache selbst.

z.B man hat die Sprache a^n b^m mit n,m aus N und n<m.

Dann würde ich zeigen wollen, dass ich das a^n so verändern kann, dass n<m nicht mehr gilt. scheint aber falsch zu sein. 
Nun sagst du ich soll die Pump Zahl wählen, nur wie?

---

Aussage des Pumping-Lemma	Verwendung im Beweis
Für alle n ∈ N	Sei n∈ℕ.
gibt es ein Wort w der Sprache mit |w| > n,	Sei w = bmcp ∈ L(A) mit m > n.
so dass es für alle Zerlegungen w = xyz mit y != λ und |xy| <= n	Wegen m > n hat jede solche Zerlegung die Form x=bm1, y = bm2, z=bm3cp.
ein k ∈ N gibt,	Sei k = p.
so dass xykz nicht in der Sprache liegt.	Wegen m1 + m2·p + m3 ≥ p ist xykz ∉ L(A).