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 [latex]L[/latex] regulär ist.

[latex]p[/latex] ist die Pumping-Länge.

Wir wählen das Wort [latex]x=a^n[/latex], [latex]n[/latex] ist eine Primzahl.

Man kann das [latex]x[/latex] in drei Teilworte zerteilen, [latex]x=uvw[/latex]

[latex]uv^iw \in L, \forall i \geq 0[/latex]

Das heisst dass wenn man [latex]i|uw|[/latex] an der Länge des [latex]x[/latex] dazu addiert, muss es immer noch in [latex]L[/latex] sein.

Also [latex]p+i|uw|[/latex] muss eine Primzahl sein [latex]\forall i \geq 0[/latex].

Für [latex]i=p[/latex] haben wir [latex]p+p|uw|=p(1+|uw|)[/latex]

[latex]p[/latex] ist eine Primzahl [latex]>1[/latex] und [latex]|uw|>1[/latex], also [latex]p(1+|uw|)[/latex] 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 [latex]L[/latex] nicht regulär.


Forensoftware: Burning Board, entwickelt von WoltLab GmbH