Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Beweis mit Pumping-Lemma (http://www.informatikerboard.de/board/thread.php?threadid=1861)
Geschrieben von AD am 02.06.2014 um 08:41:
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?
Geschrieben von marie m am 08.06.2014 um 02:57:
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.
Forensoftware: Burning Board, entwickelt von WoltLab GmbH