Mit Pumping Lemma beweisen, dass Primzahl nicht regulär ist.

Question

Aufgabe:

Ich möchte mit Pumping Lemma beweisen, dass L nicht regulär ist.

L = { 1 ⁿ | n = Primzahl }

Problem/Ansatz:

x = 1 ^r

y = 1 ^s  s ≥ 1

z = 1 ^{p - r - s}

xy ⁱ z = 1 ^r 1 ^is 1 ^{p - r- s}

= 1 ^{p + is - s}

und jetzt muss man zeigen, dass p + is - s keine Primzahl ist.

i = 2 und s ≥ 1

p + 2s - s = p

2*1 -1 = 0

und das stimmt nicht.

Kann man es so zeigen? Oder was müsste ich anders machen?

Ich habe online immer nur andere Lösungen gefunden, aber ich wollte es auf meine Art lösen.

Answer 1

xyⁱz = 1^r1^is1^p-r-s = 1^p+is-s

Bis dahin sieht's gut aus.

p + 2s - s = p

Das stimmt nicht. Es ist p + 2s - s = p + s.

und jetzt muss man zeigen, dass p + is - s keine Primzahl ist.

Nein.

Du musst zeigen, dass es ein i gibt, so dass p + is - s keine Primzahl ist.

Tipp. Wähle i so, dass p + is - s durch p teilbar ist, aber größer als p ist.

Comments

Danke für die Antwort.

Ich hätte aber nochmal eine Frage: Wieso muss man p + 2s - s = p + s verwenden?
Was schreibt man immer auf die rechte Seite? Schreibt man da nicht einen Wert hin, der in der Sprache liegt? Und dann sucht man ein i, welches zeigt, dass es nicht mehr in der Sprache liegt?

Falls das der Fall ist, wieso muss man dann nicht nur p benutzen?

---

Wieso muss man p + 2s - s = p + s verwenden

Ich habe nicht gesagt, dass man

        p + 2s - s = p + s

verwenden muss. Ich habe gesagt, dass die Terme p + 2s - s und p + s gleichwertig sind.

Was schreibt man immer auf die rechte Seite?

Was ist denn der Zweck gewesen, die linke Seite hinzuschreiben? Formuliere Beweis in vollständigen Sätzen der deutschen Sprache.

Und dann sucht man ein i, welches zeigt, dass es nicht mehr in der Sprache liegt?

Verwende weniger Pronomen.

---

Was ist denn der Zweck gewesen, die linke Seite hinzuschreiben?

Ich wollte zeigen, welchen Wert i einnehmen muss, damit die Aussage stimmt. p+is-s = p

p+is-s = p

= is - s = 0

= s(i-1) = 0

i = 1

Daraus würde ich dann schließen, dass ich für i einen anderen Wert als 1 nehmen müsste.

Nochmal zu dem Tipp zurück:

Wähle i so, dass p + is - s durch p teilbar ist, aber größer als p ist.

Dann könnte man p + 1 für i nehmen.

p + (p+1)s - s

= p + ps +s -s

= p + ps
Und das Widerspricht den Eigenschaften von Primzahlen.

Kann ich es mit meinem vorherigen Ansatz auch beweisen?

---

Ich wollte zeigen, welchen Wert i einnehmen muss, damit die Aussage stimmt. p+is-s = p

Aus der Tatsache, dass die Aussage

        p+is-s = p

stimmt oder nicht stimmt lässt sich nichts pber die Regularität von L schulssfolgern.

Dann könnte man p + 1 für i nehmen.
p + (p+1)s - s
= p + ps +s -s
= p + ps

Zusammengefasst: Wenn \(L\) regulär ist und \(1^p\in L\) ist, dann ist \(1^{p + ps}\in L\). Es ist aber \(1^{p + ps}\notin L\) weil \(p+ps\) keine Primzahl ist.

---

Danke, ich glaube es jetzt verstanden zu haben.