0 Daumen
662 Aufrufe

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.

Avatar von

1 Antwort

0 Daumen
w = ap+1bp cp+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.

Avatar von 5,6 k

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 = ap+1bpcp 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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community