Pumping Lemma für reguläre Sprachen?

1 Antwort

Der Beweis läuft darauf hinaus, dass es für jede Primzahl p und jede Konstante m <= p ein i gibt, sodass p+m*i keine Primzahl ist.

Versuche erst diese Aussage zu zeigen, und wende die dann bei der "Routine" an, die benutzt wird, um mit dem Pumpinglemma zu widerlegen, dass eine Sprache regulär ist (sprich: nimm an, dass k eine pumpingkonstante ist, finde dann ein Wort, das länger als k ist, sodass jede gültige Zerlegung nicht pumpbar ist).

Woher ich das weiß:Studium / Ausbildung – Mache derzeit meinen Mathematik Master