spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Behauptung: §L=\{\mathbf{a}^n|n\text{ ist nicht prim}\}§ ist nicht regulär.
Annahme: §L§ ist regulär.
Beweis durch Widerspruch.

Gemäß des Pumping-Lemma muss die Darstellung §uv^iw\in L§ mit §i\in\mathbb{N}\cup\{0\}§ gelten, wobei §v§ nicht leer ist.

Betrachten wir nun das Wort §\mathbf{w}=uv^6w=\mathbf{aaaaaaaa}=\mathbf{a}^8 \in L§. Betrachten wir nun das Wort §\mathbf{w}=uv^7w=\mathbf{aaaaaaaaa}=\mathbf{a}^9 \in L§.
Durch das Pumping-Lemma müsste nun aber §\forall i\in\mathbb{N}:\mathbf{w}=uv^iw=\mathbf{aa}\cdots\mathbf \text{insgesamt }i+2\text{ mal}\cdots\mathbf{a}=\mathbf{a}^{i+2}\in L§ gelten, allerdings ist trivial bekannt, dass der Zusammenhang §\forall i\in\mathbb{N}\cup\{0\}:i+2\text{ ist nicht prim}§ nicht immer gilt. Das wohl einfachste Gegenbeispiel ergibt sich schon mit §i=0§: §\mathbf{w}=uv^0w=\mathbf{aa}=\mathbf{a}^2\not\in L§, da §2§ prim ist. §\Rightarrow L§ ist nicht regulär.

MfG
Check

EDIT: Voll verpeilt, dass da nicht prim stand, also erstmal schön umhereditiert...

Fehlt in dem Beweis nicht die Mindestlänge? Das pumping Lemma enthält doch noch die Bedingung das es erst ab einer bestimmten Länge n gelten muss.

Statt einem Gegenbeispiel wird man schon mit i und i+1 arbeiten müssen. Da die nicht Primzahlen unendlich sind, sollte das mit dem gleichen Ansatz aber auch gut klappen.

Allerdings fehlt die, jedoch habe ich sie weggelassen, weil sie für mein Vorgehen an sich ja nicht notwendig war. Inwieweit man das trotzdem noch angeben muss, weiß ich nicht, hab ja noch keine Uni-Erfahrung.

MfG
Check

Puh, ist schon etwas her. Pumping Lemma ist aber schon der richtige Ansatz.
Du kannst eine schöne Eigenschaft nutzen. Wenn §L§ eine reguläre Sprache ist, dann ist auch §\bar{L}§ regulär. Diese Eigenschaft kannst du nutzen. Versuch mal mit dem Pumping Lemma zu zeigen dass die Sprache §\bar{L}=\{\mathbf{a}^n|n\text{ ist prim}\}§ nicht regulär ist. Wenn du dir dazu erst mal Gedanken machst fällt es dir vielleicht leichter. Versuche das ganze doch mal als regulären Ausdruck darzustellen oder vielleicht als NFA/DFA. Dann ist es vielleicht etwas leichter falls dir das Pumping Lemma noch Probleme bereitet.

Eine kurze Suche nach "Primzahl reguläre Sprache" ergibt viele Themen in anderen Foren zur exakt selben Aufgabe.

Ich fand den Beweis für solche Aufgaben oftmals einfacher über den Satz von Myhill-Nerode [1] zu finden. Sehr zu empfehlen.

[1] https://de.wikipedia.org/wiki/Satz_von_Myhill-Nerode