Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:44 Di 07.05.2013 | | Autor: | bandchef |
| Aufgabe | Zeigen oder widerlegen sie, dass die folgende Sprache regulär ist:
[mm] $L_3 [/mm] = [mm] \{1^i 0^j 1^k | i,j,k \in \mathbb N, i \neq k\}$ [/mm] |
Sei $L$ eine reguläre Sprache, dann gibt es eine Konstante $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 [mm] $|uv|\leq [/mm] n$, [mm] $|v|\geq [/mm] 1$ und $u [mm] v^i [/mm] w [mm] \in [/mm] L$ für alle $i [mm] \geq [/mm] 0$ gilt:
Ich wähle nun ein Wort z in Abhängigkeit der Sprache $L$ mit [mm] $|z|\geq [/mm] n$:
$z = [mm] 1^n 0^{2n} 1^n$, [/mm] $|z| = n+2n+n = 4n [mm] \geq [/mm] n$
Da die Anzahl der 1en am Anfang des Wortes gleich der Anzahl der 1en am Ende es Wortes sein muss, lege ich $uv$ in den vorderen Wortteil:
$z = [mm] \underbrace{1^n}_{=uv} \underbrace{0^{2n} 1^n}_{=w}$
[/mm]
[mm] $\Rightarrow [/mm] z = uv^iw = uv^0w [mm] \notin [/mm] L$, da vorne nun weniger 1en als hinten.
-------------------------
Stimmt der Widerspruchsbeweis so?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:13 Mi 08.05.2013 | | Autor: | tobit09 |
Hallo bandchef,
> Zeigen oder widerlegen sie, dass die folgende Sprache
> regulär ist:
>
> [mm]L_3 = \{1^i 0^j 1^k | i,j,k \in \mathbb N, i \neq k\}[/mm]
Sorry, dass ich möglicherweise zum dritten Mal nachfrage: Ist die 0 bei euch eine natürliche Zahl?
Behauptung: $L$ ist nicht regulär.
Beweis: Angenommen, $L$ wäre regulär. Dann gäbe es eine natürliche Zahl [mm] $n\in\IN$ [/mm] mit der Eigenschaft aus dem Pumping Lemma.
> Ich wähle nun ein Wort z in Abhängigkeit der Sprache [mm]L[/mm]
> mit [mm]|z|\geq n[/mm]:
>
> [mm]z = 1^n 0^{2n} 1^n[/mm], [mm]|z| = n+2n+n = 4n \geq n[/mm]
Dieses Wort $z$ liegt nicht in $L$! Daher liefert die Eigenschaft aus dem PL für $z$ keine Aussage.
> Da die Anzahl der 1en am Anfang des Wortes gleich der
> Anzahl der 1en am Ende es Wortes sein muss,
Ungleich statt gleich meinst du?
> lege ich [mm]uv[/mm] in
> den vorderen Wortteil:
>
> [mm]z = \underbrace{1^n}_{=uv} \underbrace{0^{2n} 1^n}_{=w}[/mm]
Nein, nicht uv selbst wählen.
Wenn [mm] $z\in [/mm] L$ wäre, würde dir die Eigenschaft aus dem PL liefern, dass $z$ irgendeine Zerlegung $z=uvw$ mit den gewissen Eigenschaften hat. Aus [mm] $|uv|\le [/mm] n$ könntest du dann (wenn z mit mindestens n Einsen beginnt) FOLGERN, dass uv nur aus 1en besteht.
> [mm]\Rightarrow z = uv^iw = uv^0w \notin L[/mm], da vorne nun
> weniger 1en als hinten.
Vorne weniger 1en als hinten würde ja gerade dafür sprechen, dass das Wort in L liegt.
Schreibe nicht $z=uv^0w$. Der Buchstabe $z$ ist ja schon vergeben.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:22 Mi 08.05.2013 | | Autor: | bandchef |
> Sorry, dass ich möglicherweise zum dritten Mal nachfrage: Ist die 0 bei euch eine natürliche Zahl?
So lange von [mm] $\mathbb [/mm] N$ die Rede ist, ist die 0 nicht enthalten. Wir kennzeichnen die 0 als natürlich Zahl so: [mm] $\mathbb N_0$.
[/mm]
Ich möchte dann nochmal den Beweis machen:
Behauptung: L ist regulär.
Sei $L$ eine reguläre Sprache, dann gibt es eine Konstante $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 [mm] $|uv|\leq [/mm] n$, [mm] $|v|\geq [/mm] 1$ und $u [mm] v^i [/mm] w [mm] \in [/mm] L$ für alle $i [mm] \geq [/mm] 0$ gilt:
Ich wähle nun ein Wort z in Abhängigkeit der Sprache $L$ mit [mm] $|z|\geq [/mm] n$:
$z = [mm] 1^n 0^{2n} 1^{2n}$, [/mm] $|z| = n+2n+2n = 5n [mm] \geq [/mm] n$
Da die Anzahl der 1en am Anfang des Wortes ungleich der Anzahl der 1en am Ende es Wortes sein muss, lege ich die Schleife in den vorderen Wort-Bereich:
$z = [mm] \underbrace{1^n}_{=uv} \underbrace{0^{2n} 1^n}_{=w}$ [/mm]
-> Ich weiß, das ist immer der gleiche Fehler den ich mache. Ich wähle immer SELBST das uvw. Wie muss ich das machen, dass es passt? Ich kapier das auch nach der 100. Aufgabe noch nicht... Wie muss ich also nun das uvw wählen?
[mm] $\Rightarrow [/mm] z = uv^iw = uv^0w [mm] \notin [/mm] L$, da vorne nun weniger 1en als hinten.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:58 Do 09.05.2013 | | Autor: | tobit09 |
> Behauptung: L ist regulär.
Nein, $L$ ist nicht regulär.
> Sei [mm]L[/mm] eine reguläre Sprache, dann gibt es eine Konstante [mm]n \in \mathbb N[/mm],
> so dass sich jedes [mm]z \in L[/mm] mit [mm]|z|\geq n[/mm], so als z=uvw
> schreiben lässt, dass [mm]|uv|\leq n[/mm], [mm]|v|\geq 1[/mm] und [mm]u v^i w \in L[/mm]
> für alle [mm]i \geq 0[/mm] gilt:
>
> Ich wähle nun ein Wort z in Abhängigkeit der Sprache [mm]L[/mm]
> mit [mm]|z|\geq n[/mm]:
>
> [mm]z = 1^n 0^{2n} 1^{2n}[/mm], [mm]|z| = n+2n+2n = 5n \geq n[/mm]
Ich muss zugeben, dass ich an dieser Aufgabe auch länger zu überlegen hatte. Das Ergebnis: Wähle lieber [mm] $z=1^n0^{2n}1^{n+n!}$, [/mm] wobei $n!$ für die Fakultät von $n$ steht.
> Da die Anzahl der 1en am Anfang des Wortes ungleich der
> Anzahl der 1en am Ende es Wortes sein muss, lege ich die
> Schleife in den vorderen Wort-Bereich:
>
> [mm]z = \underbrace{1^n}_{=uv} \underbrace{0^{2n} 1^n}_{=w}[/mm]
>
> -> Ich weiß, das ist immer der gleiche Fehler den ich
> mache. Ich wähle immer SELBST das uvw. Wie muss ich das
> machen, dass es passt? Ich kapier das auch nach der 100.
> Aufgabe noch nicht... Wie muss ich also nun das uvw
> wählen?
Nun, die Bedingung aus dem PL sagt dir (alles unter der Widerspruchsannahme, dass $L$ regulär wäre), dass $z=uvw$ für gewisse Wörter $u,v,w$ mit [mm] $|uv|\le [/mm] n$ und [mm] $|v|\ge1$ [/mm] und [mm] $uv^iw\in [/mm] L$ für alle [mm] $i\in\IN_0$.
[/mm]
Wegen [mm] $1^n 0^{2n} 1^{2n}=z=uvw$ [/mm] ist $uv$ ein Anfangsstück von [mm] $1^n 0^{2n} 1^{2n}$. [/mm] Außerdem hat $uv$ Länge [mm] $\le [/mm] n$. Also besteht $uv$ nur aus 1en (aber möglicherweise nicht aus allen $n$ 1en, die am Beginn von [mm] $1^n 0^{2n} 1^{2n}$ [/mm] stehen).
Nun würde es gelten, ein [mm] $i\in\IN_0$ [/mm] zu finden mit [mm] $uv^iw\not\in [/mm] L$. Wie sieht $uv^iw$ aus?
[mm] $uv^iw=1^{|u|}1^{i*|v|}1^{n-|uv|}0^{2n}1^{2n}=1^{|u|+i*v+n-(|u|+|v|)}0^{2n}1^{2n}=1^{n+(i-1)|v|}0^{2n}1^{2n}$.
[/mm]
Dieses Wort liegt nicht in $L$ genau dann, wenn $n+(i-1)|v|=2n$.
Da haben wir leider den Salat: Unter Umständen finden wir kein $i$ mit dieser Eigenschaft.
Arbeite also wie von mir vorgeschlagen lieber mit [mm] $z=1^n0^{2n}1^{n+n!}$.
[/mm]
> [mm]\Rightarrow z = uv^iw = uv^0w \notin L[/mm], da vorne nun
> weniger 1en als hinten.
Gerade deshalb gilt [mm] $uv^0w\in [/mm] L$!
Schreibe nicht $z=uv^0w$! Es gilt [mm] $z=uvw\not=uv^0w$.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:04 Do 09.05.2013 | | Autor: | bandchef |
Auf n+n! wäre ich nie gekommen... Aber dann hier nochmal:
Behauptung: L ist nicht regulär.
Sei [mm]L[/mm] eine reguläre Sprache, dann gibt es eine Konstante [mm]n \in \mathbb N[/mm],
so dass sich jedes [mm]z \in L[/mm] mit [mm]|z|\geq n[/mm], so als z=uvw
schreiben lässt, dass [mm]|uv|\leq n[/mm], [mm]|v|\geq 1[/mm] und [mm]u v^i w \in L[/mm]
für alle [mm]i \geq 0[/mm] gilt:
Ich wähle nun ein Wort z in Abhängigkeit der Sprache [mm]L[/mm]
mit [mm]|z|\geq n[/mm]:
[mm] $z=1^n0^{2n}1^{n+n!}$
[/mm]
Nun würde es gelten, ein [mm] $i\in\IN_0$ [/mm] zu finden mit [mm] $uv^iw\not\in [/mm] L$. Wie sieht $uv^iw$ aus?
[mm] $uv^iw=1^{|u|}1^{i*|v|}1^{n-|uv|}0^{2n}1^{2n}=1^{|u|+i*v+n-(|u|+|v|)}0^{2n}1^{2n}=1^{n+(i-1)|v|}0^{2n}1^{n+n!}$. [/mm]
Dieses Wort liegt nicht in $L$ genau dann, wenn $n+(i-1)|v|=n+n!$.
Wenn ich das jetzt umforme zu [mm] $i=\frac{n!}{|v|}+1$, [/mm] wie sehe ich dann, dass es hier nun wirklich kein i gibt, dass das Wort nicht mehr passend macht?
Frage:
> Wegen [mm] $1^n 0^{2n} 1^{2n}=z=uvw$ [/mm] ist $uv$ ein Anfangsstück von [mm] $1^n 0^{2n} 1^{2n}$. [/mm] Außerdem hat $uv$ Länge [mm] $\le [/mm] n$. Also besteht $uv$ nur aus 1en
> (aber möglicherweise nicht aus allen $n$ 1en, die am Beginn von [mm] $1^n 0^{2n} 1^{2n}$ [/mm] stehen).
Du schreibst, dass wegen $|uv| [mm] \leq [/mm] n$ der Wortteil uv nur aus 1en bestehen KANN. Wie siehst du das so einfach? Ist es weil, eben die Anfangs-1en des Wortes der einzige Wortteil ist, der n als Exponenten hat? Hat man dann nicht insofern dennoch eine Aufteilung uvw vorgenommen?
Was wäre gewesen, wenn man das Wort so gewählt hätte: [mm] $1^{2n} 0^{4n} 1^{2n+n!}$?
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:31 Do 09.05.2013 | | Autor: | tobit09 |
> Behauptung: L ist nicht regulär.
>
> Sei [mm]L[/mm] eine reguläre Sprache,
Angenommen, unser $L$ wäre regulär.
> dann gibt es eine Konstante [mm]n \in \mathbb N[/mm],
> so dass sich jedes [mm]z \in L[/mm] mit [mm]|z|\geq n[/mm], so als z=uvw
> schreiben lässt, dass [mm]|uv|\leq n[/mm], [mm]|v|\geq 1[/mm] und [mm]u v^i w \in L[/mm]
> für alle [mm]i \geq 0[/mm] gilt:
>
> Ich wähle nun ein Wort z in Abhängigkeit der Sprache [mm]L[/mm]
Du meinst: "Ich wähle nun ein Wort [mm] $z\in [/mm] L$"
> mit [mm]|z|\geq n[/mm]:
>
> [mm]z=1^n0^{2n}1^{n+n!}[/mm]
Insbesondere für dieses $z$ gibt es also eine Zerlegung $z=uvw$ mit...
> Nun würde es gelten, ein [mm]i\in\IN_0[/mm] zu finden mit
> [mm]uv^iw\not\in L[/mm].
Das würde einen Widerspruch zu [mm] $uv^iw\in [/mm] L$ liefern.
> Wie sieht [mm]uv^iw[/mm] aus?
>
> [mm]uv^iw=1^{|u|}1^{i*|v|}1^{n-|uv|}0^{2n}1^{2n}=1^{|u|+i*v+n-(|u|+|v|)}0^{2n}1^{2n}=1^{n+(i-1)|v|}0^{2n}1^{n+n!}[/mm].
(Hier hast du beim Copy&Paste zweimal vergessen, das $2n$ durch $n+n!$ zu ersetzen.)
> Dieses Wort liegt nicht in [mm]L[/mm] genau dann, wenn
> [mm]n+(i-1)|v|=n+n![/mm].
>
> Wenn ich das jetzt umforme zu [mm]i=\frac{n!}{|v|}+1[/mm],
![[ok]](/images/smileys/ok.gif "[ok]") Diese Umformung ist möglich wegen [mm] $|v|\ge [/mm] 1$ und somit [mm] $|v|\not=0$. [/mm] (Sonst hättest du möglicherweise durch 0 dividiert.)
> wie sehe
> ich dann, dass es hier nun wirklich kein i gibt, dass das
> Wort nicht mehr passend macht?
Im Gegenteil: Wir suchen ja gerade ein [mm] $i\in\IN_0$ [/mm] mit [mm] $uv^iw\notin [/mm] L$ (im Widerspruch zu [mm] $uv^iw\in [/mm] L$ für alle [mm] $i\in\IN_0$).
[/mm]
Offenbar leistet nach den bisherigen Überlegungen [mm] $i=\frac{n!}{|v|}+1$ [/mm] das Gewünschte, wenn es sich dabei denn um ein Element von [mm] $\IN_0$ [/mm] handelt. Warum ist letzteres der Fall?
> Frage:
> > Wegen [mm]1^n 0^{2n} 1^{2n}=z=uvw[/mm] ist [mm]uv[/mm] ein Anfangsstück
> von [mm]1^n 0^{2n} 1^{2n}[/mm]. Außerdem hat [mm]uv[/mm] Länge [mm]\le n[/mm]. Also
> besteht [mm]uv[/mm] nur aus 1en
> > (aber möglicherweise nicht aus allen [mm]n[/mm] 1en, die am
> Beginn von [mm]1^n 0^{2n} 1^{2n}[/mm] stehen).
>
> Du schreibst, dass wegen [mm]|uv| \leq n[/mm] der Wortteil uv nur
> aus 1en bestehen KANN. Wie siehst du das so einfach?
$uv$ besteht aus den ersten $|uv|$ vielen Buchstaben von [mm] $1^n 0^{2n} 1^{2n}$. $1^n 0^{2n} 1^{2n}$ [/mm] beginnt mit $n$ vielen 1en. Da [mm] $|uv|\le [/mm] n$ sind insbesondere die ersten $|uv|$ Buchstaben von [mm] $1^n 0^{2n} 1^{2n}$ [/mm] 1en. Also besteht uv nur aus 1en.
> Ist es
> weil, eben die Anfangs-1en des Wortes der einzige Wortteil
> ist, der n als Exponenten hat?
Der Begründung kann ich nicht folgen.
> Hat man dann nicht insofern
> dennoch eine Aufteilung uvw vorgenommen?
Man hat eine beliebig vorgegebene (!) Aufteilung $z=uvw$ mit [mm] $|uv|\le [/mm] n$ und [mm] $|v|\ge [/mm] 1$ betrachtet. Man hat nicht selbst die Aufteilung $z=uvw$ gewählt.
Alles, was wir über $u,v,w$ festgestellt haben, haben wir aus $z=uvw$, [mm] $|uv|\le [/mm] n$ und [mm] $|v|\ge [/mm] 1$ gefolgert.
> Was wäre gewesen, wenn man das Wort so gewählt hätte:
> [mm]1^{2n} 0^{4n} 1^{2n+n!}[/mm]?
Probiere es mal selber aus! 
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:39 Fr 10.05.2013 | | Autor: | bandchef |
> Im Gegenteil: Wir suchen ja gerade ein [mm] $i\in\IN_0$ [/mm] mit [mm] $uv^iw\notin [/mm] L$ (im Widerspruch zu [mm] $uv^iw\in [/mm] L$ für alle [mm] $i\in\IN_0$). [/mm]
> Offenbar leistet nach den bisherigen Überlegungen [mm] $i=\frac{n!}{|v|}+1$ [/mm] das Gewünschte, wenn es sich dabei denn um ein Element
> von [mm] $\IN_0$ [/mm] handelt. Warum ist letzteres der Fall?
Warum das der Fall ist, hat mir nun endlich eingeleuchtet! Laut Sprache ist ja gefordert, dass der vordere Wortteil UNGLEICH dem hinteren Wortteil sein muss. Den Widerspruch erzeuge ich nun damit, dass die vorderen 1en bei einem bestimmten i gleich den hinteren 1en werden. Das ist gerade dann der Fall, wenn ich die Formeln der "Längenpotenzen", also die Berechnung der Länge der vorderen und hinteren 1en GLEICHSETZE und dann auf das i umforme! Wenn ich dann ein i berechne, weiß ich sofort, dass das Wort nicht in L enthalten ist und die Sprache so nicht regulär sein kann!
> $uv$ besteht aus den ersten $|uv|$ vielen Buchstaben von [mm] $1^n 0^{2n} 1^{2n}$. $1^n 0^{2n} 1^{2n}$ [/mm] beginnt mit $n$ vielen 1en. Da > [mm] $|uv|\le [/mm] n$ sind insbesondere die ersten $|uv|$ Buchstaben von [mm] $1^n 0^{2n} 1^{2n}$ [/mm] 1en. Also besteht uv nur aus 1en.
In dem Zitat oben hab ich was fett gemacht. Dazu eine Frage: Dass es keine genau Grenze gibt wie viel 1en gemeint sind, ist mir mittlerweile klar und auch nicht wichtig zu wissen. Wie aber erkenne ich, dass |uv| nur aus den (vorderen) 1en besteht und nicht auch noch zu einem Teil aus 0en?
Genau diese Frage ist wahrscheinlich auch der Grund dafür, warum du schreibst: > Der Begründung kann ich nicht folgen.
> Man hat eine beliebig vorgegebene (!) Aufteilung $z=uvw$ mit [mm] $|uv|\le [/mm] n$ und [mm] $|v|\ge [/mm] 1$ betrachtet. Man hat nicht selbst die
> Aufteilung $z=uvw$ gewählt.
Gleich Frage wie oben: Beliebig vorgegeben ist alles schön und gut und leuchtet auch soweit ein, aber WOHER weiß ich dann in diesem Beispiel, dass ich mich durch $|uv| [mm] \leq [/mm] n$ wirklich nun im vordersten Wortbereich bewege? Ist es weil diese vorderen 1en ein "n" in der Potenz haben und das $|uv| [mm] \leq [/mm] n$ sein muss?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:46 Fr 10.05.2013 | | Autor: | tobit09 |
> > Offenbar leistet nach den bisherigen Überlegungen
> [mm]i=\frac{n!}{|v|}+1[/mm] das Gewünschte, wenn es sich dabei denn
> um ein Element
> > von [mm]\IN_0[/mm] handelt. Warum ist letzteres der Fall?
Mit "letzteres" meinte ich [mm] $\frac{n!}{|v|}+1\in\IN_0$.
[/mm]
Wegen [mm] $|v|\le|uv|\le [/mm] n$ teilt $|v|$ die Zahl $n!$. Also [mm] $\frac{n!}{|v|}\in\IN_0$ [/mm] und damit auch [mm] $\frac{n!}{|v|}+1\in\IN_0$.
[/mm]
> Warum das der Fall ist, hat mir nun endlich eingeleuchtet!
> Laut Sprache ist ja gefordert, dass der vordere Wortteil
> UNGLEICH dem hinteren Wortteil sein muss. Den Widerspruch
> erzeuge ich nun damit, dass die vorderen 1en bei einem
> bestimmten i gleich den hinteren 1en werden. Das ist gerade
> dann der Fall, wenn ich die Formeln der "Längenpotenzen",
> also die Berechnung der Länge der vorderen und hinteren
> 1en GLEICHSETZE und dann auf das i umforme! Wenn ich dann
> ein i berechne, weiß ich sofort, dass das Wort nicht in L
> enthalten ist und die Sprache so nicht regulär sein kann!
OK.
> > [mm]uv[/mm] besteht aus den ersten [mm]|uv|[/mm] vielen Buchstaben von [mm]1^n 0^{2n} 1^{2n}[/mm].
> [mm]1^n 0^{2n} 1^{2n}[/mm] beginnt mit [mm]n[/mm] vielen 1en. Da > [mm]|uv|\le n[/mm]
> sind insbesondere die ersten [mm]|uv|[/mm] Buchstaben von [mm]1^n 0^{2n} 1^{2n}[/mm]
> 1en. Also besteht uv nur aus 1en.
>
> In dem Zitat oben hab ich was fett gemacht.
Ich habe vorher festgestellt:
> > [mm]uv[/mm] besteht aus den ersten [mm]|uv|[/mm] vielen Buchstaben von [mm]1^n 0^{2n} 1^{2n}[/mm].
und
> > Da [mm]|uv|\le n[/mm]
> > sind insbesondere die ersten [mm]|uv|[/mm] Buchstaben von [mm]1^n 0^{2n} 1^{2n}[/mm]
> > 1en.
Zusammengenommen ergibt sich, dass $uv$ nur aus 1en besteht.
> Dazu eine
> Frage: Dass es keine genau Grenze gibt wie viel 1en gemeint
> sind, ist mir mittlerweile klar und auch nicht wichtig zu
> wissen. Wie aber erkenne ich, dass |uv| nur aus den
> (vorderen) 1en besteht und nicht auch noch zu einem Teil
> aus 0en?
Weil die Länge von $uv$ kleiner gleich $n$ ist, kann $uv$ nicht über die ersten $n$ Zeichen von [mm] $1^{n}0^{2n}1^{n+n!}$ [/mm] "hinausreichen".
> > Man hat eine beliebig vorgegebene (!) Aufteilung [mm]z=uvw[/mm] mit
> [mm]|uv|\le n[/mm] und [mm]|v|\ge 1[/mm] betrachtet. Man hat nicht selbst
> die
> > Aufteilung [mm]z=uvw[/mm] gewählt.
>
> Gleich Frage wie oben: Beliebig vorgegeben ist alles schön
> und gut und leuchtet auch soweit ein, aber WOHER weiß ich
> dann in diesem Beispiel, dass ich mich durch [mm]|uv| \leq n[/mm]
> wirklich nun im vordersten Wortbereich bewege? Ist es weil
> diese vorderen 1en ein "n" in der Potenz haben und das [mm]|uv| \leq n[/mm]
> sein muss?
Ja. Das Wort [mm] $1^{n}0^{2n}1^{n+n!}$ [/mm] beginnt mit $n$ 1en. Jedes Anfangsstück der Länge [mm] $\le [/mm] n$ besteht also nur aus 1en. $uv$ ist ein Anfangsstück von [mm] $1^{n}0^{2n}1^{n+n!}$ [/mm] der Länge [mm] $\le [/mm] n$. Somit besteht $uv$ nur aus 1en.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:56 Fr 10.05.2013 | | Autor: | bandchef |
> Weil die Länge von $uv$ kleiner gleich $n$ ist, kann $uv$ nicht über die ersten $n$
> Zeichen von [mm] $1^{n}0^{2n}1^{n+n!}$ [/mm] "hinausreichen".
Dazu noch eine Frage: Was mir immer noch nicht ganz einleuchtet, ist, warum der $|uv|$ gerade bis maximal zur letzten 1 geht. Das |uv| könnte doch genauso gut bis irgendwo in die Mitte von 0en reichen, oder? Wer sagt mir denn, dass |uv| nicht bei der ersten 0 beginnt? Aber das darf wahrscheinlich nicht sein, weil was ist dann eben mit den 1en davor? Es ist einfach so, dass man das Wort z von links nach rechts unterteilt und dabei (anscheinend) festgelegt ist, dass uv vom ersten Zeichen (also das linkeste Zeichen) bis zu den ersten n-Zeichen gehen muss; und hier sind eben die ersten n-Zeichen gerade die Anzahl der vordersten/linkesten 1en.
Wenn der Wortteil |uv| bis irgendwo zu den 0en reichen soll, dann müsste wohl im PL $|uv| [mm] \leq [/mm] 2n$ gefordert sein, oder? Dann wäre es möglich, dass auch 0en getroffen werden.
Ich weiß natürlich, dass diese Annahme von $|uv| [mm] \leq [/mm] 2n$ falsch ist!
Weitere Frage:
Was ich aber noch immer nicht durchschaut habe, wie du auf die [mm] $1^{n+n!}$ [/mm] kommst. Das ist mir noch schleierhaft. Oder ist das die Stelle, wo du selber lange überlegen musstest, wie du in einem der ersten Posts meintest?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:44 Sa 11.05.2013 | | Autor: | tobit09 |
> > Weil die Länge von [mm]uv[/mm] kleiner gleich [mm]n[/mm] ist, kann [mm]uv[/mm] nicht
> über die ersten [mm]n[/mm]
> > Zeichen von [mm]1^{n}0^{2n}1^{n+n!}[/mm] "hinausreichen".
>
> Dazu noch eine Frage: Was mir immer noch nicht ganz
> einleuchtet, ist, warum der [mm]|uv|[/mm] gerade bis maximal zur
> letzten 1 geht.
uv, nicht |uv| (letzteres wäre die Länge von uv).
> Das |uv| könnte doch genauso gut bis
> irgendwo in die Mitte von 0en reichen, oder?
Nein.
> Wer sagt mir
> denn, dass |uv| nicht bei der ersten 0 beginnt?
Die Gleichung $z=uvw$ besagt, dass z mit uv beginnt.
> Aber das
> darf wahrscheinlich nicht sein, weil was ist dann eben mit
> den 1en davor? Es ist einfach so, dass man das Wort z von
> links nach rechts unterteilt und dabei (anscheinend)
> festgelegt ist, dass uv vom ersten Zeichen (also das
> linkeste Zeichen) bis zu den ersten n-Zeichen gehen muss;
Wegen $z=uvw$ besteht $uv$ aus den ersten $|uv|$ vielen Zeichen von $z$.
> und hier sind eben die ersten n-Zeichen gerade die Anzahl
> der vordersten/linkesten 1en.
Ja.
> Wenn der Wortteil |uv| bis irgendwo zu den 0en reichen
> soll, dann müsste wohl im PL [mm]|uv| \leq 2n[/mm] gefordert sein,
> oder? Dann wäre es möglich, dass auch 0en getroffen
> werden.
Wenn es im Pumping Lemma nur [mm] $|uv|\le [/mm] 2n$ statt [mm] $|uv|\le [/mm] n$ hieße, wäre es in der Tat möglich, dass bei unserer Wahl von $z$ das Wort $uv$ auch 0en enthält.
> Ich weiß natürlich, dass diese Annahme von [mm]|uv| \leq 2n[/mm]
> falsch ist!
(Falsch genau genommen nicht, aber zu schwach...)
> Weitere Frage:
>
> Was ich aber noch immer nicht durchschaut habe, wie du auf
> die [mm]1^{n+n!}[/mm] kommst. Das ist mir noch schleierhaft. Oder
> ist das die Stelle, wo du selber lange überlegen musstest,
> wie du in einem der ersten Posts meintest?
In der Tat.
Wenn man von einem Wort der Form [mm] $z=1^n0^{2n}1^m\in [/mm] L$ für ein [mm] $m\in\IN_0$ [/mm] ausgeht (also [mm] $m\not=n$), [/mm] wie muss $m$ aussehen, damit [mm] $uv^iw=1^m0^{2n}1^m\notin [/mm] L$ für ein [mm] $i\in\IN_0$ [/mm] für jede Zerlegung $z=uvw$ mit [mm] $|uv|\le [/mm] n$, [mm] $|v|\ge [/mm] 1$ gilt?
Wegen [mm] $uv^iw=1^{n+(i-1)*|v|}0^{2n}1^m$ [/mm] für jede solche Zerlegung, soll es also ein [mm] $i\in\IN_0$ [/mm] geben mit $n+(i-1)*|v|=m$.
$m$ soll also, egal welchen Wert $|v|$ genau hat (abgesehen davon, dass er [mm] $\le [/mm] n$ ist) die Summe aus $n$ und einem Vielfachen von $|v|$ sein.
Als Vielfaches von jeder natürlichen Zahl [mm] $\le [/mm] n$ fiel mir als erstes $n!$ ein.
So entstand die Idee, $m:=n+n!$ zu wählen.
Wichtig nach einer solchen (nicht einfachen) Überlegung ist nachzuprüfen, dass die Argumentation mit dem überlegten $z$ tatsächlich funktioniert.
|
|
|
|
