Pumping Lemma Primzahl < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:49 So 05.08.2007 | | Autor: | Wiwie |
| Aufgabe | | Beweisen Sie mit Hilfe des Pumping-Lemmas für reguläre Sprachen, dass die Sprache L = [mm] \{a^n| n Primzahl\} [/mm] nicht regulär ist. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Der Lösungsweg meines Profs erscheint mir ziemlich kompliziert, für eine eigentlich recht simple Aufgabenstellung. Ich habe versucht, meiner eigenen Idee nachzugehen. Ist folgender Beweis korrekt?
[mm] n_{0} [/mm] sei die zu wählende Konstante und eine Primzahl, sodass für alle Wörter z [mm] \in [/mm] L mit |z| [mm] \ge n_{0} [/mm] die drei Bedingungen gelten.
Man setze das Wort z auf [mm] a^{n_{0}}.
[/mm]
Bed |uv| [mm] \le n_{0} [/mm] ist erfüllt.
Man kann nun z schreiben als:
z = uvw = [mm] a^{n_{0}} [/mm] = [mm] a^{|u|} a^{|v|} a^{|w|}
[/mm]
Laut Pumping Lemma muss dann jedes Wort [mm] z_{i} [/mm] auch wieder [mm] \in [/mm] L sein.
[mm] z_{i} [/mm] = [mm] a^{|u|} a^{i * |v|} a^{|w|}
[/mm]
= [mm] a^{|uw|} a^{i * |v|}
[/mm]
Da [mm] n_{0} [/mm] Primzahl, folgt, dass |uvw| ungerade.
1. Fall: |uw| gerade
Man wähle i ebenfalls |uw|, dann erhält man mit |uw| * |v| einen geraden mittleren Exponenten, sodass die Summe der Exponenten gerade ist. Dieser ist dann folglich keine Primzahl also gilt [mm] z_{i} \not\in [/mm] L und L ist nicht regulär.
2.Fall: |uw| ungerade
Es folgt, dass |v| gerade, also wähle man i = |v|+1, sodass der Exponent auch hier gerade wird. Es folgt selbiges wie oben.
Vielen Dank,
Gruß
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:04 Mo 06.08.2007 | | Autor: | Gilga |
> Da [mm]n_{0}[/mm] Primzahl, folgt, dass |uvw| ungerade.
2 ist auch eine Primzahl!
Mein Beweis: Es müsste nach Pumping gelten: 1 <= |v| <= |uvw|
mit |uw|+i*|v| Primzahl und i natürliche Zahl
setze i=|uw|
=>|uw|+|uw|*|v|=|uw|(1+|v|) Primzahl => keine schöne "Primzahl" :D
Das ist doch elegant. Ich hoffe es stimmt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:45 Mo 06.08.2007 | | Autor: | Wiwie |
Hallo,
Gilga hat natürlich recht. Ich hatte inzwischen noch andere Meinungen bzgl. des Problems eingeholt und außer der Tatsache, dass
1) Nicht alle Primzahlen ungerade sind
gilt außerdem, dass
2) mein zweiter Fall nicht korrekt ist, denn für i = |v|+1 gilt:
[mm] a^{n_{0}} [/mm] = [mm] a^{|uw|} a^{(|v|+1) |v|}
[/mm]
= [mm] a^{|uw|} a^{|v|^{2}+|v|}. [/mm] Dieser Exponent ist nicht ungerade, da sowohl [mm] |v|^{2} [/mm] als auch |v| gerade ist.
@Gilga
Dein Lösungsweg ist so ähnlich wie der meines Professors, er wählte auch i = |uw| und erhält dann irgendwann durch geschicktes Umformen und Anwenden der PL-Bedingungen zwei Schranken für den Exponenten, die genau den Bereich zwischen zwei Primzahlen angeben.
An deinem Lösungsweg fehlt mir allerdings noch ein wenig die Begründung, warum du aus i = |uw| direkt folgern kannst, dass keine Primzahl heraus kommt...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:21 Mo 06.08.2007 | | Autor: | Gilga |
|uw|(1+|v|) muss nach PL in der Sprache enthalten sein => Primzahl
|uw|(1+|v|) ist das Produkt von 2 Zahlen => also keine Primzahl
Wenn dann Prof. da erst schranken ableiten muss ist meine Lösung ja viel geschickter. Mir scheint sie aber richtig.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:59 Mo 06.08.2007 | | Autor: | Wiwie |
@Gilga
Meine Lösung |v| * (1 + |v|) ist ebenfalls ein Produkt zweier Zahlen, ohne dass es funktioniert.
Wenn bei deiner Lösung zufällig |uw| ungerade ist, funktioniert es, aber es kann auch genauso gut passieren, dass dies nicht der Fall ist, sodass eine gerade Zahl herauskommt, denn:
|uw| * (1 + |v|) = |uw| + |uw| * |v| ist genau dann ungerade, wenn |uw| ungerade ist (unabhängig vom Produkt).
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:29 Mo 06.08.2007 | | Autor: | Gilga |
Versteh jetzt nicht auf was du hinaus willst.
Um zu zeigen, dass es keine Primzahl ist muss ich nur einen Teiler ungleich 1 und der Primzahl selbst finden. Ist ja nicht zwingend nötig, dass die Zahl gerade ist
|
|
|
| |
|
Hallo,
> Mein Beweis: Es müsste nach Pumping gelten: 1 <= |v| <=
> |uvw|
> mit |uw|+i*|v| Primzahl und i natürliche Zahl
> setze i=|uw|
> =>|uw|+|uw|*|v|=|uw|(1+|v|) Primzahl => keine schöne
> "Primzahl" :D
formal gesehen ist das etwas dürftig.
Eigentlich sagt das Pumping Lemma ja folgendes aus: Falls $L$ eine reguläre Menge ist, dann existiert ein $n>0$, so dass sich alle Wörter [mm] $x\in [/mm] L$ mit [mm] $|x|\ge [/mm] n$ in $x=uvw$ zerlegen lassen, so dass [mm] $|v|\ge [/mm] 1$, [mm] $|uv|\le [/mm] n$ und [mm] $\forall i>0:uv^i w\in [/mm] L$.
Um jetzt zu zeigen, dass [mm] $L=\{a^i|i\text{ is prim}\}$ [/mm] keine reguläre Sprache ist, reicht es zu zeigen, dass obige Behauptung nicht gilt. Das bedeutet, dass [mm] $\forall n>0:\ldots$.
[/mm]
Also ohne Lücken, wäre es so in der Art: Wähle $n>0$ beliebig. Sei nun [mm] $n'\ge [/mm] n$ eine Primzahl. Sei [mm] $x=a^{n'}$ [/mm] (offensichtlich [mm] $x\in [/mm] L$). Wähle [mm] $uv=a^{n''}$ [/mm] mit [mm] $|v|\ge [/mm] 1$ und [mm] $n''\le [/mm] n$ beliebig. Sei nun $i=|uw|$, dann gilt [mm] $|uv^i w|=|u|+|v|\cdot|uw|+|w|=|uw|\cdot(1+|v|)$. [/mm] Da [mm] $uv^i w\in [/mm] L$, so muss [mm] $|uw|\cdots(1+|v|)$ [/mm] prim sein. Das ist aber natürlich nicht der Fall 
Sind wir fertig? Nein! Hier haben wir jetzt aber einen Spezialfall übersehen!
Was ist wenn [mm] $|uw|\le [/mm] 1$? Im Fall von $|uw|=0$ ist es recht einfach, da [mm] $|v^i|=|v|\cdot [/mm] i$ und [mm] $v^i$ [/mm] ist damit für ein beliebiges [mm] $i>0,i\ne [/mm] n$ natürlich auch kein Element aus $L$. Falls $|uw|=1$, dann wäre die Länge $1+|v|$ und das ist zumindestens ersteinmal nicht offentlich keine Primzahl. Also müssen wir das anders lösen. Dann wählen wir aber einfach eine Zahl $i$ so, dass [mm] $|uv^i w|=|uw|+|v|\cdot i=1+|v|\cdot [/mm] i$ keine Primzahl ist. Wir wissen, dass $1+|v|=n'$ eine Primzahl ist. Machen wir das ganze mal einfach: Nehmen wir an, dass $n'=2$, dann ist $|v|=1$, damit gilt für $i=3$ offensichtlich, dass [mm] $uv^3 w\not\in [/mm] L$, da [mm] $1+|v|\cdot 3=|uv^3 [/mm] w|=4$ keine Primzahl ist. Ist nun $n'>2$, dann ist $n'$ ungerade (ansonsten wäre es ja keine Primzahl). Das macht das ganze aber unanständig, da [mm] $1+|v|^i$ [/mm] immer ungerade sein wird. Das bedeutet, wir benötigen ein weiteres Argument, warum es ein $i$ gibt, so dass es gerade keine Primzahl ist. Das schaffen wir allerdings, indem wir uns eine Zahl größer $1+|v|$ suchen, deren "Lücke" zur nächsten Primzahl größer als $|v|$ ist (d.h. es folgen $|v|$ Zahlen, die keine Primzahl sind). Da wir unsere Zahl immer in Schritten von $|v|$ erhöhen, landen wir irgendwann genau in dieser Lücke. Wir müssen nurnoch eine solche Zahl finden. Dies schaffen wir über einen einfachen Trick. Wir wählen ein $k$, so dass das $l:=k!>1+|v|$ und $k>|v|$. Damit sind die Zahlen $l+2$ bis $l+k$ keine Primzahlen (kann man sich einfach klarmachen, da für alle [mm] $2\le j\le [/mm] k$ $l$ durch $j$ teilbar ist und auch $l+j$ durch $j$ teilbar ist und damit beide keine Primzahlen sind). Die sind allerdings genau [mm] $k-1\ge [/mm] |v|$ Zahlen und [mm] $1+|v|\cdot [/mm] i$ muss für ein $i$ genau in diesem Intervall liegen.
So es wurde also doch ein wenig länger, wenn man sich das ganze genau anschaut. Und das obwohl ich den gleichen eleganten Anzatz gewählt habe, wollte es nur exakt machen ... Niemals "Spezialfälle" übersehen. Der Lückenanzahl sollte auch direktwählbar sein, so dass man keine Spezialfälle hat ...
Gruß
Matthias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:13 Mo 06.08.2007 | | Autor: | Karl_Pech |
Hallo Wiwie,
Also was dein Problem angeht, so könntest du dir auch ![[]](/images/popup.gif) folgende Diskussion dazu anschauen. Vielleicht hilft es ja weiter.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:24 Mo 06.08.2007 | | Autor: | Gilga |
"Da steht, dass u [mm] v^k [/mm] w für alle k Element der Sprache ist. Findest du
nur ein k (Das darf durchaus konkret sein), so dass die Länge des Wortes
x keine Primzahl ist, dann bist du durch"
Auf diese Aussage aus der diskussion wollte ich hinaus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:04 Mo 06.08.2007 | | Autor: | Wiwie |
Jep, so ist es ja auch, aber es ist eben nicht so einfach möglich, eine solche Zahl zu finden, die keine Primzahl ist.
|
|
|
|
