Pumping-Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:01 So 10.06.2012 | | Autor: | bandchef |
| Aufgabe | | Beweisen oder widerlegen Sie, dass die Sprache $L = [mm] \{ 0^{i^3+i^2} | i \in \mathbb N\}$ [/mm] regulär ist. |
Hallo!
Hier wie versprochen die neue Aufgabe:
Wenn L regulär wäre, dann gäbe es eine $n>0$, so dass es zu jedem $z [mm] \in [/mm] L$ mit $|z| [mm] \leq \mathbb [/mm] N$ eine Zerlegung $z = uvw$ gibt, mit $|v| > 0$, $|uv| [mm] \leq [/mm] n$ und [mm] $uv^\star [/mm] w [mm] \in [/mm] L$.
Wir setzen $z = [mm] 0^{n^3+n^2} [/mm] = [mm] 0^{n^3} 0^{n^2}$, [/mm] dann ist $z [mm] \in [/mm] L$ mit $|z| [mm] \geq [/mm] n$.
Sei $z=uvw$ eine Zerlegung nach dem PL. Weil $|uv| [mm] \leq [/mm] n$ ist, gibt es ein $k [mm] \in \mathbb [/mm] N$:
$z = uvw = [mm] 0^{k_1} 0^{k_2} 0^{k_3} 0^{n^2}$ [/mm] mit [mm] $k_1 [/mm] + [mm] k_2 [/mm] + [mm] k_3 [/mm] = [mm] n^3$
[/mm]
i=0:
$z = uv^0w = [mm] 0^{k_1} \left( 0^{k_2}\right)^0 0^{k_3} 0^{n^2} [/mm] = [mm] 0^{k_1} 0^{k_3} 0^{n^2} \notin [/mm] L$, da [mm] $k_1 [/mm] + [mm] k_3 [/mm] < [mm] n^3$
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:51 So 10.06.2012 | | Autor: | Helbig |
> Beweisen oder widerlegen Sie, dass die Sprache [mm]L = \{ 0^{i^3+i^2} | i \in \mathbb N\}[/mm]
> regulär ist.
> Hallo!
>
> Hier wie versprochen die neue Aufgabe:
>
>
>
> Wenn L regulär wäre, dann gäbe es eine [mm]n>0[/mm], so dass es
> zu jedem [mm]z \in L[/mm] mit [mm]|z| \leq \mathbb N[/mm] eine Zerlegung [mm]z = uvw[/mm]
> gibt, mit [mm]|v| > 0[/mm], [mm]|uv| \leq n[/mm] und [mm]uv^\star w \in L[/mm].
>
>
> Wir setzen [mm]z = 0^{n^3+n^2} = 0^{n^3} 0^{n^2}[/mm], dann ist [mm]z \in L[/mm]
> mit [mm]|z| \geq n[/mm].
>
>
> Sei [mm]z=uvw[/mm] eine Zerlegung nach dem PL. Weil [mm]|uv| \leq n[/mm] ist,
> gibt es ein [mm]k \in \mathbb N[/mm]:
>
> [mm]z = uvw = 0^{k_1} 0^{k_2} 0^{k_3} 0^{n^2}[/mm] mit [mm]k_1 + k_2 + k_3 = n^3[/mm]
Hier mußt Du unbedingt angeben, was die k's bedeuten sollen.
>
>
> i=0:
>
> [mm]z = uv^0w = 0^{k_1} \left( 0^{k_2}\right)^0 0^{k_3} 0^{n^2} = 0^{k_1} 0^{k_3} 0^{n^2} \notin L[/mm],
> da [mm]k_1 + k_3 < n^3[/mm]
Warum ist [mm] $k_1+k_3 [/mm] < [mm] n^3$? [/mm] Auch dies muß begründet werden.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:09 Mo 11.06.2012 | | Autor: | bandchef |
Zitat: "
$ z = uvw = [mm] 0^{k_1} 0^{k_2} 0^{k_3} 0^{n^2} [/mm] $ mit $ [mm] k_1 [/mm] + [mm] k_2 [/mm] + [mm] k_3 [/mm] = [mm] n^3 [/mm] $
Hier mußt Du unbedingt angeben, was die k's bedeuten sollen."
Meinst du damit nun, dass ich die k's in u und v unterteilen soll? Aber im anderen Thread hast du geschrieben, dass man "Aus Stilgründen sollten wir möglichst wenig Namen einfügen. Den Längen von v und u geben wir gar keine Namen.", nicht machen sollte. Was soll ich an dieser Stelle dann sonst tun?
Zitat: "
i=0:
$ z = uv^0w = [mm] 0^{k_1} \left( 0^{k_2}\right)^0 0^{k_3} 0^{n^2} [/mm] = [mm] 0^{k_1} 0^{k_3} 0^{n^2} \notin [/mm] L $,
da $ [mm] k_1 [/mm] + [mm] k_3 [/mm] < [mm] n^3 [/mm] $
Warum ist $ [mm] k_1+k_3 [/mm] < [mm] n^3 [/mm] $? Auch dies muß begründet werden."
Was soll man hier begründen? Kann man das nicht alleine auf Grund der Aussage so stehen lassen, dass wenn [mm] $k_1 [/mm] + [mm] k_2 [/mm] + [mm] k_3 [/mm] = [mm] n^3$, [/mm] dann $ [mm] k_1 [/mm] + [mm] k_3 [/mm] < [mm] n^3 [/mm] $ (also kleiner) ist? Das einzige was ich mir vorstellen kann, ist, dass man noch spezifizieren muss, wie lang ein einzelnes k ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:15 Mo 11.06.2012 | | Autor: | Helbig |
> Zitat: "
> [mm]z = uvw = 0^{k_1} 0^{k_2} 0^{k_3} 0^{n^2}[/mm] mit [mm]k_1 + k_2 + k_3 = n^3[/mm]
>
> Hier mußt Du unbedingt angeben, was die k's bedeuten
> sollen."
>
> Meinst du damit nun, dass ich die k's in u und v
> unterteilen soll? Aber im anderen Thread hast du
> geschrieben, dass man "Aus Stilgründen sollten wir
> möglichst wenig Namen einfügen. Den Längen von v und u
> geben wir gar keine Namen.", nicht machen sollte. Was soll
> ich an dieser Stelle dann sonst tun?
Entweder keine Namen einführen, also auch nicht die k's, oder, wenn Du Namen einführen willst, solltest Du auch schreiben, für was die k's stehen. Sonst ist das sinnlos.
>
>
>
>
> Zitat: "
> i=0:
>
> [mm]z = uv^0w = 0^{k_1} \left( 0^{k_2}\right)^0 0^{k_3} 0^{n^2} = 0^{k_1} 0^{k_3} 0^{n^2} \notin L [/mm],
>
> da [mm]k_1 + k_3 < n^3[/mm]
>
> Warum ist [mm]k_1+k_3 < n^3 [/mm]? Auch dies muß begründet
> werden."
>
> Was soll man hier begründen? Kann man das nicht alleine
> auf Grund der Aussage so stehen lassen, dass wenn [mm]k_1 + k_2 + k_3 = n^3[/mm],
> dann [mm]k_1 + k_3 < n^3[/mm] (also kleiner) ist? Das einzige was
> ich mir vorstellen kann, ist, dass man noch spezifizieren
> muss, wie lang ein einzelnes k ist.
Genau! Und es sieht so aus, also ob [mm] $k_2$ [/mm] die Länge von $v$ sein soll. Dann wissen wir, daß [mm] $1\le k_2$ [/mm] ist. Und nur dann ist [mm] $k_1+k_3 [/mm] < [mm] n^3$.
[/mm]
Abgesehen davon mußt Du ja noch zeigen, daß $uw$ nicht in $L$ liegt. Das heißt, daß die Länge von $uw$ sich nicht als [mm] $m^3+m^2$ [/mm] für irgendwelche natürliche Zahlen $m$ darstellen läßt. Dies scheint mir schwierig, bzw. stimmt vielleicht auch gar nicht. In solchen Fällen mußt Du ein anderes $i$ wählen, z. B. $i=2$.
Grüße,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:19 Mo 11.06.2012 | | Autor: | bandchef |
Zitat: "Genau! Und es sieht so aus, also ob $ [mm] k_2 [/mm] $ die Länge von $ v $ ist."
Du schreibst hier, dass es so aussieht, als ob [mm] $k_2$ [/mm] die Länge von v ist. [mm] $k_2$ [/mm] tut nicht nur so, sondern soll mit meinen Überlegungen das auch tun. Im anderen Thread hast du aber davon gesprochen, dass ich auf keinen Fall fest definieren soll, wo ich die Schleife - also ja auch die Position des v's - positioniere. Wäre es - da ich es ja hier anscheinend zumindestens zum Teil richtig gemacht habe - für den Leser kenntlich machen, aus was und wo sich u, v und w zusammensetzt? Ich hab schon ein paar Mal diese Klammern benutzt, die angegeben haben wo was sitzt. Unser Prof. hat das bisher auch desöfteren so gemacht. Was spricht dann jetzt genau dagegen? Ich hab jetzt hier den Beweis nochmal komplett angeführt (auch mit der genauen Definition uvw):
Wenn L regulär wäre, dann gäbe es eine n>0, so dass es zu jedem $ z [mm] \in [/mm] L $ mit $ |z| [mm] \leq \mathbb [/mm] N $ eine Zerlegung z = uvw gibt, mit |v| > 0, $ |uv| [mm] \leq [/mm] n $ und $ [mm] uv^\star [/mm] w [mm] \in [/mm] L $.
Wir setzen $ z = [mm] 0^{n^3+n^2} [/mm] = [mm] 0^{n^3} 0^{n^2} [/mm] $, dann ist $ z [mm] \in [/mm] L $ mit $ |z| [mm] \geq [/mm] n $.
Sei z=uvw eine Zerlegung nach dem PL. Weil $ |uv| [mm] \leq [/mm] n $ ist, gibt es ein $ k [mm] \in \mathbb [/mm] N $:
$ z = uvw = [mm] \underbrace{0^{k_1}}_{=u} \underbrace{0^{k_2}}_{=v} \underbrace{0^{k_3} 0^{n^2}}_{=w} [/mm] $ mit $ [mm] k_1 [/mm] + [mm] k_2 [/mm] + [mm] k_3 [/mm] = [mm] n^3 [/mm] $, [mm] $k_2 \geq [/mm] 1$ und [mm] $k_1 [/mm] + [mm] k_3 [/mm] < [mm] n^3$
[/mm]
i=2:
$ z = uv^2w = [mm] 0^{k_1} \left( 0^{k_2}\right)^2 0^{k_3} 0^{n^2} [/mm] = [mm] 0^{k_1} 0^{2k_2} 0^{k_3} 0^{n^2} [/mm] = [mm] 0^{k_1} 0^{k_2} 0^{k_3} 0^{n^2} 0^{k_2} [/mm] = z [mm] 0^{k_2} \notin [/mm] L $, da ...?
Zitat: "Abgesehen davon mußt Du ja noch zeigen, daß $ uw $ nicht in $ L $ liegt. Das heißt, das die Länge von $ uv $ sich nicht als $ [mm] m^3+m^2 [/mm] $ für irgendwelche natürliche Zahlen $ m $ darstellen läßt. Dies scheint mir schwierig, bzw. stimmt vielleicht auch gar nicht. In solchen Fällen mußt Du ein anderes $ i $ wählen, z. B. $ i=2 $."
Und genau hier weiß ich dann wieder nicht mehr weiter. Du schreibst, dass ich noch zeigen muss, dass $ uw $ nicht in $ L $ liegt. $uw$ alleine aufgeschrieben sieht ja so aus: [mm] 0^{k_1} 0^{k_3} 0^{n^2}. [/mm] Wie ich weiter oben schon definiert habe, ist [mm] $k_1 [/mm] + [mm] k_3 [/mm] < [mm] n^3$, [/mm] was aber, damit es in L liegt, $= [mm] n^3$ [/mm] sein müsste.
Ich weiß nicht ob das jetzt alles die richtigen Schritte in Richtung korrekter Beweis waren...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:47 Mo 11.06.2012 | | Autor: | Helbig |
> Zitat: "Genau! Und es sieht so aus, also ob [mm]k_2[/mm] die Länge
> von [mm]v[/mm] ist."
>
> Du schreibst hier, dass es so aussieht, als ob [mm]k_2[/mm] die
> Länge von v ist. [mm]k_2[/mm] tut nicht nur so, sondern soll mit
> meinen Überlegungen das auch tun.
Na ja, denn schreib das doch: Sei [mm] $k_2=|v|$. [/mm]
> Im anderen Thread hast
> du aber davon gesprochen, dass ich auf keinen Fall fest
> definieren soll, wo ich die Schleife - also ja auch die
> Position des v's - positioniere.
Richtig. Es ist verboten, $v$ oder die Lage von $v$ fest vorzugeben, aber es ist erlaubt,
der Länge von $v$ einen Namen zu geben. Wenn Du das machst, mußt Du das aber dem Leser mitteilen!
> Wäre es - da ich es ja
> hier anscheinend zumindestens zum Teil richtig gemacht habe
> - für den Leser kenntlich machen, aus was und wo sich u, v
> und w zusammensetzt?
Nur wenn Du das begründen kannst! So konnten wir in dem anderen Beispiel nachweisen, daß $v$ nur aus Nullen besteht und nicht in die Einsen reinreicht. Aber mehr nicht.
> Ich hab schon ein paar Mal diese
> Klammern benutzt, die angegeben haben wo was sitzt. Unser
> Prof. hat das bisher auch desöfteren so gemacht. Was
> spricht dann jetzt genau dagegen?
Wenn Du das so darstellst, machst Du Dir ein Bild von einer speziellen Zerlegung. Du mußt den Beweis aber für alle Zerlegungen führen, mit den vom PL vorgegebenen und mittlerweile wohl sattsam bekannten Eigenschaften, nämlich [mm] $|uv|\le [/mm] n$ und [mm] $1\le [/mm] |v|$.
Und so etwas kann man nur mit Worten aber nicht mit einem Bild darstellen.
> Ich hab jetzt hier den
> Beweis nochmal komplett angeführt (auch mit der genauen
> Definition uvw):
>
>
>
>
> Wenn L regulär wäre, dann gäbe es eine n>0, so dass es
> zu jedem [mm]z \in L[/mm] mit [mm]|z| \leq \mathbb N[/mm] eine Zerlegung z =
> uvw gibt, mit |v| > 0, [mm]|uv| \leq n[/mm] und [mm]uv^\star w \in L [/mm].
>
>
> Wir setzen [mm]z = 0^{n^3+n^2} = 0^{n^3} 0^{n^2} [/mm], dann ist [mm]z \in L[/mm]
> mit [mm]|z| \geq n [/mm].
>
>
> Sei z=uvw eine Zerlegung nach dem PL. Weil [mm]|uv| \leq n[/mm] ist,
> gibt es ein [mm]k \in \mathbb N [/mm]:
>
> [mm]z = uvw = \underbrace{0^{k_1}}_{=u} \underbrace{0^{k_2}}_{=v} \underbrace{0^{k_3} 0^{n^2}}_{=w}[/mm]
> mit [mm]k_1 + k_2 + k_3 = n^3 [/mm], [mm]k_2 \geq 1[/mm] und [mm]k_1 + k_3 < n^3[/mm]
Dieser Satz ist Unsinn. Was ist mit dem $k$?
Und die anderen $k's$: Entweder, Du verzichtest auf sie oder Du schreibst explizit, für was sie stehen. Also [mm] $k_1=|u|, k_2=|v|$. [/mm] Dann ist [mm] $k_1+k_2\le [/mm] n < [mm] n^3$, [/mm] also gibt es ein [mm] $k_3>0$ [/mm] mit [mm] $k_1+k_2+k_3=n^3$. [/mm] So müßtest Du argumentieren. Aber: Für den Beweis hier ist es völlig unerheblich, wie lang die einzelnen Worte sind. Wichtig ist hier [mm] $1\le [/mm] |v| [mm] \le [/mm] n$. Aber das weiß man erst, nachdem man den Beweis geführt hat. Das heißt, Du solltest Dir zuerst den Beweis überlegen, und dann für dort häufig gebrauchte komplizierte Ausdrücke Namen einführen.
>
>
> i=2:
>
> [mm]z = uv^2w = 0^{k_1} \left( 0^{k_2}\right)^2 0^{k_3} 0^{n^2} = 0^{k_1} 0^{2k_2} 0^{k_3} 0^{n^2} = 0^{k_1} 0^{k_2} 0^{k_3} 0^{n^2} 0^{k_2} = z 0^{k_2} \notin L [/mm],
> da ...?
>
>
> Zitat: "Abgesehen davon mußt Du ja noch zeigen, daß [mm]uw[/mm]
> nicht in [mm]L[/mm] liegt. Das heißt, das die Länge von [mm]uv[/mm] sich
> nicht als [mm]m^3+m^2[/mm] für irgendwelche natürliche Zahlen [mm]m[/mm]
> darstellen läßt. Dies scheint mir schwierig, bzw. stimmt
> vielleicht auch gar nicht. In solchen Fällen mußt Du ein
> anderes [mm]i[/mm] wählen, z. B. [mm]i=2 [/mm]."
>
> Und genau hier weiß ich dann wieder nicht mehr weiter. Du
> schreibst, dass ich noch zeigen muss, dass [mm]uw[/mm] nicht in [mm]L[/mm]
> liegt. [mm]uw[/mm] alleine aufgeschrieben sieht ja so aus: [mm]0^{k_1} 0^{k_3} 0^{n^2}.[/mm]
> Wie ich weiter oben schon definiert habe, ist [mm]k_1 + k_3 < n^3[/mm],
> was aber, damit es in L liegt, [mm]= n^3[/mm] sein müsste.
Falsch! $|uw|$ liegt genau dann in $L$, wenn es einen natürliche Zahl $m$ gibt mit [mm] $|uw|=m^2+m^3$. [/mm] Dieses $m$ hat mit dem $n$ überhaupt nichts zu tun.
>
> Ich weiß nicht ob das jetzt alles die richtigen Schritte
> in Richtung korrekter Beweis waren...
Waren sie nicht.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:25 Di 12.06.2012 | | Autor: | Helbig |
Ich weiß jetzt, warum $|uw|$ nicht in $L$ liegt:
Weil [mm] $1\le|v|$ [/mm] ist, ist
$|uw| = [mm] |uvw|-|v|=n^3+n^2-|v|
Weil [mm] $|v|\le [/mm] n$ ist, ist
$|uw|=|uvw|-|v| [mm] \ge n^3-n^2-n$.
[/mm]
Nun ist
[mm] $(n-1)^3+(n-1)^2 [/mm] < [mm] n^3-n^2-n$ [/mm] für alle [mm] $n\in \IN$, $1\le [/mm] n$, wie Du leicht nachrechnen kannst.
Damit ist [mm] $(n-1)^3+(n-1)^2 [/mm] < |uw| < [mm] n^3+n^2$, [/mm] und hieraus folgt [mm] $|uw|\notin [/mm] L$.
OK?
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:40 Di 12.06.2012 | | Autor: | bandchef |
Sorry, hab fälschlicherweise meine neue Frage als Mitteilung gepostet. Siehe nun die neue Frage!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:04 Di 12.06.2012 | | Autor: | bandchef |
Ich hab mir nun deine Antwort und Mitteilung durchgelesen einiges hab ich verstanden einiges aber auch nicht. Hier mal nochmal alles soweit ich das hab:
Wenn L regulär wäre, dann gäbe es ein n>0, so dass es zu jedem $ z [mm] \in [/mm] L $ mit $ |z| [mm] \leq \mathbb [/mm] N $ eine Zerlegung z = uvw gibt, mit |v| $ [mm] \neq \epsilon, [/mm] $ $ |uv| [mm] \leq [/mm] n $ und $ [mm] uv^\star [/mm] w [mm] \in [/mm] L $.
Wir setzen $ z = [mm] 0^{n^3+n^2} [/mm] = [mm] 0^{n^3} 0^{n^2} [/mm] $, dann ist $ z [mm] \in [/mm] L $ mit $ |z| [mm] \geq [/mm] n $.
Sei z=uvw eine Zerlegung nach dem PL. Weil $ |uv| [mm] \leq [/mm] n $ ist, gibt es ein $ k [mm] \in \mathbb [/mm] N $:
$ z = uvw = [mm] \underbrace{0^{k_1}}_{=u} \underbrace{0^{k_2}}_{=v} \underbrace{0^{k_3} 0^{n^2}}_{=w} [/mm] $ mit $ [mm] k_1 [/mm] = |u| $, $ [mm] k_2 [/mm] = |v| $, $ [mm] k_1 [/mm] + [mm] k_2 \leq [/mm] n < [mm] n^3 [/mm] $ und $ [mm] k_3 [/mm] > 0 $ somit folgt: $ [mm] k_1 [/mm] + [mm] k_2 [/mm] + [mm] k_3 [/mm] = [mm] n^3 [/mm] $.
Stimmt's soweit?
Zitat: "Falsch! $ |uw| $ liegt genau dann in $ L $, wenn es einen natürliche Zahl $ m $ gibt mit $ [mm] |uw|=m^2+m^3 [/mm] $. Dieses $ m $ hat mit dem $ n $ überhaupt nichts zu tun."
Das kapier ich nicht ganz. Muss ich an dieser Stelle, wo man pumpt, quasi zeigen, dass $ |uw| [mm] \notin [/mm] L $ ist? Kommt hier dann der Teil zum Tragen, den du in der Mitteilung geschrieben hast?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:52 Di 12.06.2012 | | Autor: | Helbig |
> Ich hab mir nun deine Antwort und Mitteilung durchgelesen
> einiges hab ich verstanden einiges aber auch nicht. Hier
> mal nochmal alles soweit ich das hab:
>
> Wenn L regulär wäre, dann gäbe es ein n>0, so dass es zu
> jedem [mm]z \in L[/mm] mit [mm]|z| \leq \mathbb N[/mm] eine Zerlegung z = uvw
> gibt, mit |v| [mm]\neq \epsilon,[/mm] [mm]|uv| \leq n[/mm] und [mm]uv^\star w \in L [/mm].
>
>
> Wir setzen [mm]z = 0^{n^3+n^2} = 0^{n^3} 0^{n^2} [/mm], dann ist [mm]z \in L[/mm]
> mit [mm]|z| \geq n [/mm].
>
>
> Sei z=uvw eine Zerlegung nach dem PL. Weil [mm]|uv| \leq n[/mm] ist,
> gibt es ein [mm]k \in \mathbb N [/mm]:
>
> [mm]z = uvw = \underbrace{0^{k_1}}_{=u} \underbrace{0^{k_2}}_{=v} \underbrace{0^{k_3} 0^{n^2}}_{=w}[/mm]
> mit [mm]k_1 = |u| [/mm], [mm]k_2 = |v| [/mm], [mm]k_1 + k_2 \leq n < n^3[/mm] und [mm]k_3 > 0[/mm]
> somit folgt: [mm]k_1 + k_2 + k_3 = n^3 [/mm].
>
>
> Stimmt's soweit?
Schon besser. Immer ist noch $k$ ohne Bedeutung und taucht später nicht mehr auf. Ist also überflüssig wie ein Kropf. Wichtig ist außerdem, das [mm] $k_2 [/mm] > 0$ ist, und nicht [mm] $k_3$. [/mm] Denn nur [mm] $k_2$ [/mm] wird später im Beweis gebraucht. Genauer wird [mm] $1\le k_2 \le [/mm] n$ gebraucht.
>
>
> Zitat: "Falsch! [mm]|uw|[/mm] liegt genau dann in [mm]L [/mm], wenn es einen
> natürliche Zahl [mm]m[/mm] gibt mit [mm]|uw|=m^2+m^3 [/mm]. Dieses [mm]m[/mm] hat mit
> dem [mm]n[/mm] überhaupt nichts zu tun."
>
> Das kapier ich nicht ganz. Muss ich an dieser Stelle, wo
> man pumpt, quasi zeigen, dass [mm]|uw| \notin L[/mm] ist? Kommt hier
> dann der Teil zum Tragen, den du in der Mitteilung
> geschrieben hast?
Genau das mußt Du zeigen. Es gibt ein $i$, so daß [mm] $uv^iw\notin [/mm] L$. Früher hatte ich das mal mit $i=2$ gezeigt und in der letzten Mitteilung mit $i=0$. So ein $i$ dürfte es nach dem PL nicht geben, wenn die Sprache regulär ist.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:01 Di 12.06.2012 | | Autor: | bandchef |
Zitat: "Schon besser. Immer ist noch k ohne Bedeutung und taucht später nicht mehr auf. Ist also überflüssig wie ein Kropf. Wichtig ist außerdem, das $ [mm] k_2 [/mm] > 0 $ ist, und nicht $ [mm] k_3 [/mm] $. Denn nur $ [mm] k_2 [/mm] $ wird später im Beweis gebraucht. Genauer wird $ [mm] 1\le k_2 \le [/mm] n $ gebraucht."
JETZT hab ich ehrlich gesagt auch erst verstanden warum du immer so derart gegeben so ein k warst und JETZT hab ich auch erst verstanden warum du vor ein paar Einträgen mal das hier geschrieben hast:
$ z = uvw = [mm] 0^{|u|} 0^{|v|} 0^m 0^{n^2} [/mm] $
Das w braucht man wohl nicht "angeben"? Das k wirklich unnütz ist und die "Variablenanzahl" aufbläht ist mir nun klar. Hier brauch ich jetzt wohl nix mehr genauer definieren, denn als was ersetzt wurde, ist ja durch das PL selber definiert, oder?
Genau das mußt Du zeigen. Es gibt ein i, so daß $ [mm] uv^iw\notin [/mm] L $. Früher hatte ich das mal mit i=2 gezeigt und in der letzten Mitteilung mit i=0. So ein i dürfte es nach dem PL nicht geben, wenn die Sprache regulär ist.
In der Mitteilung hast du das für i=0 gezeigt. Das hatte ich nicht verstanden. Jetzt ist es mir klar. Hier nochmal der Beweis für i=2:
Nach dem PL ist $uv^2w = [mm] 0^{|u|} \left(0^{|v|}\right)^2 0^m 0^{n^2} [/mm] $ nicht in L, weil $|v| [mm] \neq \epsilon$ [/mm] gefordert ist, ist $|u| + m = [mm] n^3 [/mm] - 2|v| < [mm] n^3$ [/mm] und daher ist $uv^2w$ im Widerspruch zum PL nicht in L.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:23 Di 12.06.2012 | | Autor: | Helbig |
> In der Mitteilung hast du das für i=0 gezeigt. Das hatte
> ich nicht verstanden. Jetzt ist es mir klar. Hier nochmal
> der Beweis für i=2:
>
> Nach dem PL ist [mm]uv^2w = 0^{|u|} \left(0^{|v|}\right)^2 0^m 0^{n^2}[/mm]
> nicht in L, weil [mm]|v| \neq \epsilon[/mm] gefordert ist, ist [mm]|u| + m = n^3 - 2|v| < n^3[/mm]
> und daher ist [mm]uv^2w[/mm] im Widerspruch zum PL nicht in L.
Und das stimmt nicht! Vor allem: wieso ist [mm] $|u|+m=n^3-2|v|$?
[/mm]
|
|
|
| |
|
Hm, nachdem ich mir das nun alles nochmal angeschaut, habe weiß ich ehrlich gesagt selber nicht mehr so genau was ich da geschrieben hab.
Das liegt auch daran weil ich nicht genau weiß, was das m eigentlich sein soll...
Ich hab das da jetzt eingefügt, weil du es bei dieser [mm] $0^j 1^k 0^l$ [/mm] Sprache gemacht hast und damit den Beweis richtig gemacht hast.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Fr 15.06.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
