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...
Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von »Checkmateing« (29.04.2016, 02:17)