Die letzten 2 Beiträge |
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]](http://www.matheboard.de/latex2png/latex2png.php?uv^iw \in L, \forall i \geq 0)
Das heisst dass wenn man an der Länge des dazu addiert, muss es immer noch in sein.
Also muss eine Primzahl sein .
Für haben wir ![[latex]p+p|uw|=p(1+|uw|)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?p+p|uw|=p(1+|uw|))
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. |
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? |
|
|