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, 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 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. |
|