Frage zum Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:44 Di 24.01.2012 | | Autor: | bandchef |
| Aufgabe | Beweisen sie mit dem Pumping Lemma:
$L = [mm] \{1^ny | n \in \mathbb N, y \in \Sigma^\star_\text{Bool } \text{mit} |y|_1 \leq n\}$ [/mm] |
Wir haben in der Schule dieses Beispiel ausführlich gemacht. Und zwar so:
Annahme: L ist nicht regulär.
Sei [mm] $n_0 \in \mathbb [/mm] N$ und [mm] $n_0 \geq [/mm] 1$ die Konstante des PL. Wir beweisen mit PL.
Betrachte: $z= [mm] 1^{n_0} [/mm] 0 [mm] 1^{n_0}$
[/mm]
Zerlegung: [mm] $\underbrace{1^{k_1}}_{=u}\underbrace{1^{k_2}}_{=v}\underbrace{1^{k_3}01^{n_0}}_{=w}$ [/mm] mit [mm] $k_1 [/mm] + [mm] k_2 [/mm] + [mm] k_3 [/mm] = [mm] n_0$; $k_2 \geq [/mm] 1$; [mm] $k_1+k_2\leq n_0$;
[/mm]
Betrachte i=0, dann $uv^iw [mm] \notin [/mm] L$
[mm] $1^{k_1} \left(1^{k_2}\right)^0 1^{k_3} [/mm] 0 [mm] 1^{n_0} [/mm] = [mm] 1^{k_1} \left(1^{0\cdot k_2}\right) 1^{k_3} [/mm] 0 [mm] 1^{n_0} [/mm] = [mm] 1^{k_1} 1^{k_3} [/mm] 0 [mm] 1^{n_0} [/mm] = [mm] 1^{k_1+k_3} [/mm] 0 [mm] 1^{n_0}$
[/mm]
[mm] $k_1+k_3 [/mm] < [mm] n_0 \Rightarrow [/mm] uv^iw [mm] \notin [/mm] L$
Ich hab dazu jetzt schon einige Fragen:
Wie kommt man drauf, dass man $z= [mm] 1^{n_0} [/mm] 0 [mm] 1^{n_0}$ [/mm] "betrachten" muss?
Wie kommt man auf die Zerlegung?
Könnt ihr mir weiterhelfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:15 Di 24.01.2012 | | Autor: | sandp |
> Beweisen sie mit dem Pumping Lemma:
>
> [mm]L = \{1^ny | n \in \mathbb N, y \in \Sigma^\star_\text{Bool } \text{mit} |y|_1 \leq n\}[/mm]
>
> Wir haben in der Schule dieses Beispiel ausführlich
> gemacht. Und zwar so:
>
>
> Annahme: L ist nicht regulär.
> Sei [mm]n_0 \in \mathbb N[/mm] und [mm]n_0 \geq 1[/mm] die Konstante des PL.
> Wir beweisen mit PL.
>
> Betrachte: [mm]z= 1^{n_0} 0 1^{n_0}[/mm]
>
> Zerlegung:
> [mm]\underbrace{1^{k_1}}_{=u}\underbrace{1^{k_2}}_{=v}\underbrace{1^{k_3}}_{=w}01^{n_0}[/mm]
> mit [mm]k_1 + k_2 + k_3 = n_0[/mm]; [mm]k_2 \geq 1[/mm]; [mm]k_1+k_2\leq n_0[/mm];
>
>
> Betrachte i=0, dann [mm]uv^iw \notin L[/mm]
>
> [mm]1^{k_1} \left(1^{k_2}\right)^0 1^{k_3} 0 1^{n_0} = 1^{k_1} \left(1^{0\cdot k_2}\right) 1^{k_3} 0 1^{n_0} = 1^{k_1} 1^{k_3} 0 1^{n_0} = 1^{k_1+k_3} 0 1^{n_0}[/mm]
>
> [mm]k_1+k_3 < n_0 \Rightarrow uv^iw \notin L[/mm]
>
>
> Ich hab dazu jetzt schon einige Fragen:
>
> Wie kommt man drauf, dass man [mm]z= 1^{n_0} 0 1^{n_0}[/mm]
> "betrachten" muss?
Hallo,
zu allererst musst du dir Gedanken machen, wie die Sprache überhaupt aussieht.
In deiner Sprache ist gefordert, dass [mm] |y|_1 \leq [/mm] n das ist hier das Entscheidende.
Was beudeutet das?
Was musst du jetzt mit dem Pumping Lemma machen, damit diese Bedingung nichtmehr stimmt, weil genau dann hast du gezeigt, dass die Sprache nicht regulär ist.
Wenn du das weißt, dann kommen wir zur Zerlegung.
Gruß sandp
> Wie kommt man auf die Zerlegung?
>
>
> Könnt ihr mir weiterhelfen?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:27 Di 24.01.2012 | | Autor: | bandchef |
Erstmal noch grundsätzlich:
[mm] $1^n$ [/mm] sagt doch aus, dass das so viel 1en im Wort kommen wie man in n einsetzt. Das heißt: Wenn [mm] $1^6$ [/mm] dastehen würde, dann kämen am Anfang des Wortes 6 1en, oder? Die nachfolgende 1er-Kette (was ja das y symbolisiert) soll dann kleinergleich dem n sein, dass man vorher hatte, oder? Also alles kleiner gleich sechs 1en. Somit akzeptiert die Sprache bspw. 12x die 1; oder 10x die 1, nicht wahr?
Das $ [mm] |y|_1 \leq [/mm] n$ bedeutet, dass die Wortlänge der 1er kleinergleich n sein soll. Wobei n auch der Exponent ist und n aus dem Zahlenraum der natürlichen Zahlen kommt.
Ich denke mal, dass das soweit richtig sein sollte, oder?
Nun sagst du, ich muss mit dem PL an dieser Bedingung spielen, dass diese nicht mehr stimmt. Das ist jetzt schon irgendwie schwierig für mich. Was kann ich da tun?
Wenn ich den Exponenten [mm] $1^n$ [/mm] zu n+1 ändere, dann passiert doch nix, oder? Wortlänge von y kann ja immer noch kleinergleich n sein/werden.
Oder: Vielleicht muss man bei der eigentlich Sprachangabe y+1 schreiben. Dann wäre die Wortlänge von y eins größer als n und die Sprache stimmt nicht mehr.
Das wären jetzt meine zwei Versuche mal zu Versuchen was du mir geraten hast.
Hm, mehr kann ich dazu leider jetzt nicht mehr liefern.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:08 Di 24.01.2012 | | Autor: | sandp |
> Erstmal noch grundsätzlich:
>
> [mm]1^n[/mm] sagt doch aus, dass das so viel 1en im Wort kommen wie
> man in n einsetzt. Das heißt: Wenn [mm]1^6[/mm] dastehen würde,
> dann kämen am Anfang des Wortes 6 1en, oder? Die
> nachfolgende 1er-Kette (was ja das y symbolisiert) soll
> dann kleinergleich dem n sein, dass man vorher hatte, oder?
> Also alles kleiner gleich sechs 1en. Somit akzeptiert die
> Sprache bspw. 12x die 1; oder 10x die 1, nicht wahr?
>
ja genau, nur du musst beachten im y dürfen auch 0en vorkommen, weil du ja das Alphabet [mm] \Sigma^\star_\text{Bool } [/mm] hast aber sonst hast du recht die Anzahl der 1en im y muss kleiner gleich der Anzahl der 1en am Anfang des Wortes sein.
>
> Das [mm]|y|_1 \leq n[/mm] bedeutet, dass die Wortlänge der 1er
> kleinergleich n sein soll. Wobei n auch der Exponent ist
> und n aus dem Zahlenraum der natürlichen Zahlen kommt.
>
[mm]|y|_1 \leq n[/mm] sagt nur, dass die Anzahl der 1en am Anfang des Wortes größer oder gleich der Anzahl der 1en im y sein muss, über die Wortlänge kannst du direkt nichts sagen, weil du nicht weißt wie viele 0en im y stecken und das könnten ja sehr viele sein.
> Ich denke mal, dass das soweit richtig sein sollte, oder?
ja
>
>
> Nun sagst du, ich muss mit dem PL an dieser Bedingung
> spielen, dass diese nicht mehr stimmt. Das ist jetzt schon
> irgendwie schwierig für mich. Was kann ich da tun?
> Wenn ich den Exponenten [mm]1^n[/mm] zu n+1 ändere, dann passiert
> doch nix, oder? Wortlänge von y kann ja immer noch
> kleinergleich n sein/werden.
> Oder: Vielleicht muss man bei der eigentlich Sprachangabe
> y+1 schreiben. Dann wäre die Wortlänge von y eins
> größer als n und die Sprache stimmt nicht mehr.
>
> Das wären jetzt meine zwei Versuche mal zu Versuchen was
> du mir geraten hast.
>
>
> Hm, mehr kann ich dazu leider jetzt nicht mehr liefern.
Ok vergiss deine Versuche. Du musst ganz anders an die Sache rangehen.
Die Bedingung ist: Mehr 1en am Anfang als 1en im y.
also müssen wir mit dem Pumping Lemma irgendwie mehr 1en in das y bekommen oder wir müssen am Anfang des Wortes 1en wegnehmen.
Ihr habt die 2te Variante gewählt und am Anfang des Wortes die 1en abgepumpt.
Das Prinzip des PL ist dir klar? Bedingungen wie du es anwendest usw?
Wie musst du also dein Wort in die Form uvw reinpacken um die 1en am Anfang wegzupumpen?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:41 Di 24.01.2012 | | Autor: | bandchef |
Das Prinzip des PL ist dir klar? Bedingungen wie du es anwendest usw?
-> Bei manchen Aufgaben ja, aber meistens eher nicht. Hier leider auch nicht.
Wie musst du also dein Wort in die Form uvw reinpacken um die 1en am Anfang wegzupumpen?
-> Dementsprechen hab ich keine Ahnung :-(
Ein Prinzip ist aber doch, dass man den Mittelteil pumpt mit so einem hochgestellten i: $uv^iw$. Also muss ich erst mal das $1^ny$ irgendwie in uvw aufteilen. Das ist jetzt schon mal die erste Hürde. Ich weiß, dass ich zum Widerlegen der Sprache das y größer machen muss bzw. das [mm] $1^n$ [/mm] kleiner. Soweit ist mir das jetzt klar. Wie aber zerlege ich das nun, dass ich dann ab/aufpumpen genau das machen kann damit ich aus der Sprache rausfliege?
Ich hab mir jetzt die Lösung aus der Schule nochmal angesehen. Ich versteh da zwei Dinge gar nicht.
1. Warum darf man $1^ny$ in [mm] $1^{n_0}01^{n_0}$ [/mm] zerlegen; besser gesagt wo kommt die 0 in der Mitt her? Die zwei [mm] $1^{n_0}$ [/mm] leuchten ja irgendwie ein, das erste [mm] $1^{n_0}$ [/mm] mit dem [mm] $1^n$ [/mm] übereinstimmt und das zweite [mm] $1^{n_0}$ [/mm] mit dem y was man ja ersetzen darf, weil es in der Bedingung ja heißt: $|y| [mm] \leq n_0$.
[/mm]
2. Warum gilt ganz am Schluss der Zusammenhang: [mm] $k_1+k_3 [/mm] < [mm] n_0$? [/mm] Woher weiß man das dann? Das [mm] $k_1+k_2 \leq n_0$ [/mm] ist, ist klar, denn das Definiert ja das PL!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:18 Di 24.01.2012 | | Autor: | sandp |
> Das Prinzip des PL ist dir klar? Bedingungen wie du es
> anwendest usw?
>
> -> Bei manchen Aufgaben ja, aber meistens eher nicht. Hier
> leider auch nicht.
Funktioniert immer nach dem gleichen Prinzip, wenn du diese Aufgabe verstanden hast, probiere es immer auf dem gleichen Weg zu lösen
>
>
> Wie musst du also dein Wort in die Form uvw reinpacken um
> die 1en am Anfang wegzupumpen?
>
> -> Dementsprechen hab ich keine Ahnung :-(
>
>
>
> Ein Prinzip ist aber doch, dass man den Mittelteil pumpt
> mit so einem hochgestellten i: [mm]uv^iw[/mm]. Also muss ich erst
> mal das [mm]1^ny[/mm] irgendwie in uvw aufteilen. Das ist jetzt
> schon mal die erste Hürde. Ich weiß, dass ich zum
> Widerlegen der Sprache das y größer machen muss bzw. das
> [mm]1^n[/mm] kleiner. Soweit ist mir das jetzt klar. Wie aber
> zerlege ich das nun, dass ich dann ab/aufpumpen genau das
> machen kann damit ich aus der Sprache rausfliege?
>
>
> Ich hab mir jetzt die Lösung aus der Schule nochmal
> angesehen. Ich versteh da zwei Dinge gar nicht.
>
ok also, das PL funkioniert immer nach dem gleichen Prinzip:
fangen wir mal an mit dem Satz des PL:
für alle x [mm] \in [/mm] L gibt es ein n [mm] \in \IN [/mm] sodass gilt: |x| [mm] \ge [/mm] n
dann gibt es uvw=x, also eine Zerlegung von x
für diese Zerlegung muss gelten:
1.) [mm] |v|\ge [/mm] 1
2.) |uv| [mm] \le [/mm] n
3.) [mm] uv^{i}w \in [/mm] L für alle [mm] i\ge [/mm] 0
und im 3ten Schritt wählen wir immer ein i, sodass [mm] uv^{i}w \not\in [/mm] L weil daraus folgt dann, dass die Sprache nicht regulär ist.
so also fangen wir an unser x [mm] \in [/mm] L zu wählen
bei euch wurde jetzt das gewählt: [mm]1^{n_0}01^{n_0}[/mm]
warum wurde das gewählt?
also wir haben schon die Idee um die 1en am Anfang abzupumpen,
für [mm] n_{0}\in \IN [/mm] haben wir jetzt ein festes n, das setzen wir schonmal ein, daher haben wir [mm] 1^{n_{0}}y, [/mm] jetzt müssen wir noch das y bestimmen, da wählen wir jetzt einfach genau gleich viele 1en wie im Anfang des Wortes und wie gesagt darf y aus 0en und 1en bestehen und über die Anzahl der 0en haben wir keine Angaben, dürfen also so viele reinpacken wie wir wollen
ihr habt jetzt eine Null reingepackt: [mm]1^{n_0}01^{n_0}[/mm]
genau so dürfte man dies hier verwenden : [mm]1^{n_0}1^{n_0}[/mm]
oder das: [mm]1^{n_0}00001^{n_0}000[/mm]
hauptsache die Wörter liegen in unserer Sprache
ok jetzt wählen wir unsere Zerlegung uvw
wir müssen schauen, dass in uv nur 1en sind, weil wir wollen das später wegpumpen
daher wählt man die Zerlegung: $ [mm] \underbrace{1^{k_1}}_{=u}\underbrace{1^{k_2}}_{=v}\underbrace{1^{k_3}01^{n_0}}_{=w} [/mm] $ mit $ [mm] k_1 [/mm] + [mm] k_2 [/mm] + [mm] k_3 [/mm] = [mm] n_0 [/mm] $; $ [mm] k_2 \geq [/mm] 1 $; $ [mm] k_1+k_2\leq n_0 [/mm] $;
diese Bedingungen für die k wählt man für sie, damit die Bedingungen 1.) und 2.) gelten
mit [mm] k_2 \geq [/mm] 1 geht man sicher, dass 1.) gilt
und mit [mm] k_1+k_2\leq n_0 [/mm] geht man sicher, dass 2.) gilt
jetzt sind in uv nur noch 1en also können wir i=0 wählen, daraus folgt dann [mm] uv^{i}w=uv^0w=uw [/mm] da 1.) gilt war v nicht leer und somit hat man mindestens eine 1 abgepumpt, daher hat man vorne jetzt eine 1 weniger als hinten und daher ist dieses Wort nicht in L, damit haben wir bewiesen, dass die Sprache nicht regulär ist.
Ich hoffe es wurde jetzt verständlicher
>
>
> 1. Warum darf man [mm]1^ny[/mm] in [mm]1^{n_0}01^{n_0}[/mm] zerlegen; besser
> gesagt wo kommt die 0 in der Mitt her? Die zwei [mm]1^{n_0}[/mm]
> leuchten ja irgendwie ein, das erste [mm]1^{n_0}[/mm] mit dem [mm]1^n[/mm]
> übereinstimmt und das zweite [mm]1^{n_0}[/mm] mit dem y was man ja
> ersetzen darf, weil es in der Bedingung ja heißt: [mm]|y| \leq n_0[/mm].
>
> 2. Warum gilt ganz am Schluss der Zusammenhang: [mm]k_1+k_3 < n_0[/mm]?
> Woher weiß man das dann? Das [mm]k_1+k_2 \leq n_0[/mm] ist, ist
> klar, denn das Definiert ja das PL!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:22 Mi 25.01.2012 | | Autor: | bandchef |
Erstmal ein großes Dankeschön an dich, dass du dir so viel Zeit nimmst und mir das PL erklärt hast.
Noch eine Frage zu deiner letzten Ausführlichen Erklärung:
Bei der Zerlegung wählt man ja diese Bedingungen der k's so, dass sie mit den Bedingungen des PL übereinstimmen. Wo aber finde ich denn im PL die Bedingung, dass [mm] $k_1+k_2+k_3=n_0$ [/mm] sein muss, bzw. da ich diese Bedingung im PL nicht finde, woher weiß ich dann, dass man [mm] $k_1+k_2+k_3=n_0$ [/mm] schreiben muss? Kommt das daher weil man quasi den Exponenten von [mm] $1^{n_0}$ [/mm] in [mm] $k_1+k_2+k_3$ [/mm] zerlegt und deswegen gleich dem Exponenten, also [mm] $=n_0$, [/mm] sein muss?
Des Weiteren schreibst du in deiner Erklärung, dass [mm] $k_1+k_2 \leq n_0$; [/mm] das korreliert ja mit der 2. Bedingung des PL. Legt man also in den Bedingungen des PL schon fest ob man auf- oder abpumpt?
-> Macht das [mm] $\leq$ [/mm] nun die Aussage des "abpumpens"? Andersrum: Wenn man [mm] $\geq$ [/mm] schreiben würde, würde man dann aufpumpen? Muss man also in den Bedingungen des PL vorher schon festlegen ob man auf oder abpumpen will?
Aber ich denke, dass ich das ür diese Sprache jetzt soweit mal verstanden hab.
Ich hab hier noch eine Sprache gefunden auf die man das PL anwenden soll: [mm] $L=\{0^i^3 | i \in \mathbb N \}$
[/mm]
Ich tipp meine Lösung jetzt nicht in LaTeX hier ab sondern hab dir von meiner Papierlösung ein Bild gemacht; zu finden hier: http://imageshack.us/photo/my-images/21/32206067.jpg/ Wär nett wenn du mir sagen könntest, ob das stimmt / ob man das so machen darf! Danke!
Jetzt muss ich das PL halt noch üben. Hast du da ähnliche Sprachen? Zu der du mir evtl. kleine Hilfestellungen bzw. das Ergebnis posten könntest?
Das wär sehr nett!
Danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:18 Mi 25.01.2012 | | Autor: | sandp |
> Erstmal ein großes Dankeschön an dich, dass du dir so
> viel Zeit nimmst und mir das PL erklärt hast.
>
kein Problem
> Noch eine Frage zu deiner letzten Ausführlichen
> Erklärung:
> Bei der Zerlegung wählt man ja diese Bedingungen der k's
> so, dass sie mit den Bedingungen des PL übereinstimmen. Wo
> aber finde ich denn im PL die Bedingung, dass
> [mm]k_1+k_2+k_3=n_0[/mm] sein muss, bzw. da ich diese Bedingung im
> PL nicht finde, woher weiß ich dann, dass man
> [mm]k_1+k_2+k_3=n_0[/mm] schreiben muss? Kommt das daher weil man
> quasi den Exponenten von [mm]1^{n_0}[/mm] in [mm]k_1+k_2+k_3[/mm] zerlegt und
> deswegen gleich dem Exponenten, also [mm]=n_0[/mm], sein muss?
>
ja genau
> Des Weiteren schreibst du in deiner Erklärung, dass
> [mm]k_1+k_2 \leq n_0[/mm]; das korreliert ja mit der 2. Bedingung
> des PL. Legt man also in den Bedingungen des PL schon fest
> ob man auf- oder abpumpt?
> -> Macht das [mm]\leq[/mm] nun die Aussage des "abpumpens"?
> Andersrum: Wenn man [mm]\geq[/mm] schreiben würde, würde man dann
> aufpumpen? Muss man also in den Bedingungen des PL vorher
> schon festlegen ob man auf oder abpumpen will?
>
nein die Bedingungen sind immer die Gleichen.
das ab- bzw. aufpumpen machst du mit Hilfe des Exponenten i
wenn du i=1 wählst uv^1w=uvw dann hast du genau dein Wort, welches du gewählt hast
wenn du i=0 wählst dann pumpst du ab [mm] uv^{0}w=uw
[/mm]
und wenn du i=2wählst dann pumpst du auf [mm] uv^{2}w=uvvw
[/mm]
du kannst natürlich auch i [mm] \ge [/mm] 2 wählen um aufzupumpen, das ist aber nur sehr selten nötig
> Aber ich denke, dass ich das ür diese Sprache jetzt soweit
> mal verstanden hab.
>
>
>
>
> Ich hab hier noch eine Sprache gefunden auf die man das PL
> anwenden soll: [mm]L=\{0^i^3 | i \in \mathbb N \}[/mm]
>
> Ich tipp meine Lösung jetzt nicht in LaTeX hier ab sondern
> hab dir von meiner Papierlösung ein Bild gemacht; zu
> finden hier:
> http://imageshack.us/photo/my-images/21/32206067.jpg/ Wär
> nett wenn du mir sagen könntest, ob das stimmt / ob man
> das so machen darf! Danke!
>
Das stimmt leider so nicht, weil es könnte der Fall eintreten, dass [mm] k_{2} [/mm] ein Vielfaches von [mm] i^{3} [/mm] ist, überleg dir mal was das bedeuten würde?
Bei dieser Aufgabe musst du aufpumpen (zumindest sehe ich gerade keine Möglichkeit mit abpumpen an das Ziel zu kommen).
Wenn du aufgepumpt hast musst du eine Abschätzung machen. D.h. du musst zeigen dass gilt : [mm] n^{3}< |uv^{2}w| <(n+1)^{3}
[/mm]
>
>
>
> Jetzt muss ich das PL halt noch üben. Hast du da ähnliche
> Sprachen? Zu der du mir evtl. kleine Hilfestellungen bzw.
> das Ergebnis posten könntest?
>
Hier hast du noch 2 Beispiele:
1: [mm] L_{1}={a^{m}b^{m}|m\ge 1}
[/mm]
2: [mm] L_{2}={0^{p}|p ist Primzahl}
[/mm]
probier dich einfach ersteinmal selbst daran
> Das wär sehr nett!
>
> Danke!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:37 Fr 27.01.2012 | | Autor: | bandchef |
Zitat: "Das stimmt leider so nicht, weil es könnte der Fall eintreten, dass $ [mm] k_{2} [/mm] $ ein Vielfaches von $ [mm] i^{3} [/mm] $ ist, überleg dir mal was das bedeuten würde?"
Ehrlich gesagt weiß ich nicht, was du damit meinst. Was ein Vielfaches ist, ist mir natürlich klar. Die Sprache ist doch so aufgebaut: Wenn nun i=2 ist, dann bekomm ich acht 0en. Wenn i=3 ist, bekomm ich 27 0en. Wenn ich nun den Exponenten der Sprache auf drei "Teil"-Exponenten aufteile, wie bspw. [mm] $k_1+k_2+k_3$ [/mm] und dann hier k2 auf 0 setze dann gilt [mm] $k_1+k_2
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:30 Sa 28.01.2012 | | Autor: | sandp |
> Zitat: "Das stimmt leider so nicht, weil es könnte der
> Fall eintreten, dass [mm]k_{2}[/mm] ein Vielfaches von [mm]i^{3}[/mm] ist,
> überleg dir mal was das bedeuten würde?"
>
> Ehrlich gesagt weiß ich nicht, was du damit meinst. Was
> ein Vielfaches ist, ist mir natürlich klar. Die Sprache
> ist doch so aufgebaut: Wenn nun i=2 ist, dann bekomm ich
> acht 0en. Wenn i=3 ist, bekomm ich 27 0en. Wenn ich nun den
> Exponenten der Sprache auf drei "Teil"-Exponenten aufteile,
> wie bspw. [mm]k_1+k_2+k_3[/mm] und dann hier k2 auf 0 setze dann
k2 auf 0 setzen? dein k2 muss auf alle fälle [mm] \ge [/mm] 1 sein, da du sonst gegen Bedingung 1) verstoßen würdest, du kannst höchstens mit i(vom PL) = 0 das k2 wegpumpen, falls du das meintest
> gilt [mm]k_1+k_2
> bin aus der Sprache rausgeflogen, oder? Das ist doch
> richtig soweit, oder? Deswegen verstehe ich nicht was daran
> falsch sein soll.
$ [mm] L=\{0^i^{3} | i \in \mathbb N \} [/mm] $
ok ich zeig dir dein Denkfehler:
gehen wir davon aus du hast das Wort i=2 mit 8 0en.
Jetzt pumpst du das k2(entspricht ja dem v Teil deines Wortes) weg, wir wissen über das v, es darf nicht leer sein, also muss mindestens eine 0 in v vorkommen, aber falls k2=7 dann würden in v sieben 0en vorkommen, also hast du sieben 0en weggepumpt.
Also hätte dein Wort jetzt nur noch eine 0 und dieses Wort liegt immernoch in deiner Sprache.
Somit hast du mit dem PL kein Widerspruch erzeugt.
|
|
|
|
