Informatiker Board | Theoretische Informatik | Beweis mit Pumping-Lemma

Registrierung

Kalender

Mitgliederliste

Teammitglieder

Suche

Häufig gestellte Fragen

Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » Beweis mit Pumping-Lemma

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Neues Thema erstellen

Antwort erstellen

Zum Ende der Seite springen

Beweis mit Pumping-Lemma

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

AD
unregistriert

Beweis mit Pumping-Lemma

Auf diesen Beitrag antworten

Zitatantwort auf diesen Beitrag erstellen

Diesen Beitrag editieren/löschen

Diesen Beitrag einem Moderator melden

Zum Anfang der Seite springen

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?

02.06.2014 08:41

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

RE: Beweis mit Pumping-Lemma

Auf diesen Beitrag antworten

Zitatantwort auf diesen Beitrag erstellen

Diesen Beitrag editieren/löschen

Diesen Beitrag einem Moderator melden

Zum Anfang der Seite springen

Wir nehmen an dass die Sprache [latex]L[/latex]

[latex]L[/latex]

regulär ist.

[latex]p[/latex]

[latex]p[/latex]

ist die Pumping-Länge.

Wir wählen das Wort [latex]x=a^n[/latex]

[latex]x=a^n[/latex]

,

[latex]n[/latex]

ist eine Primzahl.

Man kann das [latex]x[/latex]

[latex]x[/latex]

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

[latex]x=uvw[/latex]

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

Das heisst dass wenn man [latex]i|uw|[/latex]

[latex]i|uw|[/latex]

an der Länge des [latex]x[/latex]

[latex]x[/latex]

dazu addiert, muss es immer noch in [latex]L[/latex]

[latex]L[/latex]

sein.

Also [latex]p+i|uw|[/latex]

[latex]p+i|uw|[/latex]

muss eine Primzahl sein $[latex]\forall i \geq 0[/latex]$ .

Für [latex]i=p[/latex]

[latex]i=p[/latex]

haben wir

[latex]p+p|uw|=p(1+|uw|)[/latex]

[latex]p[/latex]

ist eine Primzahl [latex]>1[/latex]

[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]

[latex]L[/latex]

nicht regulär.

Dieser Beitrag wurde 5 mal editiert, zum letzten Mal von marie m: 08.06.2014 03:00.

08.06.2014 02:57

marie m ist offline

Beiträge von marie m suchen

Nehmen Sie marie m in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Neues Thema erstellen

Antwort erstellen

Informatiker Board » Themengebiete » Theoretische Informatik » Beweis mit Pumping-Lemma

© by Informatikerboard.de
Forensoftware: Burning Board, entwickelt von WoltLab GmbH