Pumping-Lemma: Beweise, dass die Sprache nicht regulär ist

Question

Frage:

Die Aufgabe lautet zu beweisen, dass die Sprache L := { w {a,b,c}* | |w|a > |w|b oder |w|a > |w|} nicht regulär ist.

Ich habe als Wort w = a^(p+1)b^p c^(p+1) genommen, stimmt das so?

Dann müsste man ja theoretisch nur noch b aufpumpen, sodass dann auch |w|a <= |w|b gilt.

Answer 1

w = a^p+1b^p c^p+1

Ich vermute p soll die Pumping-Zahl sein.

Wäre L regulär, dann liese sich w so in drei Teile xyz teilen, dass

• |y| ≥ 1
• |xy| ≤ p
• ...

ist.

Dann müsste man ja theoretisch nur noch b aufpumpen

Wenn du w gemäß Pumping Lemma aufpumpst, dann bekommst du mehr a, wegen |xy| ≤ p.

Natürlich kannst du auch die b aufpumpen, darüber sagt dann aber das Pumping Lemma nichts aus.

Comments

Also dann könnte man w = a^(p+1) b^p c^p wählen.

p dann abpumpen, sodass w nicht mehr in der Sprache ist. Richtig?

---

Also dann könnte man w = a^p+1b^pc^p wählen.

Was ist denn dann das y, das |y| ≥ 1 erfüllt?

Wenn du das y gefunden hast, was ist dann das x, so dass |xy| ≤ p ist?

p dann abpumpen, sodass w nicht mehr in der Sprache ist.

Würde gehen.