Ist Sprache regulär? < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:02 Fr 03.06.2011 | | Autor: | bandchef |
| Aufgabe | Beweisen oder widerlegen sie, dass die folgende Sprache regulär ist:
[mm] $L_1 =\{ 0^p | \text{p ist keine Primzahl} \}$ [/mm] |
Ich soll die Aufgabe lösen. Weiß aber so gar nicht wie ich da rangehen soll. Könnt ihr mir helfen? Allerdings: Mein erster Gedanke zur Lösung dieser Aufgabe war, man könnte es ja mit Pumpunk-Lemma versuchen. Wenn dieses erfüllt wird, dann ist die Sprache L regulär. Nun aber meine Frage: Wie wende ich das PL hier korrekt an?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:01 Fr 03.06.2011 | | Autor: | felixf |
Moin!
> Beweisen oder widerlegen sie, dass die folgende Sprache
> regulär ist:
>
> [mm]L_1 =\{ 0^p | \text{p ist keine Primzahl} \}[/mm]
>
>
> Ich soll die Aufgabe lösen. Weiß aber so gar nicht wie
> ich da rangehen soll. Könnt ihr mir helfen? Allerdings:
> Mein erster Gedanke zur Lösung dieser Aufgabe war, man
> könnte es ja mit Pumpunk-Lemma versuchen.
Das ist mal eine nette Schreibweise 
> Wenn dieses
> erfüllt wird, dann ist die Sprache L regulär. Nun aber
> meine Frage: Wie wende ich das PL hier korrekt an?
Nun, sei die Konstante $n$ aus dem Pumping-Lemma gegeben. Jetzt musst du eine Zahl $p$ waehlen, die keine Primzahl ist, und die fuer jede Zerlegung $p = a + b + c$ mit $a + b [mm] \le [/mm] n$ und $b > 1$ erfuellt, dass $a + c$ und $b$ teilerfremd sind. Dann kannst du naemlich mit Hilfe des ![[]](/images/popup.gif) Dirichletschen Primzahlsatzes einen Widerspruch bekommen.
Einfacher ist es aber wohl, ueber das Komplement zu gehen: die Sprache ist genau dann regulaer, wenn ihr Komplement regulaer ist. Zeige mit Hilfe des Pumping-Lemma, dass das Komplement eben nicht regulaer ist, indem du ein Wort [mm] $0^p$ [/mm] im Komplement konstruierst mit $p$ nicht prim.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:13 Fr 03.06.2011 | | Autor: | bandchef |
Können wir uns drauf einigen, dass wir für die Zerlegung die Buchstaben z=uvw wählen? Muss nicht eigentlich so heißen: $|uv| [mm] \leq [/mm] n$ und $|v|geq 1$? Die Betragsstriche geben die Teilwortlänge an; das haben wir zumindestens so gelernt. Da wir diesen Primzahlsatz noch nicht gelernt haben und wir (wahrscheinlich) auch nicht machen, würde ich lieber über den einfachere Weg des Komplements gehen.
Hilfst du mir noch weiter?
Ich hab jetzt auf meinem Blatt stehen:
Da ich ja nun mit dem Komplement arbeiten möchte, muss ich doch die Sprachdefinition erstmal ins Komplement wandeln. Mein Versuch:
[mm] $L_c [/mm] = [mm] \{ 0^p | \text{p ist Primzahl} \}$
[/mm]
Stimmt das so? Falls das jetzt richtig ist, muss ich auf diese Sprache doch nun das Pumping-Lemma anwenden. Also hab ich mal hingeschrieben: $z=uvw=...$
Weiter bin ich aber leider noch nicht gekommen weil's hier nämlich mit dem Verständnis aufhört...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:24 Fr 03.06.2011 | | Autor: | felixf |
Moin!
> Können wir uns drauf einigen, dass wir für die Zerlegung
> die Buchstaben z=uvw wählen? Muss nicht eigentlich so
> heißen: [mm]|uv| \leq n[/mm] und [mm]|v|geq 1[/mm]? Die Betragsstriche geben
> die Teilwortlänge an; das haben wir zumindestens so
> gelernt. Da wir diesen Primzahlsatz noch nicht gelernt
> haben und wir (wahrscheinlich) auch nicht machen, würde
> ich lieber über den einfachere Weg des Komplements gehen.
Ich hab von einer Zerlegung einer Zahl geredet, nicht einer Zerlegung eines Wortes 
In deiner Notation ist $u = [mm] 0^a$, [/mm] $v = [mm] 0^b$, [/mm] $w = [mm] 0^c$. [/mm] Dann bedeutet $|u v| [mm] \le [/mm] n$ gerade $a + b [mm] \le [/mm] n$, und $|v| [mm] \ge [/mm] 1$ bedeutet gerade $b [mm] \ge [/mm] 1$.
> Hilfst du mir noch weiter?
>
> Ich hab jetzt auf meinem Blatt stehen:
>
> Da ich ja nun mit dem Komplement arbeiten möchte, muss ich
> doch die Sprachdefinition erstmal ins Komplement wandeln.
> Mein Versuch:
>
> [mm]L_c = \{ 0^p | \text{p ist Primzahl} \}[/mm]
>
> Stimmt das so?
Ja, falls [mm] $\Sigma [/mm] = [mm] \{ 0 \}$ [/mm] das Alphabet ist.
> Falls das jetzt richtig ist, muss ich auf
> diese Sprache doch nun das Pumping-Lemma anwenden. Also hab
> ich mal hingeschrieben: [mm]z=uvw=...[/mm]
>
> Weiter bin ich aber leider noch nicht gekommen weil's hier
> nämlich mit dem Verständnis aufhört...
Nun, $u [mm] v^k [/mm] w = [mm] 0^{a + k b + c}$ [/mm] in meiner Notation.
Waehle $k$ nun so, dass $a + k b + c$ ganz bestimmt keine Primzahl ist.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:40 Fr 03.06.2011 | | Autor: | bandchef |
Frage noch zu deiner vorletzten Antwort. Du schreibst: "die Sprache ist genau dann regulaer, wenn ihr Komplement regulaer ist. Zeige mit Hilfe des Pumping-Lemma, dass das Komplement eben nicht regulaer ist, indem du ein Wort $ [mm] 0^p [/mm] $ im Komplement konstruierst mit p nicht prim."
Das verstehe ich aber nicht so ganz. Müsste es nicht so lauten: "die Sprache ist genau dann regulaer, wenn ihr Komplement NICHTregulaer ist. Zeige mit Hilfe des Pumping-Lemma, dass das Komplement eben nicht regulaer ist, indem du ein Wort $ [mm] 0^p [/mm] $ im Komplement konstruierst mit p nicht prim."
Ich hab das alles so auf meinem Blatt stehen:
[mm] $L_1 =\{ 0^p | \text{p ist keine Primzahl} \}$
[/mm]
Ich bilde Komplement von Sprache [mm] $L_1$ [/mm] weil die Sprache [mm] $L_1$ [/mm] genau dann regulaer ist, wenn ihr Komplement NICHT regulaer ist. Ich zeige mit Hilfe des Pumping-Lemma, dass das Komplement eben nicht regulaer ist, indem ich ein Wort $ [mm] 0^p [/mm] $ im Komplement konstruiere, welches mit p keine Primzahl ist.
[mm] $L_c [/mm] = [mm] \{ 0^p |\text{ p ist Primzahl} \} [/mm] mit [mm] $\Sigma =\{0\}$
[/mm]
Ich suche Zerlegung:
$z = uvw = uv^kw = [mm] u^a v^{k\cdot b} w^c [/mm] = [mm] 0^a 0^{k\cdot b} 0^c [/mm] = [mm] 0^{a+k\cdot b + c}$
[/mm]
Ich wähle [mm] $a+k\cdot [/mm] b + c$ nun so, dass es keine Primzahl ist.
Hierzu noch eine Frage: Wie schreibe ich nun den letzten Satz mathematisch richtig hin? Ich will z.B. haben, dass das jetzt gleich 12 ist. Muss ich mir jetzt geeignete a, b, c und k aussuchen, dass das passt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:35 So 05.06.2011 | | Autor: | felixf |
Moin!
> Frage noch zu deiner vorletzten Antwort. Du schreibst: "die
> Sprache ist genau dann regulaer, wenn ihr Komplement
> regulaer ist. Zeige mit Hilfe des Pumping-Lemma, dass das
> Komplement eben nicht regulaer ist, indem du ein Wort [mm]0^p[/mm]
> im Komplement konstruierst mit p nicht prim."
>
> Das verstehe ich aber nicht so ganz. Müsste es nicht so
> lauten: "die Sprache ist genau dann regulaer, wenn ihr
> Komplement NICHTregulaer ist.
Eben nicht: eine Sprache ist genau dann regulaer, wenn ihr Komplement regulaer ist. Wenn du einen Automaten hast, der eine Sprache $L$ akzeptiert, kannst du einfach die akzeptierenden Zustaende zu nichtakzeptierenden Zustaenden machen und umgekehrt: der Automat akzeptiert dann die Komplementaersprache.
> Zeige mit Hilfe des
> Pumping-Lemma, dass das Komplement eben nicht regulaer ist,
> indem du ein Wort [mm]0^p[/mm] im Komplement konstruierst mit p
> nicht prim."
Weder die Sprache selber noch ihr Komplement sind regulaer.
> Ich hab das alles so auf meinem Blatt stehen:
>
> [mm]L_1 =\{ 0^p | \text{p ist keine Primzahl} \}[/mm]
>
> Ich bilde Komplement von Sprache [mm]L_1[/mm] weil die Sprache [mm]L_1[/mm]
> genau dann regulaer ist, wenn ihr Komplement NICHT regulaer
> ist.
Falsch.
> Ich zeige mit Hilfe des Pumping-Lemma, dass das
> Komplement eben nicht regulaer ist, indem ich ein Wort [mm]0^p[/mm]
> im Komplement konstruiere, welches mit p keine Primzahl
> ist.
![[ok]](/images/smileys/ok.gif "[ok]")
> [mm]$L_c[/mm] = [mm]\{ 0^p |\text{ p ist Primzahl} \}[/mm] mit [mm]$\Sigma =\{0\}$[/mm]
> Ich suche Zerlegung:
>
> [mm]z = uvw = uv^kw = u^a v^{k\cdot b} w^c = 0^a 0^{k\cdot b} 0^c = 0^{a+k\cdot b + c}[/mm]
Du suchst keine Zerlegung. Du nimmst an, die Sprache [mm] $L^c$ [/mm] ist regulaer, wendest das Pumping-Lemma an, und nimmst dir eine Zerlegung eines Wortes. Daraus konsturierst du dann einen Widerspruch, womit die Sprache [mm] $L^c$ [/mm] nicht regulaer ist.
> Ich wähle [mm]a+k\cdot b + c[/mm] nun so, dass es keine Primzahl
> ist.
Wie waehlst du es denn? Das musst du schon genauer ausfuehren.
> Hierzu noch eine Frage: Wie schreibe ich nun den letzten
> Satz mathematisch richtig hin? Ich will z.B. haben, dass
> das jetzt gleich 12 ist. Muss ich mir jetzt geeignete a, b,
> c und k aussuchen, dass das passt?
Naja, wenn $a = 1$ und $c = 100$ ist, wirst du nicht auf 12 kommen.
Und $a, b, c$ kannst du dir nicht aussuchen. Nur $k$.
Versuch doch mal $k$ (und das Wort $w$) so zu waehlen, dass $a + k b + c$ durch $a + c > 1$ teilbar ist, und dass $a + k b + c > a + c$ ist. Daraus folgt dann, dass $a + k b + c$ nicht prim ist.
LG Felix
|
|
|
|
