Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:00 Mi 08.05.2013 | | Autor: | bandchef |
| Aufgabe | Beweisen oder widerlegen Sie, dass die Sprache regulär ist:
[mm] $L=\{a^n | n \in \mathbb N \text{ ist eine gerade Zahl}\}$ [/mm] |
Hi Leute!
Hier noch eine Übungsaufgabe. Diese Übungsaufgabe ist eine Abwandlung einer bisher schon gelösten Übungsaufgabe!
Behauptung: Die Sprache L ist regulär.
Sie L eine reguläre Sprache, dann gibt es ein $n [mm] \in \mathbb [/mm] N$, so dass sich jedes $z [mm] \in [/mm] L$ mit [mm] $|z|\geq [/mm] n$, so als $z=uvw$ schreiben lässt, dass $|uv| [mm] \leq [/mm] n$, $|v| [mm] \geq [/mm] 1$ und $uv^iw$ für alle [mm] $i\geq [/mm] 0$ gilt:
wähle: [mm] $z=a^n$, [/mm] $|z| = n [mm] \geq [/mm] n$
$n = |z| =|uvw| < |uv^2w| [mm] \leq [/mm] n+n < n+n+1$
d.h. n ist eine gerade Zahl zwischen n und n+n+1. Widerspruch!
Frage: Die Konstante n spiegelt die Anzahl der Zustände des (eventuellen) Automaten wieder, oder? Die Überlegung dahinter steckt in diesem Bild: http://s14.directupload.net/file/d/3249/e7urjo45_png.htm
Ich hab für die oben genannte Sprache versucht einen DEA zu malen. Das man mit der Sprache nicht fertig wird erklärt sich wohl von alleine; das sollen auch die drei "Folgepunkt" unter dem DEA ausdrücken.
Aber: Ist nun der Antwortsatz zu obigem Gegenbeweis wirklich richtig? Wo drehe ich denn da eigentlich die Schleife? Gehen wir mal von dem Wort für die gerade Zahl 2 aus. Dieser Automat hätte 3 Zustände. Wo würde hier dann gepumpt werden, wenn ich mir in obiger Gleichung für n=3 einsetze? Das würde ja dann so heißen: $3 = |z| =|uvw| < |uv^2w| [mm] \leq [/mm] 3+3 < 3+3+1$
Der Antwortsatz gibt aber dann irgendwie keinen Sinn mehr: Zwischen n=3 und n+n+1 = 3+3+1 = 7 gibt es sehr wohl eine gerade Zahl! Nämlich 4 und6!
Verwirrung: Ist hier eigentlich mit "gerader Zahl" "die gerade natürliche Anzahl" der a's gemeint, oder die gerade Zahl der Zustände vom Automaten?
"
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:31 Do 09.05.2013 | | Autor: | tobit09 |
Hallo bandchef,
> [mm]L=\{a^n | n \in \mathbb N \text{ ist eine gerade Zahl}\}[/mm]
> Behauptung: Die Sprache L ist regulär.
Genau. Das kann man durch Angabe eines DEA mit 3 Zuständen zeigen.
Das folgende sieht aber so aus, als wolltest du die Regularität von $L$ widerlegen?
> Sie L eine reguläre Sprache, dann gibt es ein [mm]n \in \mathbb N[/mm],
> so dass sich jedes [mm]z \in L[/mm] mit [mm]|z|\geq n[/mm], so als [mm]z=uvw[/mm]
> schreiben lässt, dass [mm]|uv| \leq n[/mm], [mm]|v| \geq 1[/mm] und [mm]uv^iw[/mm]
> für alle [mm]i\geq 0[/mm] gilt:
>
> wähle: [mm]z=a^n[/mm], [mm]|z| = n \geq n[/mm]
Dieses $z$ liegt nicht in $L$, falls $n$ ungerade.
>
> [mm]n = |z| =|uvw| < |uv^2w| \leq n+n < n+n+1[/mm]
>
> d.h. n ist eine gerade Zahl zwischen n und n+n+1.
> Widerspruch!
Das ist doch kein Widerspruch!
> Frage: Die Konstante n spiegelt die Anzahl der Zustände
> des (eventuellen) Automaten wieder, oder?
Ja. Dem Beweis des Pumping Lemmas kann man entnehmen, dass für jede durch einen DEA mit $n$ Zuständen akzeptierte Sprache dieses $n$ die Eigenschaft aus dem PL hat.
> Die Überlegung
> dahinter steckt in diesem Bild:
> http://s14.directupload.net/file/d/3249/e7urjo45_png.htm
> Ich hab für die oben genannte Sprache versucht einen DEA
> zu malen. Das man mit der Sprache nicht fertig wird
> erklärt sich wohl von alleine; das sollen auch die drei
> "Folgepunkt" unter dem DEA ausdrücken.
Falsches Bild hochgeladen? Warum stehen da 0en und 1en statt a's an den Pfeilen? Warum gehen von manchen Zuständen mehrere Pfeile mit identischer Beschriftung aus und von anderen Zuständen gar keiner? So ist das jedenfalls kein DEA.
> Aber: Ist nun der Antwortsatz zu obigem Gegenbeweis
> wirklich richtig? Wo drehe ich denn da eigentlich die
> Schleife? Gehen wir mal von dem Wort für die gerade Zahl 2
> aus. Dieser Automat hätte 3 Zustände.
Verstehe ich dich richtig, dass du hier einen DEA für die einelementige Sprache [mm] $L':=\{aa\}$ [/mm] meinst?
> Wo würde hier dann
> gepumpt werden, wenn ich mir in obiger Gleichung für n=3
> einsetze? Das würde ja dann so heißen: [mm]3 = |z| =|uvw| < |uv^2w| \leq 3+3 < 3+3+1[/mm]
>
> Der Antwortsatz gibt aber dann irgendwie keinen Sinn mehr:
> Zwischen n=3 und n+n+1 = 3+3+1 = 7 gibt es sehr wohl eine
> gerade Zahl! Nämlich 4 und6!
Genau. In der Tat hast du nirgendwo einen Widerspruch hergeleitet.
> Verwirrung: Ist hier eigentlich mit "gerader Zahl" "die
> gerade natürliche Anzahl" der a's gemeint, oder die gerade
> Zahl der Zustände vom Automaten?"
In der Definition von $L$ natürlich ersteres. Hast du vielleicht das $n$ aus dem PL mit dem $n$ aus der Definition von $L$ verwechselst? Das $n$ in der Definition von $L$ hat nichts mit der Zahl $n$ aus dem PL zu tun.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:11 Do 09.05.2013 | | Autor: | bandchef |
> Genau. Das kann man durch Angabe eines DEA mit 3 Zuständen zeigen.
Aber wenn ich die gerade Anzahl a's von 888888 mit einem DEA zeigen will, dann brauch ich ja 888888 Zustände! Dann kommt der nächste, der will 2222222 a's haben der nächste will dann 4444444 a's usw usf dann werde ich ja nie fertig und die Sprache kann doch dann nicht regulär sein, oder?
> Das folgende sieht aber so aus, als wolltest du die Regularität von L widerlegen?
Genau deswegen wollte ich ja auch die behauptete Regularität von L mit einem Widerspruchsbeweis durch das PL widerlegen!
Wäre dann wohl diese Antwort von dir schon die Lösung der Sprache gewesen?
> Dieses $z$ liegt nicht in $L$, falls $n$ ungerade.
Du hast Recht. Der Automat war falsch. Hier ein neuer: http://s7.directupload.net/file/d/3250/279yje8u_png.htm
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:42 Do 09.05.2013 | | Autor: | tobit09 |
> > Genau. Das kann man durch Angabe eines DEA mit 3 Zuständen
> zeigen.
>
> Aber wenn ich die gerade Anzahl a's von 888888 mit einem
> DEA zeigen will, dann brauch ich ja 888888 Zustände! Dann
> kommt der nächste, der will 2222222 a's haben der nächste
> will dann 4444444 a's usw usf dann werde ich ja nie fertig
> und die Sprache kann doch dann nicht regulär sein, oder?
>
> Du hast Recht. Der Automat war falsch. Hier ein neuer:
> http://s7.directupload.net/file/d/3250/279yje8u_png.htm
Streiche alle Zustände [mm] $q_i$ [/mm] mit $i>2$ und male einen mit $a$ beschrifteten Pfeil von [mm] $q_2$ [/mm] nach [mm] $q_1$.
[/mm]
> > Das folgende sieht aber so aus, als wolltest du die
> Regularität von L widerlegen?
>
> Genau deswegen wollte ich ja auch die behauptete
> Regularität von L mit einem Widerspruchsbeweis durch das
> PL widerlegen!
Wenn du "Behauptung: $L$ regulär" schreibst, sieht es so aus, als würdest du behaupten wollen, $L$ sei regulär.
Schreibe stattdessen in so einem Fall: "Behauptung: $L$ nicht regulär. Widerspruchsannahme: $L$ regulär."
> Wäre dann wohl diese Antwort von dir schon die Lösung der
> Sprache gewesen?
>
> > Dieses [mm]z[/mm] liegt nicht in [mm]L[/mm], falls [mm]n[/mm] ungerade.
Ich sehe nicht, was dieser Satz für sich genommen mit einer Lösung der Aufgabe zu tun hat.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:26 Fr 10.05.2013 | | Autor: | bandchef |
> Ich sehe nicht, was dieser Satz für sich genommen mit einer Lösung der Aufgabe zu tun hat.
Genau deswegen gleich nochmal von vorne:
Behauptung: Die Sprache L ist nicht regulär.
Sie L eine reguläre Sprache, dann gibt es ein $n [mm] \in \mathbb [/mm] N$, so dass sich jedes $z [mm] \in [/mm] L$ mit [mm] $|z|\geq [/mm] n$, so als $z=uvw$ schreiben lässt, dass $|uv| [mm] \leq [/mm] n$, $|v| [mm] \geq [/mm] 1$ und $uv^iw$ für alle [mm] $i\geq [/mm] 0$ gilt:
wähle: [mm] $z=a^n$, [/mm] $|z| = n [mm] \geq [/mm] n$
$|uv^iw| = [mm] a^{|u|} a^{i\cdot |v|} a^{n-|uv|} [/mm] = ... = [mm] a^{|v| \cdot (i-1)+n}$
[/mm]
[mm] $\Rightarrow [/mm] |v| [mm] \cdot [/mm] (i-1)+n < n$
[mm] $\Leftrightarrow [/mm] |v| [mm] \cdot [/mm] (i-1) < 0$
[mm] $\Leftrightarrow [/mm] i < 1$
mit i=0, da i<1 gilt: $uv^0w [mm] \notin [/mm] L$ Widerspruch!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:28 Fr 10.05.2013 | | Autor: | tobit09 |
> Behauptung: Die Sprache L ist nicht regulär.
Wie gesagt: Falsch, sie ist regulär. Wie du einen DEA für $L$ erhältst, habe ich in der vorherigen Antwort geschrieben.
> Sie L eine reguläre Sprache, dann gibt es ein [mm]n \in \mathbb N[/mm],
> so dass sich jedes [mm]z \in L[/mm] mit [mm]|z|\geq n[/mm], so als [mm]z=uvw[/mm]
> schreiben lässt, dass [mm]|uv| \leq n[/mm], [mm]|v| \geq 1[/mm] und [mm]uv^iw[/mm]
> für alle [mm]i\geq 0[/mm] gilt:
>
> wähle: [mm]z=a^n[/mm], [mm]|z| = n \geq n[/mm]
Dieses $z$ muss kein Element von $L$ sein, da n nicht gerade sein muss. Also macht die Bedingung aus dem Pumping Lemma möglicherweise keine Aussage über dieses $z$.
(Ich ignoriere diesen Punkt im Folgenden und tue so, als ob [mm] $z\in [/mm] L$ gelten würde.)
Dann gibt es Wörter $u,v,w$ mit $z=uvw$, so dass [mm] $|uv|\le [/mm] n$, [mm] $|v|\ge1$ [/mm] und [mm] $uv^iw\in [/mm] L$ für alle [mm] $i\in \IN_0$.
[/mm]
> [mm]|uv^iw| = a^{|u|} a^{i\cdot |v|} a^{n-|uv|} = ... = a^{|v| \cdot (i-1)+n}[/mm]
gilt für alle [mm] $i\in \IN_0$. [/mm] ![[ok]](/images/smileys/ok.gif "[ok]")
> [mm]\Rightarrow |v| \cdot (i-1)+n < n[/mm]
Woraus soll das folgen?
> [mm]\Leftrightarrow |v| \cdot (i-1) < 0[/mm]
>
> [mm]\Leftrightarrow i < 1[/mm]
Folgerichtig.
> mit i=0, da i<1 gilt: [mm]uv^0w \notin L[/mm] Widerspruch!
Warum sollte [mm] $uv^0w\notin [/mm] L$ gelten?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:41 Fr 10.05.2013 | | Autor: | bandchef |
> Woraus soll das folgen?
Die Formel [mm] $\Rightarrow [/mm] |v| [mm] \cdot [/mm] (i-1)+n < n$ folgt aus der Potenz dieser Berechnung $|uv^iw| = [mm] a^{|u|} a^{i\cdot |v|} a^{n-|uv|} [/mm] = ... = [mm] a^{|v| \cdot (i-1)+n}$.
[/mm]
> Warum sollte [mm] $uv^0w\notin [/mm] L$ gelten?
Tja, das ist hier jetzt wieder die Stelle an der ich keine Ahnung mehr hab. Aber du hast schon Recht. [mm] $\notin [/mm] L$ kann nicht gehen, weil ja die Sprache regulär ist. Ist an dieser Stelle dann das PL das falsche Mittel? Mann kann ja mit dem PL einen Widerspruchsbeweis führe, aber nicht zwingend belegen, dass eine Sprache regulär ist, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:17 Sa 11.05.2013 | | Autor: | tobit09 |
> > Woraus soll das folgen?
>
> Die Formel [mm]\Rightarrow |v| \cdot (i-1)+n < n[/mm] folgt aus der
> Potenz dieser Berechnung [mm]|uv^iw| = a^{|u|} a^{i\cdot |v|} a^{n-|uv|} = ... = a^{|v| \cdot (i-1)+n}[/mm].
$|v|*(i-1)+n$ ist die Anzahl der a's in $uv^iw$, ok, aber warum soll diese Anzahl kleiner als $n$ sein?
> > Warum sollte [mm]uv^0w\notin L[/mm] gelten?
>
> Tja, das ist hier jetzt wieder die Stelle an der ich keine
> Ahnung mehr hab. Aber du hast schon Recht. [mm]\notin L[/mm] kann
> nicht gehen, weil ja die Sprache regulär ist. Ist an
> dieser Stelle dann das PL das falsche Mittel? Mann kann ja
> mit dem PL einen Widerspruchsbeweis führe, aber nicht
> zwingend belegen, dass eine Sprache regulär ist, oder?
Richtig.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:02 So 12.05.2013 | | Autor: | bandchef |
Hm, ich werd mir dann dazu keine weiteren Gedanken mehr machen weil bei dieser Aufgabe eh kein PL funktioniert.
|
|
|
|
