Beweis mit Pumping-Lemma

02.06.2014, 08:41	Auf diesen Beitrag antworten »
AD	Beweis mit Pumping-Lemma Meine Frage: Hallo, ich möchte zeigen, dass die Sprache L={a^n\|n Primzahl} nicht regulär ist. Meine Ideen: Ich hab das Pumping-Lemma benutzt: Sei also x=a^n in L. Dann wähle ich u=a^k, v=a, w=a^(n-k-1); offenbar ist uvw in L, aber u(v^0)w liegt nicht in L. Kann ich das so machen?


08.06.2014, 02:57	Auf diesen Beitrag antworten »
marie m	RE: Beweis mit Pumping-Lemma Wir nehmen an dass die Sprache regulär ist. ist die Pumping-Länge. Wir wählen das Wort , ist eine Primzahl. Man kann das in drei Teilworte zerteilen, $[latex]uv^iw \in L, \forall i \geq 0[/latex]$ Das heisst dass wenn man an der Länge des dazu addiert, muss es immer noch in sein. Also muss eine Primzahl sein $[latex]\forall i \geq 0[/latex]$ . Für haben wir ist eine Primzahl und , also ist keine Primzahl da es ein Produkt von zwei Zahlen, die größer als 1 sind, ist. Also kann unsere Vermutung nicht stimmen. Also ist nicht regulär.

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »