kontextfrei&primzahlen < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:39 Fr 12.01.2007 | | Autor: | AriR |
| Aufgabe | | Zeigen Sie, dass die Sprache [mm] \{\*^p | p_ist_Primzahl\} [/mm] nicht kontextfrei ist. |
Hey leute,
hab leider keine ahnung wie ich diese aufgabe angehen soll.
kann mir da vielleihct einer einen tip geben?
Gruß Ari
|
|
| |
|
Hallo Ari, nimm halt zB das Pumping-Lemma für kontextfreie Sprachen her, nimm ein Element der Sprache, und bringe
die Anwendung des Pumping-Lemmas darauf zum Widerspruch mit der Definition der Sprache.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:56 Fr 12.01.2007 | | Autor: | AriR |
hi mathiash,
kann man das vielleicht so machen:
Sei n wie im Pumping Lemma. Sei [mm] w\in [/mm] L mit [mm] |w|\ge [/mm] n gegeben
[mm] \Rightarrow [/mm] Es gibt eine Zerlegung von w folgendermaßen: w=uvwxy mit [mm] |vx|\ge1 [/mm] und [mm] |vwx|\le [/mm] n und [mm] uv^iwx^iy\in [/mm] L für alle [mm] i\in\IN
[/mm]
[mm] \rightarrow [/mm] uv^iwx^iy im allgemeinen keine primzahl falls uvwxy primzahl ist.
Beispiel: Sei u=w=x=y=1 und v=2, dann ist [mm] uvwxy=\*^7 [/mm] primzahl
aber [mm] uv^2wx^2y=\*^8 [/mm] keine primzahl
ich hoffe das kommt hin :)
Gruß Ari
|
|
|
| |
|
Hallo Ari,
Du solltest halt zeigen, daß sowas auch existiert.
Wenn der String uvwxy mit [mm] |vwx|\leq [/mm] n Länge m hat und |vx|=l gilt, so hat ja der String
uv^iwx^iy die Länge [mm] m+i\cdot [/mm] l, und wir nehmen ja an, daß m prim ist und n die Zahl aus dem Puming-Lemma angewandt auf [mm] L=\{*^p|p\:\: prim\}.
[/mm]
W'ähle dann zB i=p, nicht wahr ?
Gruß,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:18 Di 16.01.2007 | | Autor: | AriR |
hey mathiash,
vielen dank für deine ganzen antworten auf meine fragen. Die haben mir alle gut geholfen.
Gruß Ari :)
|
|
|
|
