Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:32 Do 24.05.2012 | | Autor: | bandchef |
Hi Leute!
Ich muss eine Vorlesung zu Theoretischer Informatik machen und hab riesige Probleme beim Pumping Lemma. Ich kann nun schon fast diesbezüglich, dass ganze Skript auswendig, hab auch schon den Hopcroft (Standardliteratur in diesem Gebiet!) zu diesem Thema gewälzt, aber bei Aufgaben häng ich immer noch in der Luft.
Ich hab natürlich erst im Informatik Subforum gepostet, nur leider hat mir da niemand so richtig geantwortet, was denn nun bei der Berechnung falsch gelaufen oder richtig gelaufen ist.
Da das Thema der Mathematik besser gesagt, der Mengenlehre nicht ganz fremd ist, hab ich mir gedacht, ich probiers hier mal.
Also wie funktioniert, das nun richtig?
Ich hoffe ihr könnt mir weiterhelfen! Danke!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:52 Do 24.05.2012 | | Autor: | Blech |
Hi,
die Idee ist, daß Du p+1 Schritte bei einem Automaten durchführst, der nur p Zustände kennt. Also wird mindestens 1 Zustand mehr als einmal auftreten. Was auch immer zwischen den beiden Zeitpunkten passiert ist, kannst Du entweder weglassen oder beliebig oft wiederholen, weil es Dich ja wieder in den gleichen Zustand zurückführt.
> Ich muss eine Vorlesung zu Theoretischer Informatik machen und hab riesige Probleme beim Pumping Lemma. Ich kann nun schon fast diesbezüglich, dass ganze Skript auswendig, hab auch schon den Hopcroft (Standardliteratur in diesem Gebiet!) zu diesem Thema gewälzt, aber bei Aufgaben häng ich immer noch in der Luft.
Wenn Du die Idee verstanden hast, aber Dir die Anwendung schwerfällt, dann ist es schwer Dir zu helfen, wenn Du nur das topic, aber keine speziellen Aufgaben postest. =)
ciao
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:52 So 27.05.2012 | | Autor: | bandchef |
| Aufgabe | Beweisen oder widerlegen Sie, dass die folgenden Sprachen regulär sind:
a) [mm] $L_1 [/mm] = [mm] \{ 0^j 1^k 0^l | j=k+l \text{für } j,k,l \in \mathbb N \}$
[/mm]
b) [mm] $L_2 [/mm] = [mm] \{ 0^{i^3+i^2} | i\in \mathbb N \} [/mm] |
Also, erstmal danke für deine Antwort. Bei diesem Thema ist nämlich generell schwierig überhaupt unterstützung zu diesem Tehma zu finden. Ich lese momentan den Hopcroft (Standardliteratur). Außerdem hab ich mich schon ziemlich lange mit diesem Thema beschäftigt. Ich denke, so das grundsätzliche am PL hab ich verstanden. Ich hab nun eben nur Probleme bei der Anwendung. Ich hab hier nun eine Aufgabe die ich mit dem PL lösen soll.
Ich hab hier nun für a) schon mal angefangen:
Bevor man mit dem PL beginnt, muss man eine Annahme darüber treffen ob die Sprache regulär ist oder nicht, dass man mit dem PL bestätigt, oder widerlegt. Deshalb:
Annahme: L ist regulär.
Sei [mm] n_0 [/mm] die Konstante des PL, dann gilt: [mm] $n_o \in \mathbb [/mm] N$, [mm] $n_0 \geq [/mm] 1$
Nun muss man die Sprache irgendwie mit dem PL-Konstante ausdrücken. Da hakts dann schon. Ich verstehe die Sprache so: die gesamte Anzahl der 1en und der 0en an der letzten Stelle ergibt die gesamte Anzahl der 0en an der ersten Stelle im Wort. Stimmt doch soweit. Wenn ich jetzt bspw. k=3 und l=4 wähle sieht ein mögliches Wort, dass in der Sprache [mm] $L_1$ [/mm] liegt wie folgt aus: 00000001110000. Das wäre jetzt ein Wort das in der Sprache liegt.
Wenn man das dann hat, muss man die Sprache in $uv^iw$ zerlegen. Mit einer passenden Wahl von i kann man dann widerlegen, dass die Sprache regulär ist, wenn durch das "pumpen" ein Wort rauskommt, welches nicht mehr in der Sprache [mm] $L_1$ [/mm] liegt. Somit hätte man mit "Beweis durch Gegenbeispiel" gezeigt, dass die Sprache [mm] $L_1$ [/mm] nicht regulär ist, was heißt, dass man für jedes mögliche Wort aus der Sprache [mm] $L_1$ [/mm] einen Automaten zeichenn kann. Das sollte doch soweit auch stimmen, oder?
Weiter bin ich leider nicht gekommen. Ich hoffe ihr (du) kannst mir nun weiterhelfen...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:21 Di 29.05.2012 | | Autor: | Helbig |
Hallo,
Ich denke, wir Mathematiker können hier helfen.
Um mit dem Pumpinglemma zu zeigen, daß $L$ nicht regulär ist, mußt du ein Wort der Form [mm] $uvw\in [/mm] L$ finden, so daß [mm] $|uv|\ge n_0$ [/mm] und [mm] $uv^iw\notin [/mm] L$ für ein [mm] $i\in\IN$, $i\ge [/mm] 1$. Achtung falsch!
Für [mm] $L_1$ [/mm] wäre das z. B. [mm] $u=0^{n_0+1},\; v=1,\; w=0^{n_0},\; [/mm] i=2$.
[mm] $L_2$ [/mm] ist auch nicht regulär. Schaffst Du den Beweis?
viel Erfolg,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:46 Di 29.05.2012 | | Autor: | bandchef |
Gehe ich richtig in der Annahme, dass man mit dem PL nur zeigen kann, dass die Sprache nicht regulär ist? Was ich damit sagen will, ist, dass man mit dem PL immer darauf hinarbeiten muss, dass man aus der Sprache rausfliegt? Ist das richtig so?
Hier nochmal kurz der Beweis für [mm] L_1:
[/mm]
Annahme: [mm] L_1 [/mm] ist regulär.
Sei $ [mm] n_0 [/mm] $ die Konstante des PL, dann gilt: $ [mm] n_o \in \mathbb [/mm] N $, $ [mm] n_0 \geq [/mm] 1 $
$ [mm] u=0^{n_0+1},\; v=1,\; w=0^{n_0},\; [/mm] i=2 $.
z = [mm] 0^{n_0+1} \text{ } 1^i \text{ } 0^{n_0} [/mm] mit i=2: $uv^2w = z = [mm] 0^{n_0+1} 1^2 0^{n_0}$ [/mm] Soweit sollte das doch passen. Wenn ich mir nun die Zeichenreihe aufschreiben möchte die da rauskommt (damit ich vergleichen kann, dass die wirklich nicht mehr in der Sprache liegt...), muss ich ja [mm] $n_0$ [/mm] einen Wert einsetzen, damit ich weiß wieviel 0en vorne und wieviel 0en ich hinten schreiben muss. Die Anzahl der 1en in der Mitte ist ja klar. Die hab ich auf 2 gepumpt. Was muss ich nun für [mm] "n_0" [/mm] einsetzen? Und wie hängt das dann mit dem geforderten j = k + l aus der Sprache zusammen?
Bei manchen Aufgaben haben wir dann auch desöfteren aufgeschrieben, dass man diese [mm] n_0 [/mm] in k's aufteilen soll/kann/muss. Wir haben dann immer noch eine zusätzliche Bedingung bei einer "Zerlegung" aufgeschrieben, die so aussieht: [mm] $n_0 [/mm] = [mm] k_1 [/mm] + [mm] k_2 [/mm] + [mm] k_3$ [/mm] Kannst du mir das erklären?
Hier zur Sprache [mm] L_2:
[/mm]
Annahme: [mm] L_2 [/mm] ist regulär.
Sei $ [mm] n_0 [/mm] $ die Konstante des PL, dann gilt: $ [mm] n_o \in \mathbb [/mm] N $, $ [mm] n_0 \geq [/mm] 1 $
$z = [mm] 0^{i^3 + i^2} [/mm] = [mm] {0^i}^3 {0^i}^2 [/mm] = [mm] 0^{n_0^3} 0^{n_0^2}$
[/mm]
Nun möchte ich $uv^iw$ betrachten. Nur hab ich hier nun das Problem, dass ich nicht weiß wie ich [mm] 0^{n_0^3} 0^{n_0^2} [/mm] in uvw unterteilen soll. Ich hab ja auch nur 2 Teile.
Könnt ihr mir helfen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:07 Di 29.05.2012 | | Autor: | Helbig |
> Gehe ich richtig in der Annahme, dass man mit dem PL nur
> zeigen kann, dass die Sprache nicht regulär ist? Was ich
> damit sagen will, ist, dass man mit dem PL immer darauf
> hinarbeiten muss, dass man aus der Sprache rausfliegt? Ist
> das richtig so?
Ja. Das PL sagt aus, daß jede reguläre Sprache eine bestimmte Eigenschaft hat.
Und wenn jetzt eine vorgelegte Sprache nicht diese Eigenschaft hat, kann sie nicht regulär sein.
Wenn dagegen eine Sprache die Eigenschaft hat, heißt das noch lange nicht, daß sie auch regulär sein muß. Um die Regularität der Sprache zu beweisen, gibt man im allgemeinen einen endlichen Automaten an, der die Sprache akzeptiert.
>
>
> Hier nochmal kurz der Beweis für [mm]L_1:[/mm]
>
> Annahme: [mm]L_1[/mm] ist regulär.
>
> Sei [mm]n_0[/mm] die Konstante des PL, dann gilt: [mm]n_o \in \mathbb N [/mm],
> [mm]n_0 \geq 1[/mm]
>
> [mm]u=0^{n_0+1},\; v=1,\; w=0^{n_0},\; i=2 [/mm].
Das heißt, [mm] $uvw\in L_1$ [/mm] und $uv$ hat eine Länge von mindestens [mm] $n_0$.
[/mm]
>
> z = [mm]0^{n_0+1} \text{ } 1^i \text{ } 0^{n_0}[/mm] mit i=2:
> [mm]uv^2w = z = 0^{n_0+1} 1^2 0^{n_0}[/mm]
Dann muß nach dem PL auch $z$ in [mm] $L_1$ [/mm] sein, was aber nicht der Fall ist.
Soweit sollte das doch
> passen. Wenn ich mir nun die Zeichenreihe aufschreiben
> möchte die da rauskommt (damit ich vergleichen kann, dass
> die wirklich nicht mehr in der Sprache liegt...), muss ich
> ja [mm]n_0[/mm] einen Wert einsetzen, damit ich weiß wieviel 0en
> vorne und wieviel 0en ich hinten schreiben muss. Die Anzahl
> der 1en in der Mitte ist ja klar. Die hab ich auf 2
> gepumpt. Was muss ich nun für [mm]"n_0"[/mm] einsetzen? Und wie
> hängt das dann mit dem geforderten j = k + l aus der
> Sprache zusammen?
Nun, in $z$ ist nicht in der Sprache, weil [mm] $n_0+1 \ne [/mm] 2 + [mm] n_0$ [/mm] ist. Da muß man für [mm] $n_0$ [/mm] nichts einsetzen, dies muß für jedes [mm] $n_0$ [/mm] gelten.
>
> Bei manchen Aufgaben haben wir dann auch desöfteren
> aufgeschrieben, dass man diese [mm]n_0[/mm] in k's aufteilen
> soll/kann/muss. Wir haben dann immer noch eine zusätzliche
> Bedingung bei einer "Zerlegung" aufgeschrieben, die so
> aussieht: [mm]n_0 = k_1 + k_2 + k_3[/mm] Kannst du mir das
> erklären?
Dies macht man, um das Gegenbeispiel zu beschreiben.
Für [mm] $L_2$ [/mm] könnte man [mm] $u=0^{n_0^3}, v=0^{n_0^2}, w=\epsilon$ [/mm] setzen. Dann ist [mm] $|uv|>n_0$ [/mm] und [mm] $uvw\in L_2$. [/mm] Jetzt muß Du ein $i$ finden, so daß [mm] $uv^iw\notin L_2$. [/mm] Das bedeutet, daß sich [mm] $n_0^3 [/mm] + i * [mm] n_0^2$ [/mm] nicht als Summe der Form [mm] $k^3+k^2$ [/mm] darstellen läßt. Probier mal [mm] $i=n_0$ [/mm] aus. Ich weiß allerdings nicht, ob dann [mm] $uv^{n_0}w$ [/mm] wirklich nicht in [mm] $L_2$ [/mm] ist. Da muß man ein bisschen spielen und $i$ bzw. $u$, $v$ und $w$ so wählen, daß der Beweis leicht fällt.
Viel Erfolg,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:37 Di 29.05.2012 | | Autor: | bandchef |
Du schreibst immer, dass $|uv| > [mm] n_0$ [/mm] sein soll. In meinem Lehrbuch dazu (der Hopcroft) steht, aber dass $|xy| [mm] \geq n_0$ [/mm] sein soll. xy deswegen weil hier anstatt uv eben einfach xy verwendet werden; das macht ja nix...
Zu [mm] $L_2$:
[/mm]
$z = [mm] \underbrace{0^{n_0}^3}_{=u} \underbrace{0^{n_0}^2}_{=v} \underbrace{\epsilon}_{w}$
[/mm]
mit i=2:
$z = uv^iw = uv^2w = [mm] 0^{n_0}^3 0^{n_0}^2 \epsilon [/mm] = [mm] 0^{n_0}^3 \left(0^{n_0}^2\right)^2 \epsilon \notin L_2$
[/mm]
Wenn ich jetzt ein Beispiel durchrechne, dann könnte es passen, da normalerweise gilt:
Ich setze jetzt [mm] $n_0 [/mm] = 2$:
$z = uv^2w = [mm] {0^2}^3 \left({0^2}^2\right)^2 \epsilon \Rightarrow \underbrace{00000000}_{\widehat{=} {0^2}^3} \underbrace{0000000000000000}_{\widehat{=} \left({0^2}^2\right)^2}$
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:31 Di 29.05.2012 | | Autor: | Helbig |
> Du schreibst immer, dass [mm]|uv| > n_0[/mm] sein soll. In meinem
> Lehrbuch dazu (der Hopcroft) steht, aber dass [mm]|xy| \geq n_0[/mm]
> sein soll. xy deswegen weil hier anstatt uv eben einfach xy
> verwendet werden; das macht ja nix...
Wenn ich ein Beispiel habe mit [mm] $|uv|>n_0$, [/mm] dann habe ich auch ein Beispiel mit [mm] $|uv|\ge n_0$.
[/mm]
> Zu [mm]L_2[/mm]:
> [mm]z = \underbrace{0^{n_0}^3}_{=u} \underbrace{0^{n_0}^2}_{=v} \underbrace{\epsilon}_{w}[/mm]
>
> mit i=2:
> [mm]z = uv^iw = uv^2w = 0^{n_0}^3 0^{n_0}^2 \epsilon = 0^{n_0}^3 \left(0^{n_0}^2\right)^2 \epsilon \notin L_2[/mm]
>
>
> Wenn ich jetzt ein Beispiel durchrechne, dann könnte es
> passen, da normalerweise gilt:
> Ich setze jetzt [mm]n_0 = 2[/mm]:
>
> [mm]z = uv^2w = {0^2}^3 \left({0^2}^2\right)^2 \epsilon \Rightarrow \underbrace{00000000}_{\widehat{=} {0^2}^3} \underbrace{0000000000000000}_{\widehat{=} \left({0^2}^2\right)^2}[/mm]
Du darfst nicht für [mm] $n_0$ [/mm] eine Zahl einfach einsetzen. Das Gegenbeispiel muß für jedes [mm] $n_0$ [/mm] gelten. Auch wenn [mm] $n_0$ [/mm] eine Milliarde ist. Und da mußt Du schon abstrakt formulieren und beweisen. Das [mm] $n_0$ [/mm] ist vorgegeben. Die drei Wörter $u$, $v$ und $w$ und die Zahl $i$ mußt Du in Abhängigkeit von [mm] $n_0$ [/mm] konstruieren, so daß [mm] $uvw\in L_2$ [/mm] ist, [mm] $|uv|\ge n_0$ [/mm] ist und [mm] $uv^iw\notin L_2$ [/mm] ist. Dies klappt mit
[mm] $u=0^{n_0^3},\ [/mm] v=0,\ [mm] w=0^{n_0^2-1},\ [/mm] i=2$.
Dann ist die Länge von [mm] $z=uv^2w=n_0^3+2+n_0^2-1$. [/mm] Diese Zahl läßt sich nicht als [mm] $k^3+k^2$ [/mm] darstellen. (Den Beweis hierzu überlasse ich Dir). Und damit ist [mm] $z\notin L_2$.
[/mm]
OK?
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:07 Mi 30.05.2012 | | Autor: | bandchef |
Entschuldige bitte, aber ich hab mich bei meiner letzten Frage im Ungleichheitszeichen vertan:
Du schreibst immer, dass $ |uv| > [mm] n_0 [/mm] $ sein soll. In meinem Lehrbuch dazu (der Hopcroft) steht, aber dass $ |xy| [mm] \leq n_0 [/mm] $ sein soll. xy deswegen weil hier anstatt uv eben einfach xy verwendet werden; das macht ja nix...
Und nun nochmal zum Beweis:
Zu $ [mm] L_2 [/mm] $:
$ z = [mm] 0^{i^3+i^3} [/mm] = [mm] {0^i}^3 {0^i}^2 [/mm] = [mm] \underbrace{0^{n_0}^3}_{=u} \underbrace{0^{n_0}^2}_{=v} \underbrace{\epsilon}_{w} [/mm] $ mit [mm] $k_1 [/mm] + [mm] k_2 [/mm] = [mm] {n_0}^2$
[/mm]
mit i=2:
$ z = uv^iw = [mm] 0^{n_0}^3 \left(0^{{n_0}^2-1}\right)^i \epsilon [/mm] = [mm] 0^{n_0}^3 \left(0^{{n_0}^2-1}\right)^2 \epsilon \notin L_2 [/mm] $
Dass das nun nicht mehr in [mm] L_2 [/mm] enthalten ist, ist klar, da ja im mittleren Teilwort immer eine einzige 0 zu wenig ist. Aber warum darf ich "einfach so" eine 0 abziehen? Weiter schreibst du, dass sich diese "neue" Zahl nun nicht mehr als $ [mm] k^3+k^2 [/mm] $ darstellen lässt. Wie schreibt man das nun am besten auf? Ich verstehe ehrlich gesagt auch nicht, warum du bei k die gleichen Exponenten ranschreibst wie das [mm] n_0 [/mm] hat? Ich hab immer gedacht, dass [mm] n_0 [/mm] wird in k's aufgeteilt und zwar wird das [mm] n_0 [/mm] immer in so viel k's aufgeteilt wie es [mm] n_0 [/mm] hat. Hier also zwei k und es wird immer das [mm] n_0 [/mm] aufgeteilt, welches später gepumpt wird, also so: [mm] $k_1 [/mm] + [mm] k_2 [/mm] = [mm] {n_0}^2$
[/mm]
Nachtrag: Da ich beim "gepumpten v" ja jetzt IMMER eine einzige 0 "abziehe", müsste es doch theoretisch auch eine Lösung mit i=0 geben, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:43 Mi 30.05.2012 | | Autor: | Helbig |
> Entschuldige bitte, aber ich hab mich bei meiner letzten
> Frage im Ungleichheitszeichen vertan:
>
> Du schreibst immer, dass [mm]|uv| > n_0[/mm] sein soll. In meinem
> Lehrbuch dazu (der Hopcroft) steht, aber dass [mm]|xy| \leq n_0[/mm]
> sein soll. xy deswegen weil hier anstatt uv eben einfach xy
> verwendet werden; das macht ja nix...
Ja, ich merke gerade, daß Hopcroft und alle anderen das Pumpinglemma anders als ich verwenden. Aber ich denke, mein Beweis ist auch richtig.
Jedenfalls muß das Wort $uv$ mindestens [mm] $n_0$ [/mm] Zeichen lang sein. Die Idee dabei ist,
daß der Automat mit seinen endlich vielen Zuständen beim Lesen eines genügend langen Anfangs $x$ eines Wortes [mm] $xw\in L_2$ [/mm] mindestens einen Zustand $p$ zweimal annehmen muß. Das erste Mal irgendwo in $x$ und das zweite Mal, nachdem er das letzte Zeichen von $x$ gelesen hat. Wir zerlegen das Wort $x$ in zwei Wörter $x=uv$, so daß er nach dem Lesen von $u$ zum ersten Mal in den Zustand $p$ geht.
Weil nun $uvw [mm] \in L_2$ [/mm] ist, akzeptiert der Automat im Zustand $p$ sowohl $v$ als auch $w$ so daß auch auch $uvvw [mm] \in L_2$ [/mm] usw.
> Zu [mm]L_2 [/mm]:
> [mm]z = 0^{i^3+i^3} = {0^i}^3 {0^i}^2 = \underbrace{0^{n_0}^3}_{=u} \underbrace{0^{n_0}^2}_{=v} \underbrace{\epsilon}_{w}[/mm]
> mit [mm]k_1 + k_2 = {n_0}^2[/mm]
Was Du hier machst, verstehe ich beim besten Willen nicht.
>
>
> mit i=2:
> [mm]z = uv^iw = 0^{n_0}^3 \left(0^{{n_0}^2-1}\right)^i \epsilon = 0^{n_0}^3 \left(0^{{n_0}^2-1}\right)^2 \epsilon \notin L_2[/mm]
>
> Dass das nun nicht mehr in [mm]L_2[/mm] enthalten ist, ist klar, da
> ja im mittleren Teilwort immer eine einzige 0 zu wenig ist.
Ja und? Ein Wort ist genau dann in der Sprache [mm] $L_2$, [/mm] wenn es aus lauter Nullen besteht und sich seine Länge als [mm] $k^3+k^2$ [/mm] für ein [mm] $k\in \IN$ [/mm] darstellen ist.
Demnach ist [mm] $0^{n_0^3}00^{n_0^2-1} \in L_2$, [/mm] denn es besteht aus genau [mm] $n_0^3+n_0^2$ [/mm] Nullen. Aber [mm] $0^{n_0^3}000^{n_0^2-1}$ [/mm] ist nicht in der Sprache, denn die Länge ist [mm] $n_0^3+2+n_0^2-1$. [/mm] Diese Zahl ist ungerade. Aber für jedes [mm] $k\in\IN$ [/mm] ist
[mm] $k^3+k^2$ [/mm] gerade, also kann es kein [mm] $k\in\IN$ [/mm] geben mit [mm] $n_0^3+2+n_0^2-1= k^3+k^2$. [/mm]
Wäre nun [mm] $L_2$ [/mm] regulär, so wäre nach dem PL mit [mm] $0^{n_0^3}00^{n_0^2-1}$ [/mm] auch [mm] $0^{n_0^3}000^{n_0^2-1}$ [/mm] in [mm] $L_2$.
[/mm]
> Aber warum darf ich "einfach so" eine 0 abziehen? Weiter
> schreibst du, dass sich diese "neue" Zahl nun nicht mehr
> als [mm]k^3+k^2[/mm] darstellen lässt. Wie schreibt man das nun am
> besten auf? Ich verstehe ehrlich gesagt auch nicht, warum
> du bei k die gleichen Exponenten ranschreibst wie das [mm]n_0[/mm]
> hat? Ich hab immer gedacht, dass [mm]n_0[/mm] wird in k's aufgeteilt
> und zwar wird das [mm]n_0[/mm] immer in so viel k's aufgeteilt wie
> es [mm]n_0[/mm] hat. Hier also zwei k und es wird immer das [mm]n_0[/mm]
> aufgeteilt, welches später gepumpt wird, also so: [mm]k_1 + k_2 = {n_0}^2[/mm]
Die Vorgehensweise mag in speziellen Fällen nützlich sein, aber jeder Beweis der Nichtregularität sieht anders aus. Eigentlich steckt nicht viel hinter dem Pumpinglemma. Einer Sprache sieht man schnell an, ob sie regulär ist. Hierzu überlegt man, ob der Automat mit seinem endlichen Speicher sich bei jedem Wort der Sprache nur endlich viel merken muß. So ist z. B. [mm] $\{0^n1^n:n\in\IN\}$ [/mm] nicht regulär, da sich der Automat $n$ merken müßte, was bei beschränktem Speicher und genügend großem $n$ nicht möglich ist.
>
> Nachtrag: Da ich beim "gepumpten v" ja jetzt IMMER eine
> einzige 0 "abziehe", müsste es doch theoretisch auch eine
> Lösung mit i=0 geben, oder?
Ja. Aber das brauchen wir nicht. Wir wollen ja zeigen, daß es ein $i$ gibt, so daß $uv^iw$ nicht in $L$ ist.
Aber mehr fällt mir dazu nicht ein.
Grüße,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 20:12 Mi 30.05.2012 | | Autor: | bandchef |
Ich hab nun die Aufgabe soweit verstanden und jetzt genau das auf meinem Blatt stehen:
[mm] $L_2 [/mm] $ = $ [mm] \{ 0^{i^3+i^2} | i\in \mathbb N \} [/mm] $
Annahme: L ist regulär.
Sei [mm] n_0 [/mm] die Konstante des PL, dann gilt: [mm] $n_0 \in \mathbb [/mm] N$, [mm] $n_0 \geq [/mm] 1$.
$z = [mm] 0^{{i}^3 + i^2} [/mm] = [mm] 0^{{i}^3} [/mm] + [mm] 0^{i^2} [/mm] = [mm] 0^{{n_0}^3} 0^{{n_0}^2}$
[/mm]
Eine gültige Zerlegung ist: $z = [mm] \underbrace{0^{{n_0}^3}}_{=u} \underbrace{0}_{=v} \underbrace{0^{{n_0}^2-1}}_{=w}$
[/mm]
mit $|uv| [mm] \geq [/mm] 1$, $ |v| [mm] \geq [/mm] 1$ und $z=uvw$
i=2:
$z = uv^iw = [mm] 0^{{n_0}^3} 0^2 0^{{n_0}^2-1} \notin L_2$, [/mm] da [mm] ${n_0}^3 [/mm] + 2 + [mm] {n_0}^2-1 \neq k^3+k^2$.
[/mm]
Stimmt der Beweis nun so?
Info: Wobei ich mir nach wie vor nicht sicher bin, ob das $|uv| [mm] \geq [/mm] 1$ so stimmt. Auch in meinen Vorlesungsunterlagen (wie im Hopcroft) wird $|uv| [mm] \leq [/mm] 1$ angegeben... Ich möchte dich natürlich hier NICHT angreifen!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:39 Mi 30.05.2012 | | Autor: | Helbig |
Lieber bandchef,
Hopcroft und die vielen anderen haben recht und ich unrecht! Irgendwie bin ich in die falsche Richtung gestolpert. Vergiß am besten alles, was ich zur Anwendung des PLs geschrieben habe.
Nach dem PL gibt es ein $n$, so daß es zu jedem [mm] $z\in [/mm] L$ mit [mm] $|z|\ge [/mm] n$ eine Zerlegung $z=uvw$ gibt mit $|v| [mm] \ge [/mm] 1$, [mm] $|uv|\le [/mm] n$ und [mm] $uv^iw\in [/mm] L$ für alle [mm] $i\in \IN$. [/mm] Um ein Gegenbeispiel zu konstruieren, müssen wir das $z$ angeben, aber wir können nicht die Zerlegung frei wählen, wie ich irrtümlich dachte.
Also nochmal von vorne.
Tut mir leid,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:36 Mi 30.05.2012 | | Autor: | bandchef |
Am besten ist es dann wohl, wenn wir nochmal mit der Aufgabe a) anfangen:
$ [mm] L_1 [/mm] = [mm] \{ 0^j 1^k 0^l | j=k+l \text{für } j,k,l \in \mathbb N \} [/mm] $
Ich beginn dann so:
Annahme: [mm] L_1 [/mm] ist regulär.
Sei [mm] n_0 [/mm] die Konstante des PL, dann gilt: [mm] $n_0 \in \mathbb [/mm] N$, [mm] $n_0 \geq [/mm] 1$.
$z = [mm] 0^{n_0} 1^{n_0} 0^{n_0}$ [/mm] mit $|uv| [mm] \leq n_0$, [/mm] $|v| [mm] \geq [/mm] 1$ und $z = uvw$
gültige Zerlegung:
$z = [mm] \underbrace{0^{n_0}}_{=u} \underbrace{1^{n_0}}_{=v} \underbrace{0^{n_0}}_{=w}$
[/mm]
i=2:
$z = uv^iw = [mm] 0^{n_0} \left(1^{n_0}\right)^2 0^{n_0} \notin L_1$
[/mm]
Naja und irgendwie muss jetzt noch dieses [mm] $k_1 [/mm] + [mm] k_2 [/mm] + [mm] k_3 [/mm] = [mm] n_0$ [/mm] mit rein. Aber da weiß ich jetzt wieder nicht mehr weiter. Ich hoff du hilfst mir jetzt noch weiter 
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:57 Mi 30.05.2012 | | Autor: | Helbig |
> Am besten ist es dann wohl, wenn wir nochmal mit der
> Aufgabe a) anfangen:
>
> [mm]L_1 = \{ 0^j 1^k 0^l | j=k+l \text{für } j,k,l \in \mathbb N \}[/mm]
>
>
> Ich beginn dann so:
>
>
> Annahme: [mm]L_1[/mm] ist regulär.
>
> Sei [mm]n_0[/mm] die Konstante des PL, dann gilt: [mm]n_0 \in \mathbb N[/mm],
> [mm]n_0 \geq 1[/mm].
>
> [mm]z = 0^{n_0} 1^{n_0} 0^{n_0}[/mm] mit [mm]|uv| \leq n_0[/mm], [mm]|v| \geq 1[/mm]
> und [mm]z = uvw[/mm]
>
>
> gültige Zerlegung:
Dies ist falsch! Wir müssen ein [mm] $z\in L_1$ [/mm] wählen. Und dann für jede Zerlegung von
$z=uvw$ mit [mm] $|uv|\le [/mm] n$ und [mm] $1\le [/mm] |v|$ ein $i$ angeben, so daß [mm] $uv^iw\notin L_1$.
[/mm]
>
> [mm]z = \underbrace{0^{n_0}}_{=u} \underbrace{1^{n_0}}_{=v} \underbrace{0^{n_0}}_{=w}[/mm]
Diese $u$, $v$, $w$ dürfen wir nicht bestimmen. Die sind wie das $n$ vom Pumpinglemma vorgegeben.
>
>
>
> i=2:
>
> [mm]z = uv^iw = 0^{n_0} \left(1^{n_0}\right)^2 0^{n_0} \notin L_1[/mm]
>
> Naja und irgendwie muss jetzt noch dieses [mm]k_1 + k_2 + k_3 = n_0[/mm]
> mit rein. Aber da weiß ich jetzt wieder nicht mehr weiter.
> Ich hoff du hilfst mir jetzt noch weiter
Siehe meinen zweiten Versuch!
Grüße,
Wolfgang
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:41 Mi 30.05.2012 | | Autor: | Helbig |
> Beweisen oder widerlegen Sie, dass die folgenden Sprachen
> regulär sind:
>
> a) [mm]L_1 = \{ 0^j 1^k 0^l | j=k+l \text{für } j,k,l \in \mathbb N \}[/mm]
>
> b) [mm]$L_2[/mm] = [mm]\{ 0^{i^3+i^2} | i\in \mathbb N \}[/mm]
>
>
>
> Ich hab hier nun für a) schon mal angefangen:
>
> Bevor man mit dem PL beginnt, muss man eine Annahme
> darüber treffen ob die Sprache regulär ist oder nicht,
> dass man mit dem PL bestätigt, oder widerlegt. Deshalb:
Das Pumpinglemma eignet sich nur, um durch einen Widerspruchsbeweis zu zeigen, daß eine Sprache nicht regulär ist.
>
> Annahme: L ist regulär.
> Sei [mm]n_0[/mm] die Konstante des PL, dann gilt: [mm]n_o \in \mathbb N[/mm],
> [mm]n_0 \geq 1[/mm]
>
> Nun muss man die Sprache irgendwie mit dem PL-Konstante
> ausdrücken. Da hakts dann schon. Ich verstehe die Sprache
> so: die gesamte Anzahl der 1en und der 0en an der letzten
> Stelle ergibt die gesamte Anzahl der 0en an der ersten
> Stelle im Wort. Stimmt doch soweit. Wenn ich jetzt bspw.
> k=3 und l=4 wähle sieht ein mögliches Wort, dass in der
> Sprache [mm]L_1[/mm] liegt wie folgt aus: 00000001110000. Das wäre
> jetzt ein Wort das in der Sprache liegt.
Stimmt. Um zum Widerspruch zu kommen, muß die Länge des Wortes mindestens $n$ sein.
>
>
>
> Wenn man das dann hat, muss man die Sprache in [mm]uv^iw[/mm]
> zerlegen.
Nein! Hier hast Du mich auf die falsche Fährte gebracht. Vielmehr müssen wir zeigen,
daß es zu jeder Zerlegung $z=uvw$ mit [mm] $|uv|\le [/mm] n$ ein $i$ gibt, so daß $uv^iw$ nicht in [mm] $L_1$ [/mm] liegt.
Hierzu wählen wir [mm] $z=0^{2n}1^n0^n$. [/mm] Dann ist [mm] $z\in L_1$ [/mm] und die Länge von $z$ mindestens $n$.
Jetzt sei $z=uvw$ eine Zerlegung mit [mm] $|uv|\le [/mm] n$ und [mm] $1\le [/mm] |v| $. Da [mm] $|uv|\le [/mm] n < 2n$ ist, enthält das Wort $uv$ nur Nullen. Damit enthält $uvvw$ $2n+|v|$ Nullen vor den $n$ Einsen und $n$ Nullen nach den $n$ Einsen. Damit ist $uvvw$ nicht in unserer Sprache [mm] $L_1$.
[/mm]
> Mit einer passenden Wahl von i kann man dann
> widerlegen, dass die Sprache regulär ist, wenn durch das
> "pumpen" ein Wort rauskommt, welches nicht mehr in der
> Sprache [mm]L_1[/mm] liegt. Somit hätte man mit "Beweis durch
> Gegenbeispiel" gezeigt, dass die Sprache [mm]L_1[/mm] nicht regulär
> ist, was heißt, dass man für jedes mögliche Wort aus der
> Sprache [mm]L_1[/mm] einen Automaten zeichenn kann. Das sollte doch
> soweit auch stimmen, oder?
Ja!
Jetzt zum zweiten Beispiel:
Hier wählen wir [mm] $z=0^{n^3}0^{n^2}$. [/mm] Dann ist [mm] $|z|\ge [/mm] n$. Sei jetzt $z=uvw$ mit [mm] $|uv|\le [/mm] n$ und [mm] $1\le [/mm] |v|$. Dann ist [mm] $1\le [/mm] |v| [mm] \le [/mm] n$ und wir erhalten:
[mm] $n^3+n^2 [/mm] < [mm] n^3+n^2 [/mm] + 1 [mm] \le [/mm] |uvvw| [mm] \le n^3+n^2+n [/mm] < [mm] (n+1)^3+(n+1)^2$.
[/mm]
Damit läßt sich die Länge von $uvvw$ nicht in der Form [mm] $k^3+k^2$ [/mm] darstellen,
denn für [mm] $k\le [/mm] n$ ist [mm] $k^3+k^2 \le n^3+n^2 [/mm] < |uvvw|$ und für $k [mm] \ge [/mm] n+1$
ist |uvvw| < [mm] (n+1)^3 [/mm] + [mm] (n+1)^2 \le k^3+k^2$.
[/mm]
Damit haben wir den Widerspruch zum Pumpinglemma [mm] $uvvw\notin [/mm] L$ mit $i=2$ gezeigt.
So, ich glaube, jetzt stimmt es.
liebe Grüße,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:27 Do 31.05.2012 | | Autor: | bandchef |
Zitat:
Hierzu wählen wir $ [mm] z=0^{2n}1^n0^n [/mm] $. Dann ist $ [mm] z\in L_1 [/mm] $ und die Länge von $ z $ mindestens $ n $.
Was hast du hier nun gemacht? Das musst du mir näher erklären. WARUM darf man hier einfach [mm] $0^{2n_0}$ [/mm] schreiben?
Hier mal wieder so wie es auf dem Blat bei mir nun steht:
Annahme: [mm] L_1 [/mm] ist regulär.
Sei $ [mm] n_0 [/mm] $ die Konstante des PL, dann gilt: $ [mm] n_o \in \mathbb [/mm] N $, $ [mm] n_0 \geq [/mm] 1 $.
Somit sieht die Sprache doch nun so aus: $ z = [mm] 0^{n_0} 1^{n_0} 0^{n_0} [/mm] $
Zerlegung:
$ z = [mm] \underbrace{0^{2n}}_{=u} \underbrace{1^n}_{=v} \underbrace{0^n}_{=w}$ [/mm] mit $ [mm] |uv|\le [/mm] n $ und $ [mm] 1\le [/mm] |v| $.
Ich hab ja hier nun die doppelte Anzahl 0en im ersten Teilwort und die richtige Anzahl an 1en mittleren Teilwort und ebenfalls die richtige Anzahl 0en im letzten Teilwort. Laut Bedingung muss ja $|uv|$ kleinergleich dem [mm] $n_0$ [/mm] sein. Wenn ich nun die (Teil-)Wortlänge von u und v zusammennehme, komm ich auf [mm] $3\cdot n_0$ [/mm] was aber nicht mehr kleiner [mm] $n_0$ [/mm] wäre, oder?
Und jetzt muss ich ja noch zeigen, dass ich mit $z = uv^iw$ aus der Sprache rausfliege (so haben wir das zumindestens in der Vorlesung immer gemacht) und "pumpen" darf ich ja eh nur am v:
mit i=1: $ z = uv^iw = [mm] 0^{2n_0} \left(1^{n_0}\right)^i 0^{n_0} [/mm] $ Flieg ich da jetzt wirklich aus der Sprache raus?
Ich denke, dass du mir deine Antwort dazu nochmal genauer erklären müsstest, da du hier versuchst mir genau diese Stelle näher zu bringen:
Zitat: "Jetzt sei $ z=uvw $ eine Zerlegung mit $ [mm] |uv|\le [/mm] n $ und $ [mm] 1\le [/mm] |v| $. Da $ [mm] |uv|\le [/mm] n < 2n $ ist, enthält das Wort $ uv $ nur Nullen. Damit enthält $ uvvw $ $ 2n+|v| $ Nullen vor den $ n $ Einsen und $ n $ Nullen nach den $ n $ Einsen. Damit ist $ uvvw $ nicht in unserer Sprache $ [mm] L_1 [/mm] $."
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:46 Do 31.05.2012 | | Autor: | Helbig |
> Zitat:
>
> Hierzu wählen wir [mm]z=0^{2n}1^n0^n [/mm]. Dann ist [mm]z\in L_1[/mm] und
> die Länge von [mm]z[/mm] mindestens [mm]n [/mm].
>
> Was hast du hier nun gemacht? Das musst du mir näher
> erklären. WARUM darf man hier einfach [mm]0^{2n_0}[/mm] schreiben?
Ich habe ein [mm] $z\in [/mm] L$ angegeben mit $|z| [mm] \ge [/mm] n$. Dabei ist $n$ die Konstante aus dem PL. (Ich schreibe $n$ statt [mm] $n_0$ [/mm] -- aus Faulheit).
>
>
>
> Hier mal wieder so wie es auf dem Blat bei mir nun steht:
>
> Annahme: [mm]L_1[/mm] ist regulär.
> Sei [mm]n_0[/mm] die Konstante des PL, dann gilt: [mm]n_o \in \mathbb N [/mm],
> [mm]n_0 \geq 1 [/mm].
So weit so gut!
>
> Somit sieht die Sprache doch nun so aus: [mm]z = 0^{n_0} 1^{n_0} 0^{n_0}[/mm]
Nein! Wir dürfen die Sprache nicht einfach umdefinieren! Unsere Sprache ist und bleibt
[mm] $L_1=\{0^i1^k0^j : i=j+k\}$ [/mm] und von dieser Sprache wollen wir zeigen, daß sie nicht regulär sein kann!
>
>
> Zerlegung:
> [mm]z = \underbrace{0^{2n}}_{=u} \underbrace{1^n}_{=v} \underbrace{0^n}_{=w}[/mm]
> mit [mm]|uv|\le n[/mm] und [mm]1\le |v| [/mm].
Dies ist eine der vielen möglichen Zerlegungen. Aber wir können die Zerlegung gerade nicht vorgeben, sondern wir müssen den Beweis für alle möglichen Zerlegungen [mm] $0^{2n}0^n0^n=uvw$ [/mm] mit [mm] $|uv|\le [/mm] n$ und [mm] $|v|\ge [/mm] 1$ führen.
>
> Ich hab ja hier nun die doppelte Anzahl 0en im ersten
> Teilwort und die richtige Anzahl an 1en mittleren Teilwort
> und ebenfalls die richtige Anzahl 0en im letzten Teilwort.
> Laut Bedingung muss ja [mm]|uv|[/mm] kleinergleich dem [mm]n_0[/mm] sein.
> Wenn ich nun die (Teil-)Wortlänge von u und v
> zusammennehme, komm ich auf [mm]3\cdot n_0[/mm] was aber nicht mehr
> kleiner [mm]n_0[/mm] wäre, oder?
Genau! Du darfst über die Zerlegung von $z$ in $u$, $v$, $w$ nur voraussetzen, was ich oben geschrieben habe. Dazu gehört nicht, daß [mm] $u=0^{2n},\; v=1^n,\; w=0^n$ [/mm] ist.
>
>
> Und jetzt muss ich ja noch zeigen, dass ich mit [mm]z = uv^iw[/mm]
> aus der Sprache rausfliege (so haben wir das zumindestens
> in der Vorlesung immer gemacht) und "pumpen" darf ich ja eh
> nur am v:
Ja, aber dieses rausfliegen mußt Du für jede der möglichen Zerlegungen zeigen.
>
> mit i=1: [mm]z = uv^iw = 0^{2n_0} \left(1^{n_0}\right)^i 0^{n_0}[/mm]
> Flieg ich da jetzt wirklich aus der Sprache raus?
>
> Ich denke, dass du mir deine Antwort dazu nochmal genauer
> erklären müsstest, da du hier versuchst mir genau diese
> Stelle näher zu bringen:
> Zitat: "Jetzt sei [mm]z=uvw[/mm] eine Zerlegung mit [mm]|uv|\le n[/mm] und
> [mm]1\le |v| [/mm]. Da [mm]|uv|\le n < 2n[/mm] ist, enthält das Wort [mm]uv[/mm] nur
> Nullen. Damit enthält [mm]uvvw[/mm] [mm]2n+|v|[/mm] Nullen vor den [mm]n[/mm] Einsen
> und [mm]n[/mm] Nullen nach den [mm]n[/mm] Einsen. Damit ist [mm]uvvw[/mm] nicht in
> unserer Sprache [mm]L_1 [/mm]."
Erkläre ich Dir gerne. Welches Argument ist unklar? Denke bitte daran, daß das Pumpinglemma keine Handlungsanweisung ist, sondern ein mathematischer Satz. Ich habe jetzt mal in meinem Hopcroft (deutsch 1988) nachgeschaut. Da wird das Pumpinglemma sehr ungenau formuliert, gefolgt von einem Beweisrezept. Der Zusammenhang zwischen seinem PL und der Beweisrezeptur bleibt dabei im Unklaren.
Versuche das Pumpinglemma zu verstehen. Und dann verstehst Du auch meine Beweise.
Hier noch mal eine saubere Formulierung:
Sei $L$ eine reguläre Sprache. Dann gibt es eine natürliche Zahl [mm] $n\ge [/mm] 1$ so, daß gilt:
Zu jedem Wort $ z [mm] \in [/mm] L $ mit [mm] $|z|\ge [/mm] n$ gibt es eine Zerlegung $z=uvw$
mit [mm] $|uv|\le [/mm] n$, [mm] $|v|\ge [/mm] 1$ und [mm] $uv^iw\in [/mm] L$ für jedes [mm] $i\in \IN$.
[/mm]
Beim Widerspruchsbeweis müssen wir also ein [mm] $z\in [/mm] L$ und ein $i$ so angeben,
daß [mm] $|z|\ge [/mm] n$ und [mm] $z=uv^iw\notin [/mm] L$ für jede Zerlegung von $z=uvw$ mit [mm] $|uv|\le [/mm] n$ und [mm] $|v|\ge [/mm] 1$.
liebe Grüße,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:17 Fr 01.06.2012 | | Autor: | bandchef |
Zitat: "Genau! Du darfst über die Zerlegung von z in u, v, w nur voraussetzen, was ich oben geschrieben habe. Dazu gehört nicht, daß $ [mm] u=0^{2n},\; v=1^n,\; w=0^n [/mm] $ ist."
Ok. Weil eben nun (Voraussetzung war ja: $|uv| [mm] \leq n_0$, [/mm] $|v| [mm] \geq [/mm] 1$ und $z = uvw$) von dieser Zerlegung die Länge $|uv| > [mm] n_0$ [/mm] ist (genauer [mm] 3\cdot n_0), [/mm] kann die Sprache (in diesem Fall; bis jetzt zumindestens) nicht mehr regulär sein.
Jetzt folgt also nun noch der Beweis mit dem eigentlichen PL, in dem Zeigen muss, dass das für alles gilt, oder?
Zitat: "Dies ist eine der vielen möglichen Zerlegungen. Aber wir können die Zerlegung gerade nicht vorgeben, sondern wir müssen den Beweis für alle möglichen Zerlegungen $ [mm] 0^{2n}0^n0^n=uvw [/mm] $ mit $ [mm] |uv|\le [/mm] n $ und $ [mm] |v|\ge [/mm] 1 $ führen."
Warum schreibst du hier: $ [mm] 0^{2n}0^n0^n=uvw [/mm] $? Muss das nicht so lauten: $ [mm] 0^{2n}1^n0^n=uvw [/mm] $
Zitat: "Beim Widerspruchsbeweis müssen wir also ein $ [mm] z\in [/mm] L $ und ein i so angeben,
daß $ [mm] |z|\ge [/mm] n $ und $ [mm] z=uv^iw\notin [/mm] L $ für jede Zerlegung von z=uvw mit $ [mm] |uv|\le [/mm] n $ und $ [mm] |v|\ge [/mm] 1 $."
So hier gehts dann wohl um das PL an sich. Das Wort muss also per Definition größer n sein. Das gepumpte Wort ($ [mm] z=uv^iw\notin [/mm] L $) darf dann nicht mehr in L sein. Das is ja eben der Widerspruchsbeweis, dass wenn man für ein einziges Wort zeigen kann, dass es "rausfliegt" die gesamte Sprache nicht mehr regulär sein kann. Soweit hab ich das auch kapiert. Aber ich muss ja eben jetzt noch eine Zerlegung angeben, die genau das erfüllt.
Was ich nun nicht verstehe, ist, warum dann $z = [mm] 0^{2n}0^n0^n=uvw [/mm] $ nicht gleich so eine Zerlegung ist. Da ist ohne pumpen dieses Wort schon nicht mehr in L, denn wie ich schon mal geschrieben habe, ist hier dann $|uv| = 3 [mm] \cdot n_0$, [/mm] was zur Folge hat, dass $|uv| > [mm] n_0$ [/mm] ist, was per Definition verboten ist...
Verstehst du was ich meine?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:36 Fr 01.06.2012 | | Autor: | Helbig |
> Ok. Weil eben nun (Voraussetzung war ja: [mm]|uv| \leq n_0[/mm], [mm]|v| \geq 1[/mm]
> und [mm]z = uvw[/mm]) von dieser Zerlegung die Länge [mm]|uv| > n_0[/mm] ist
> (genauer [mm]3\cdot n_0),[/mm] kann die Sprache (in diesem Fall; bis
> jetzt zumindestens) nicht mehr regulär sein.
Falsch. Bei Deiner Wahl speziellen Zerlegung ist das so. Aber nicht bei jeder Zerlegung.
Nehmen wir ein konkretes Beispiel mit $n=2$. Dann ist $z=0010$ in unserer Sprache und $|z|=4 > 2. Eine mögliche Zerlegung $z=uvw$ mit [mm] $|uv|\le [/mm] n$ und [mm] $|v|\ge [/mm] 1$ wäre jetzt [mm] $u=\epsilon, [/mm] v=00, w=10$. Und für diese Zerlegung ist $uv^2w=000010$ nicht in unserer Sprache. In diesem Beispiel habe ich $i=2$ gewählt, aber auch $i=0$ liefert ein Wort, das nicht in der Sprache ist, nämlich $10$.
Im Beweis muß man für jede Zerlegung ein $i$ angeben.
>
> Jetzt folgt also nun noch der Beweis mit dem eigentlichen
> PL, in dem Zeigen muss, dass das für alles gilt, oder?
>
>
>
> Zitat: "Dies ist eine der vielen möglichen Zerlegungen.
> Aber wir können die Zerlegung gerade nicht vorgeben,
> sondern wir müssen den Beweis für alle möglichen
> Zerlegungen [mm]0^{2n}0^n0^n=uvw[/mm] mit [mm]|uv|\le n[/mm] und [mm]|v|\ge 1[/mm]
> führen."
>
> Warum schreibst du hier: [mm]0^{2n}0^n0^n=uvw [/mm]? Muss das nicht
> so lauten: [mm]0^{2n}1^n0^n=uvw[/mm]
Ja. Tippfheler.
> Zitat: "Beim Widerspruchsbeweis müssen wir also ein [mm]z\in L[/mm]
> und ein i so angeben,
> daß [mm]|z|\ge n[/mm] und [mm]z=uv^iw\notin L[/mm] für jede Zerlegung von
> z=uvw mit [mm]|uv|\le n[/mm] und [mm]|v|\ge 1 [/mm]."
>
> So hier gehts dann wohl um das PL an sich. Das Wort muss
> also per Definition größer n sein. Das gepumpte Wort ([mm] z=uv^iw\notin L [/mm])
> darf dann nicht mehr in L sein. Das is ja eben der
> Widerspruchsbeweis, dass wenn man für ein einziges Wort
> zeigen kann, dass es "rausfliegt" die gesamte Sprache nicht
> mehr regulär sein kann. Soweit hab ich das auch kapiert.
> Aber ich muss ja eben jetzt noch eine Zerlegung angeben,
> die genau das erfüllt.
Nein, nein, nein. Du mußt den Beweis für jede Zerlegung führen, du darfst gar keine spezielle Zerlegung angeben.
>
> Was ich nun nicht verstehe, ist, warum dann [mm]z = 0^{2n}0^n0^n=uvw[/mm]
> nicht gleich so eine Zerlegung ist. Da ist ohne pumpen
> dieses Wort schon nicht mehr in L, denn wie ich schon mal
> geschrieben habe, ist hier dann [mm]|uv| = 3 \cdot n_0[/mm], was zur
> Folge hat, dass [mm]|uv| > n_0[/mm] ist, was per Definition verboten
> ist...
>
> Verstehst du was ich meine?
Ja. Es gibt sehr viele Zerlegungen von [mm] $0^{2n}1^n0^n$. [/mm] Einige von denen erfüllen die Zusatzbedingung [mm] $|uv|\le [/mm] n$ und [mm] $|v|\ge [/mm] n$. Und für alle diese mußt Du zeigen, daß man sie aus der Sprache "rauspumpen" kann.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:13 Sa 02.06.2012 | | Autor: | bandchef |
Zitat: "Nehmen wir ein konkretes Beispiel mit $n=2$. Dann ist $z=0010$ in unserer Sprache und $|z|=4 > 2. Eine mögliche Zerlegung $z=uvw$ mit $ [mm] $|uv|\le [/mm] $ n$ und $ [mm] $|v|\ge [/mm] $ 1$ wäre jetzt $ [mm] $u=\epsilon, [/mm] $ v=00, w=10$. Und für diese Zerlegung ist $uv^2w=000010$ nicht in unserer Sprache. In diesem Beispiel habe ich $i=2$ gewählt, aber auch $i=0$ liefert ein Wort, das nicht in der Sprache ist, nämlich $10$."
Ein konkretes Beispiel ist eine super Idee. Vielleicht kann ich es mir da besser vorstellen.
Wir haben ja mittlerweile rausgefunden, dass $z = [mm] 0^{2n} 1^n 0^n$ [/mm] gilt. Jetzt setzen wir für das Konkrete Beispiel n=2. Wenn ich hier nun 2 einsetze, dann komm ich auf ein ganze anderes Wort als du:
$z = [mm] 0^{2\cdot 2} 1^2 0^2$ [/mm] was ja dann 00001100 entspricht. Hier wäre dann $|z| = 8 > 2$. Kann es vielleicht sein, dass du dich oben verschrieben hast und anstatt n=2, n=1 wählen wolltest? Denn dann stimmt's überein
$z = [mm] 0^{2n} 1^n 0^n [/mm] = [mm] 0^{2\cdot 2} 1^2 0^2 \Rightarrow [/mm] z = 00001100$ Wenn ich zu diesem Wort nun meine Ausgangssprache, also $z = [mm] 0^j 1^k 0^l$ [/mm] mit $j=k+l$ anschaue ist dieses Wort noch in der Sprache und somit noch regulär.
Zerlegung: $z = [mm] \underbrace{\epsilon}_{=u} \underbrace{0^{2n} 1^n}_{=v} \underbrace{0^n}_{=w}$
[/mm]
mit i=2: $z = uv^iw = [mm] \underbrace{\epsilon}_{=u} \left( \underbrace{0^{2n}}_{=v} \right)^2 \underbrace{1^n 0^n}_{=w} \notin [/mm] L$
Wenn jetzt gepumpt wurde sieht das Wort so aus: $z = 000000001100$. Wenn ich zu diesem Wort nun meine Ausgangssprache, also $z = [mm] 0^j 1^k 0^l$ [/mm] mit $j=k+l$ anschaue ist das ein Wort das rausgeflogen ist. Somit ist die Sprache doch nicht mehr regulär.
PS: Was ich bis jetzt gemeint habe, dass ich es verstanden habe,
dem aber leider nicht so ganz ist, ist, wie wir von $z = [mm] 0^j 1^k 0^l$ [/mm] zu $z = [mm] 0^{2n} 1^n 0^n$ [/mm] gekommen sind.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:15 Sa 02.06.2012 | | Autor: | Helbig |
> Wir haben ja mittlerweile rausgefunden, dass [mm]z = 0^{2n} 1^n 0^n[/mm]
> gilt.
Das "gilt" nicht, sondern $z$ entspricht den Voraussetzungen des PLs, d. h. [mm] $z\in [/mm] L$ und
[mm] $|z|\ge [/mm] n$.
>Jetzt setzen wir für das Konkrete Beispiel n=2. Wenn
> ich hier nun 2 einsetze, dann komm ich auf ein ganze
> anderes Wort als du:
Na ja, so anders nun auch wieder nicht. Aber ich meinte tatsächlich $n=1$. Genauso gut klappt es natürlich mit $n=2$.
>
>
> [mm]z = 0^{2n} 1^n 0^n = 0^{2\cdot 2} 1^2 0^2 \Rightarrow z = 00001100[/mm]
> Wenn ich zu diesem Wort nun meine Ausgangssprache, also [mm]z = 0^j 1^k 0^l[/mm]
> mit [mm]j=k+l[/mm] anschaue ist dieses Wort noch in der Sprache und
> somit noch regulär.
Das ist kein Zufall. Nach PL habe ich das Wort so wählen müssen, sonst wäre der Beweis falsch!
>
>
> Zerlegung: [mm]z = \underbrace{\epsilon}_{=u} \underbrace{0^{2n} 1^n}_{=v} \underbrace{0^n}_{=w}[/mm]
Diese Zerlegung liefert kein Beispiel! Nach Pumpinglemma gibt es eine Zerlegung mit $|uv| [mm] \le [/mm] n$. Die Schreibweise mit dem [mm] $\underbrace$ [/mm] ist nicht so das Gelbe vom Ei. Gibt doch einfach $u$, $v$ und $w$ an!
>
> mit i=2: [mm]z = uv^iw = \underbrace{\epsilon}_{=u} \left( \underbrace{0^{2n}}_{=v} \right)^2 \underbrace{1^n 0^n}_{=w} \notin L[/mm]
>
> Wenn jetzt gepumpt wurde sieht das Wort so aus: [mm]z = 000000001100[/mm].
Was ist denn jetzt dein $v$ gewesen. Hier markierst Du es als [mm] $0^{2n}$, [/mm] und vorher als [mm] $0^{2n}1^n$.
[/mm]
Für $v=000011$ ist [mm] $v^2=000011000011$ [/mm] und
$uv^2w=00001100001100$. Dies ist zwar auch nicht in der Sprache, aber aus ganz anderen Gründen als bei meinem Beweis. Daher als Beispiel ungeeignet.
> Wenn ich zu diesem Wort nun meine Ausgangssprache, also [mm]z = 0^j 1^k 0^l[/mm]
> mit [mm]j=k+l[/mm] anschaue ist das ein Wort das rausgeflogen ist.
> Somit ist die Sprache doch nicht mehr regulär.
Wenn ich das so lese, scheint mir ein großes Mißverständnis Deinerseits vorzuliegen.
Wir haben es hier immer nur mit ein und derselben Sprache zu tun! Wir haben keine Ausgangs- oder Zielsprache. Und diese Sprache ist regulär oder sie ist es nicht. Zu sagen, sie sei es "nicht mehr", ist Unsinn.
>
>
> PS: Was ich bis jetzt gemeint habe, dass ich es verstanden
> habe,
> dem aber leider nicht so ganz ist, ist, wie wir von [mm]z = 0^j 1^k 0^l[/mm]
> zu [mm]z = 0^{2n} 1^n 0^n[/mm] gekommen sind.
Durch unsere große Findigkeit: Wir suchen ein [mm] $z\in [/mm] L$ mit [mm] $|z|\ge [/mm] n$.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:44 So 03.06.2012 | | Autor: | bandchef |
Zitat: "Diese Zerlegung liefert kein Beispiel! Nach Pumpinglemma gibt es eine Zerlegung mit $ |uv| [mm] \le [/mm] n $. Die Schreibweise mit dem $ [mm] \underbrace [/mm] $ ist nicht so das Gelbe vom Ei. Gibt doch einfach $ u $, $ v $ und $ w $ an!"
Nun ja, da ist mir wohl ein Tipfehler untergekommen:
Zerlegung: $ z = [mm] \underbrace{\epsilon}_{=u} \underbrace{0^{2n}}_{=v} \underbrace{1^n 0^n}_{=w} [/mm] $
Jetzt sollte es passen. Dass diese [mm] $\underbrace{}_{}$ [/mm] nicht so der Bringer ist; hab ich nicht gedacht. Mein Prof benutzt die eigentlich immer. Aber ok. Man lernt eben nie aus.
Diese Zerlegung darf man "frei" wählen, aber eben nur so, dass man dann im nächsten Schritt wo man pumpt, sieht, dass die Sprache nicht regulär ist.
Zitat: "Durch unsere große Findigkeit: Wir suchen ein $ [mm] z\in [/mm] L $ mit $ [mm] |z|\ge [/mm] n $."
Das heißt also, dass hier eigentlich die ganze Arbeit drin steckt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:07 So 03.06.2012 | | Autor: | Helbig |
> Nun ja, da ist mir wohl ein Tipfehler untergekommen:
>
> Zerlegung: [mm]z = \underbrace{\epsilon}_{=u} \underbrace{0^{2n}}_{=v} \underbrace{1^n 0^n}_{=w}[/mm]
Dies ist falsch. Beim Beweis dürfen wir die Zerlegung gerade nicht frei wählen,
sondern müssen ihn für jede mögliche Zerlegung führen. Dabei dürfen wir nur voraussetzen, daß [mm] $|uv|\le [/mm] n$ ist und [mm] $|v|\ge\epsilon$ [/mm] -- und sonst gar nichts.
In Deiner Beispielzerlegung ist nun gerade diese Voraussetzung nicht gegeben, da $|v|=2n > n$ ist.
> Diese Zerlegung darf man "frei" wählen, aber eben nur so,
> dass man dann im nächsten Schritt wo man pumpt, sieht,
> dass die Sprache nicht regulär ist.
Das einzige, was man frei wählen darf, ist das $z$ mit [mm] $|z|\ge [/mm] n$ und [mm] $z\in [/mm] L$. Und dies muß man so geschickt wählen, daß man danach ein [mm] $i\in \IN$ [/mm] angeben kann, so daß für jede Zerlegung [mm] $uv^iw\notin [/mm] L$ ist.
Lies doch nochmal den Beweis des PL von Blech durch. Das $v$ ist dann gerade die Zeichenkette, die der Automat zwischen dem ersten und dem zweiten Eintritt in den Zustand $p$ liest. Dazu muß er mindestens ein Zeichen lesen, daher ist [mm] $|v|\ge [/mm] 1$ und ein Zustand wird nach höchstens $n$ Schritten zum zweiten Mal angenommen, daher ist [mm] $|uv|\le [/mm] n$. Hierbei ist $n$ die Zahl der Zustände des endlichen Automaten.
OK?
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:37 So 03.06.2012 | | Autor: | bandchef |
Ich werd dann hier nochmal genau das reinschreiben, was ich auf meinem Blatt stehen hab:
Annahme: L ist regulär
Sei [mm] n_0 [/mm] die Konstante des Pl, dann gilt: [mm] $n_0 \in \mathbb [/mm] N$ mit [mm] $n_0 \geq [/mm] 1$.
$z = [mm] 0^{2n} 1^n 0^n$ [/mm] mit $z=uvw$, $|uv| [mm] \leq n_0$ [/mm] und $|v| [mm] \geq [/mm] 1$
Eine mögliche Zerlegung: $ z = [mm] \underbrace{\epsilon}_{=u} \underbrace{0^{2n}}_{=v} \underbrace{1^n 0^n}_{=w} [/mm] $
mit i=2: $z = uv^iw = uv^2w = [mm] \underbrace{\epsilon}_{=u} \left(\underbrace{0^{2n}}_{=v}\right)^2 \underbrace{1^n 0^n}_{=w} \notin [/mm] L$, da nun $|uv| [mm] \geq n_0$
[/mm]
Ich denke mal, dass das nun bis zur Zerlegung stimmen sollte.
Zitat: "Beim Beweis dürfen wir die Zerlegung gerade nicht frei wählen,
sondern müssen ihn für jede mögliche Zerlegung führen. Dabei dürfen wir nur voraussetzen, daß $ [mm] |uv|\le [/mm] n $ ist und $ [mm] |v|\ge\epsilon [/mm] $ -- und sonst gar nichts."
Ich hab mir zu Blechs Informationen mal eine Zeichnung gemacht: http://s14.directupload.net/file/d/2910/tj6pkcsf_jpg.htm
Wie ich nun diese Zerlegung richtig mache, verstehe ich einfach nicht. Laut Blech, soll man ja p+1 Schritte an einem Automaten durchführen, der aber nur p Schritte kennt. Dass dann ein Zustand mehr als einmal vorkommen muss ist mir auch klar. Wie er schreibt, ist es dann auch egal was zwischen den beiden Zeitpunkten passiert. Das leuchtet mir auch noch ein. Dass man das dann einfach weglassen (wie soll das weglassen hier allerdings funktionieren also speziell in meinem Automaten?) oder so oft wiederholen kann wie man will leuchtet ebenfalls ein insbesondere deswegen weil ich ja wirklich immer wieder in den Zustand zurückkomme, das ist quasi die gestrichelte Schleife in diesem Automaten.
Jetzt kann man sich fragen wo das Problem liegt. Das Problem ist einfach, dass ich nicht weiß wie ich diese Theorie auf den praktischen Beweis anweden soll...
Edit:
Zitat: "In Deiner Beispielzerlegung ist nun gerade diese Voraussetzung nicht gegeben, da |v|=2n > n ist."
Aber diese Beispielzerlegung hab ich ja von dir quasi "abgeschrieben"... Irgendwie verstehe ich jetzt gar nix mehr Aber wir bleiben weiter dran am Problem
Edit2:
Zitat: "Dabei dürfen wir nur voraussetzen, daß $ [mm] |uv|\le [/mm] n $ ist und $ [mm] |v|\ge\epsilon [/mm] $ -- und sonst gar nichts."
Ich hab immer gedacht, dass $|v| [mm] \neq \epsilon$ [/mm] sein muss. So steht's zumindestens auch im Hopcroft.
Laut meinen Folien machen wir dann hier die ganze Zeit die Anwendung des "verschärften PL". Auch hab ich gelesen, dass das [mm] $n_0$ [/mm] der Gesamtheit aller Zustände des Automaten entspricht, also Q.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:00 So 03.06.2012 | | Autor: | Helbig |
> Zitat: "Dabei dürfen wir nur voraussetzen, daß [mm]|uv|\le n[/mm]
> ist und [mm]|v|\ge\epsilon[/mm] -- und sonst gar nichts."
Da hab ich einen Tippfehler gemacht. Es muß [mm] $|v|\ge [/mm] 1$ oder [mm] $v\ne\epsilon$ [/mm] heißen,
was ja dasselbe bedeutet.
>
> Ich hab immer gedacht, dass [mm]|v| \neq \epsilon[/mm] sein muss. So
> steht's zumindestens auch im Hopcroft.
> Laut meinen Folien machen wir dann hier die ganze Zeit die
> Anwendung des "verschärften PL". Auch hab ich gelesen,
> dass das [mm]n_0[/mm] der Gesamtheit aller Zustände des Automaten
> entspricht, also Q.
[mm] $n_0$ [/mm] "entspricht" nicht $Q$, sondern ist die Anzahl der Zustände, d.h. der Elemente in Q. Genauso hat es auch Blech formuliert.
Gruß
Wolfgang
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:02 Mo 04.06.2012 | | Autor: | bandchef |
Hm, wo hat Helbig eigentlich was zum PL geschrieben? Den einzigen Eintrag den ich finden kann, ist der zweite in diesem Thread, und da schreibt er nichts von Q...
Meinst du etwa einen anderen Thread?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:40 Mo 04.06.2012 | | Autor: | Helbig |
> Hm, wo hat Helbig eigentlich was zum PL geschrieben? Den
> einzigen Eintrag den ich finden kann, ist der zweite in
> diesem Thread, und da schreibt er nichts von Q...
>
> Meinst du etwa einen anderen Thread?
Nein. Sondern Blech.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:17 Mo 04.06.2012 | | Autor: | bandchef |
Ich probiere dann nochmal die Aufgabe zu lösen:
$L = [mm] \{ 0^j 1^k 0^l | j=k+l \text{ für }j,k,l \in \mathbb N \}
[/mm]
Annahme: L ist regulär.
Sei [mm] n_0 [/mm] die Konstante des PL, dann gilt: [mm] $n_0 \geq [/mm] 1$ und [mm] $n_o \in \mathbb [/mm] N$
$z = [mm] 0^{n_0} 1^{n_0} 0^{n_0}$ [/mm] mit $|z| [mm] \geq n_0$ [/mm] und $z [mm] \in \mathbb [/mm] N$
Jede gültige Zerlegung von z hat die Form:
$z = [mm] 0^{2n_0} 1^{n_0} 0^{n_0} [/mm] = [mm] 0^{k_1} 0^{k_2} 0^{k_3} 1^{n_0} 0^{n_0}$
[/mm]
mit $u = [mm] 0^{k_1}$, [/mm] $v = [mm] 0^{k_2}$ [/mm] und $ w = [mm] 0^{k_3} 1^{n_0} 0^{n_0}$
[/mm]
sowie [mm] $k_1 [/mm] + [mm] k_2 [/mm] + [mm] k_3 [/mm] = [mm] 2n_0$, $k_2 [/mm] < [mm] n_0$, $k_1 [/mm] + [mm] k_3 [/mm] < [mm] n_0$
[/mm]
und $|uv| [mm] \leq n_0$ [/mm] und $|v| [mm] \geq [/mm] 1$
$z = uv^2w = [mm] 0^{k_1} \left(0^{k_2}\right)^2 0^{k_3} 1^{n_0} 0^{n_0} [/mm] = [mm] 0^{k_1} 0^{k_2} 0^{k_3} 1^{n_0} 0^{n_0} 0^{k_2} [/mm] = z [mm] 0^{k_2} \notin [/mm] L$, da [mm] $2n_0 [/mm] < [mm] 2n_0+1$
[/mm]
Stimmt das so?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:38 Mo 04.06.2012 | | Autor: | Helbig |
> Ich probiere dann nochmal die Aufgabe zu lösen:
>
>
> $L = [mm]\{ 0^j 1^k 0^l | j=k+l \text{ für }j,k,l \in \mathbb N \}[/mm]
>
>
> Annahme: L ist regulär.
>
> Sei [mm]n_0[/mm] die Konstante des PL, dann gilt: [mm]n_0 \geq 1[/mm] und [mm]n_o \in \mathbb N[/mm]
>
> [mm]z = 0^{n_0} 1^{n_0} 0^{n_0}[/mm] mit [mm]|z| \geq n_0[/mm] und [mm]z \in \mathbb N[/mm]
Falsch. Das von Dir gewählte $z$ muß in der Sprache $L$ sein. Was nicht der Fall ist.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:43 Mo 04.06.2012 | | Autor: | bandchef |
$L = $ [mm] \{ 0^j 1^k 0^l | j=k+l \text{ für }j,k,l \in \mathbb N \} [/mm] $
Annahme: L ist regulär.
Sei $ [mm] n_0 [/mm] $ die Konstante des PL, dann gilt: $ [mm] n_0 \geq [/mm] 1 $ und $ [mm] n_o \in \mathbb [/mm] N $
$ z = [mm] 0^{2n_0} 1^{n_0} 0^{n_0} [/mm] $ mit $ |z| [mm] \geq n_0 [/mm] $ und $ z [mm] \in \mathbb [/mm] N $
Jede gültige Zerlegung von z hat die Form:
$ z = [mm] 0^{2n_0} 1^{n_0} 0^{n_0} [/mm] = [mm] 0^{k_1} 0^{k_2} 0^{k_3} 1^{n_0} 0^{n_0} [/mm] $
mit $ u = [mm] 0^{k_1} [/mm] $, $ v = [mm] 0^{k_2} [/mm] $ und $ w = [mm] 0^{k_3} 1^{n_0} 0^{n_0} [/mm] $
sowie $ [mm] k_1 [/mm] + [mm] k_2 [/mm] + [mm] k_3 [/mm] = [mm] 2n_0 [/mm] $, $ [mm] k_2 [/mm] < [mm] n_0 [/mm] $, $ [mm] k_1 [/mm] + [mm] k_3 [/mm] < [mm] n_0 [/mm] $
und $ |uv| [mm] \leq n_0 [/mm] $ und $ |v| [mm] \geq [/mm] 1 $
$ z = uv^2w = [mm] 0^{k_1} \left(0^{k_2}\right)^2 0^{k_3} 1^{n_0} 0^{n_0} [/mm] = [mm] 0^{k_1} 0^{k_2} 0^{k_3} 1^{n_0} 0^{n_0} 0^{k_2} [/mm] = z [mm] 0^{k_2} \notin [/mm] L $, da $ [mm] 2n_0 [/mm] < [mm] 2n_0+1 [/mm] $
Stimmts jetzt? Jetzt ist zumindestens schon mal z in L...
Zitat: "Nein. Sondern Blech."
Ja, wie gesagt, in diesem Thread gibt es ja nur eine Antwort von Blech! Und da erklärt er ja eigentlich nichts vom PL...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:56 Mo 04.06.2012 | | Autor: | Helbig |
>
> Jede gültige Zerlegung von z hat die Form:
>
> [mm]z = 0^{2n_0} 1^{n_0} 0^{n_0} = 0^{k_1} 0^{k_2} 0^{k_3} 1^{n_0} 0^{n_0}[/mm]
>
> mit [mm]u = 0^{k_1} [/mm], [mm]v = 0^{k_2}[/mm] und [mm]w = 0^{k_3} 1^{n_0} 0^{n_0}[/mm]
>
> sowie [mm]k_1 + k_2 + k_3 = 2n_0 [/mm], [mm]k_2 < n_0 [/mm], [mm]k_1 + k_3 < n_0[/mm]
>
> und [mm]|uv| \leq n_0[/mm] und [mm]|v| \geq 1[/mm]
Damit kann ich nichts anfangen.
Weiter geht's vielmehr mit: Sei $z=uvw$ eine Zerlegung von $z$ mit [mm] $|uv|\le [/mm] n$ und [mm] $v\ne\epsilon$.
[/mm]
> Zitat: "Nein. Sondern Blech."
>
> Ja, wie gesagt, in diesem Thread gibt es ja nur eine
> Antwort von Blech! Und da erklärt er ja eigentlich nichts
> vom PL...
Wirklich nicht? Er beweist das Pumpinglemma sogar!
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:19 Mo 04.06.2012 | | Autor: | bandchef |
Zitat: "
Hi,
die Idee ist, daß Du p+1 Schritte bei einem Automaten durchführst, der nur p Zustände kennt. Also wird mindestens 1 Zustand mehr als einmal auftreten. Was auch immer zwischen den beiden Zeitpunkten passiert ist, kannst Du entweder weglassen oder beliebig oft wiederholen, weil es Dich ja wieder in den gleichen Zustand zurückführt.
> Ich muss eine Vorlesung zu Theoretischer Informatik machen und hab riesige Probleme beim Pumping Lemma. Ich kann nun schon fast diesbezüglich, dass ganze Skript auswendig, hab auch schon den Hopcroft (Standardliteratur in diesem Gebiet!) zu diesem Thema gewälzt, aber bei Aufgaben häng ich immer noch in der Luft.
Wenn Du die Idee verstanden hast, aber Dir die Anwendung schwerfällt, dann ist es schwer Dir zu helfen, wenn Du nur das topic, aber keine speziellen Aufgaben postest. =)
ciao
Stefan
"
Ist das dann alles?
Annahme: L ist regulär.
Sei $ [mm] n_0 [/mm] $ die Konstante des PL, dann gilt: $ [mm] n_0 \geq [/mm] 1 $ und $ [mm] n_o \in \mathbb [/mm] N $
$ z = [mm] 0^{2n_0} 1^{n_0} 0^{n_0} [/mm] $ mit $ |z| [mm] \geq n_0 [/mm] $ und $ z [mm] \in \mathbb [/mm] N $
Jede gültige Zerlegung von z hat die Form:
$ z = [mm] \epsilon 0^{2n_0} 1^{n_0} 0^{n_0} \Rightarrow [/mm] u = [mm] \epsilon, [/mm] v = [mm] 0^{2n_0}, [/mm] w = [mm] 1^{n_0} 0^{n_0}$
[/mm]
und $ |uv| [mm] \leq n_0 [/mm] $ und $ |v| [mm] \geq [/mm] 1 $
$ z = uv^2w = [mm] \epsilon \left( 0^{2n_0} \right)^2 1^{n_0} 0^{n_0} [/mm] = [mm] \epsilon 0^{4n_0} 1^{n_0} 0^{n_0}$
[/mm]
Wie geht's da jetzt weiter?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:38 Mo 04.06.2012 | | Autor: | Helbig |
> Zitat: "
> Hi,
>
> die Idee ist, daß Du p+1 Schritte bei einem Automaten
> durchführst, der nur p Zustände kennt. Also wird
> mindestens 1 Zustand mehr als einmal auftreten. Was auch
> immer zwischen den beiden Zeitpunkten passiert ist, kannst
> Du entweder weglassen oder beliebig oft wiederholen, weil
> es Dich ja wieder in den gleichen Zustand zurückführt.
>
> Ist das dann alles?
Ja. Das ist der Beweis.
Das Weglassen oder beliebig oft wiederholen ist dann das Pumpen, d. h. für alle [mm] $i\in\IN$ [/mm] wird mit $uvw$ auch $uv^iw$ von dem Automaten akzeptiert. Und wenn es ein $i$ gibt, so daß $uv^iw$ nicht in der Sprache ist, kann die Sprache nicht regulär sein.
>
> Jede gültige Zerlegung von z hat die Form:
>
> [mm]z = \epsilon 0^{2n_0} 1^{n_0} 0^{n_0} \Rightarrow u = \epsilon, v = 0^{2n_0}, w = 1^{n_0} 0^{n_0}[/mm]
>
> und [mm]|uv| \leq n_0[/mm] und [mm]|v| \geq 1[/mm]
Unsinn. Mach da weiter wo ich aufgehört hatte.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:49 Mo 04.06.2012 | | Autor: | bandchef |
Dann gleich nochmal:
Annahme: L ist regulär.
Sei $ [mm] n_0 [/mm] $ die Konstante des PL, dann gilt: $ [mm] n_0 \geq [/mm] 1 $ und $ [mm] n_o \in \mathbb [/mm] N $
$ z = [mm] 0^{2n_0} 1^{n_0} 0^{n_0} [/mm] $ mit $ |z| [mm] \geq n_0 [/mm] $ und $ z [mm] \in \mathbb [/mm] N $
Sei z=uvw eine Zerlegung von z mit: $|uv| [mm] \leq n_0$ [/mm] und $|v| [mm] \geq [/mm] 1$:
$z = uvw = [mm] 0^{2n_0} 1^{n_0} 0^{n_0} \Rightarrow [/mm] u = [mm] 0^{2n_0}, [/mm] v = [mm] 1^{n_0} [/mm] u = [mm] 0^{n_0} [/mm] $
So, jetzt hab ich da weitergemacht wo du aufgehört hast. Aber das ist doch auch blödsinn was da jetzt steht, oder? Wo soll ich denn da jetzt pumpen? Pumpen in v macht keinen Sinn weil wenn ich nun das v pumpe, dann ist jedes weitere Wort wieder in L, da es ja in der Sprache j=k+l heißt und das v quasi dem k entspricht und somit immer das richtige j rauskommt. Ich will ja das es falsch wird, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:14 Mo 04.06.2012 | | Autor: | Helbig |
> Sei z=uvw eine Zerlegung von z mit: [mm]|uv| \leq n_0[/mm] und [mm]|v| \geq 1[/mm]:
>
> [mm]z = uvw = 0^{2n_0} 1^{n_0} 0^{n_0} \Rightarrow u = 0^{2n_0}, v = 1^{n_0} u = 0^{n_0}[/mm]
> So, jetzt hab ich da weitergemacht wo du aufgehört hast.
> Aber das ist doch auch blödsinn was da jetzt steht, oder?
Ja! Die Implikation ist falsch! Es geht so weiter:
Sei [mm] $\,z=uvw$ [/mm] eine Zerlegung von z mit: [mm]|uv| \leq n_0[/mm] und [mm]|v| \geq 1[/mm].
Da [mm] $|uv|\le n_0$ [/mm] ist und $z$ mit [mm] $2*n_0$ [/mm] Nullen beginnt, besteht $uv$ nur aus Nullen.
So und nun schließe, daß $uv^2w$ nicht in $L$ liegt. Benutze dabei [mm] $v\ne\epsilon$.
[/mm]
Gruß,
Wolfgang
> Wo soll ich denn da jetzt pumpen? Pumpen in v macht keinen
> Sinn weil wenn ich nun das v pumpe, dann ist jedes weitere
> Wort wieder in L, da es ja in der Sprache j=k+l heißt und
> das v quasi dem k entspricht und somit immer das richtige j
> rauskommt. Ich will ja das es falsch wird, oder?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:25 Mo 04.06.2012 | | Autor: | bandchef |
Annahme: L ist regulär.
Sei $ [mm] n_0 [/mm] $ die Konstante des PL, dann gilt: $ [mm] n_0 \geq [/mm] 1 $ und $ [mm] n_o \in \mathbb [/mm] N $
$ z = [mm] 0^{2n_0} 1^{n_0} 0^{n_0} [/mm] $ mit $ |z| [mm] \geq n_0 [/mm] $ und $ z [mm] \in \mathbb [/mm] N $
Sei $ [mm] \,z=uvw [/mm] $ eine Zerlegung von z mit: $ |uv| [mm] \leq n_0 [/mm] $ und $ |v| [mm] \geq [/mm] 1 $:
$ z = [mm] \epsilon\ 0^{n_0} 0^{n_0} 1^{n_0} 0^{n_0} [/mm] $ mit $ u = [mm] \epsilon, [/mm] v = [mm] 0^{n_0} [/mm] w = [mm] 0^{n_0} 1^{n_0} 0^{n_0} [/mm] $
mit i=2:
$z = uv^2w = [mm] \epsilon\ \left(0^{n_0}\right)^2 0^{n_0} 1^{n_0} 0^{n_0} [/mm] = [mm] \epsilon\ 0^{2n_0} 0^{n_0} 1^{n_0} 0^{n_0} [/mm] = [mm] 0^{2n_0} 0^{n_0} 1^{n_0} 0^{n_0} [/mm] = z [mm] 0^{2n_0} \notin [/mm] L$, da [mm] $2n_0$-Nullen [/mm] zu viel vorkommen.
Edit: Falls das jetzt richtig sein sollte, sollte i=1 auch schon genügen um zu zeigen, dass L nicht regulär ist, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:20 Mo 04.06.2012 | | Autor: | Helbig |
> [mm]z = \epsilon\ 0^{n_0} 0^{n_0} 1^{n_0} 0^{n_0}[/mm] mit [mm]u = \epsilon, v = 0^{n_0} w = 0^{n_0} 1^{n_0} 0^{n_0}[/mm]
Falsch! Du darfst nicht $u$ und $v$ und $w$ auf irgendwas setzen! Das habe ich Dir jetzt schon so oft geschrieben. Ich habe keine Lust mehr.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:26 Di 05.06.2012 | | Autor: | bandchef |
Dass ich u,v und w nicht auf irgendwas setzen darf, ist mir schon klar. Es muss ja diese PL-Eigenschaft erfüllen. Das ist ja das seit Anfang an was ich nicht verstehe. Aber in meinem Beispiel ist doch nun $|uv| [mm] \leq [/mm] 1$. Warum ist das dann wieder falsch?
Zitat: "Da $ [mm] |uv|\le n_0 [/mm] $ ist und $ z $ mit $ [mm] 2\cdot{}n_0 [/mm] $ Nullen beginnt, besteht $ uv $ nur aus Nullen."
Genau hier ist doch schon was falsch gelaufen, oder? |uv| muss kleinergleich [mm] n_0 [/mm] sein. Da aber in meiner Zerlegung [mm] u^{2n_0} [/mm] steht kann |uv| nicht mehr kleinergleich [mm] n_0 [/mm] sein, weil ja schon [mm] $2\cdot n_0$ [/mm] dort steht, oder? Wie muss ich hier nun zerlegen, wenn schon die Variante die ich angegeben habe, dumm ist?
Zitat: "So und nun schließe, daß $ uv^2w $ nicht in $ L $ liegt. Benutze dabei $ [mm] v\ne\epsilon [/mm] $."
Gleiche Frage wie grad. Wie muss ich dann Zerlegen? Wenn man die Zerlegung hat, dann ist das Pumpen an sich kein Problem mehr...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:15 Di 05.06.2012 | | Autor: | Helbig |
>
> Zitat: "Da [mm]|uv|\le n_0[/mm] ist und [mm]z[/mm] mit [mm]2\cdot{}n_0[/mm] Nullen
> beginnt, besteht [mm]uv[/mm] nur aus Nullen."
>
> Genau hier ist doch schon was falsch gelaufen, oder? |uv|
> muss kleinergleich [mm]n_0[/mm] sein.
Nach dem PL ist [mm] $|uv|\le n_0$ [/mm] und fertig.
> Da aber in meiner Zerlegung
> [mm]u^{2n_0}[/mm] steht kann |uv| nicht mehr kleinergleich [mm]n_0[/mm] sein,
> weil ja schon [mm]2\cdot n_0[/mm] dort steht, oder? Wie muss ich
> hier nun zerlegen, wenn schon die Variante die ich
> angegeben habe, dumm ist?
Wenn ich [mm] $uvw=0^{2*n}1^n0^n$ [/mm] habe, so heißt das überhaupt nicht [mm] $uv=0^{2n}$! [/mm] Im Gegenteil, weil ja [mm] $|uv|\le [/mm] n$ ist, und $z$ mit $2n$ Nullen beginnt, ist $uv$ eine echtes Teilwort von [mm] $0^{2n}$ [/mm] und besteht damit nur aus Nullen. Wir wissen nicht aus wieviel Nullen. Wir wissen nur aus mindestens einer Null und höchstens $n$ Nullen.
> Zitat: "So und nun schließe, daß [mm]uv^2w[/mm] nicht in [mm]L[/mm] liegt.
> Benutze dabei [mm]v\ne\epsilon [/mm]."
>
> Gleiche Frage wie grad. Wie muss ich dann Zerlegen? Wenn
> man die Zerlegung hat, dann ist das Pumpen an sich kein
> Problem mehr...
Du darfst überhaupt nicht zerlegen, sondern mußt unabhängig von einer Zerlegung argumentieren.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:13 Sa 09.06.2012 | | Autor: | bandchef |
Zitat: "Wenn ich $ [mm] uvw=0^{2\cdot{}n}1^n0^n [/mm] $ habe, so heißt das überhaupt nicht $ [mm] uv=0^{2n} [/mm] $! Im Gegenteil, weil ja $ [mm] |uv|\le [/mm] n $ ist, und $ z $ mit $ 2n $ Nullen beginnt, ist $ uv $ eine echtes Teilwort von $ [mm] 0^{2n} [/mm] $ und besteht damit nur aus Nullen. Wir wissen nicht aus wieviel Nullen. Wir wissen nur aus mindestens einer Null und höchstens $ n $ Nullen."
Ich denke jetzt hab ich das ganze verstanden! Ich werde jetzt EIN MÖGLICHES Beispiel für ein mögiches [mm] $n_0$ [/mm] angeben:
[mm] n_0 [/mm] = 5:
Wenn jetzt [mm] $n_0$ [/mm] nun gleich 5 ist, dann sieht ein mögliches Wort, welches in der Sprache ist, so aus:
$z = 0000000000 11111 00000$
Da ich durch die PL-Eigenschaft weiß, dass das $|uv| [mm] \leq n_0$ [/mm] sein muss, könnte es doch so aussehen (Aber wohl gemerkt, wir wissen, nicht wie lang |uv| wirklich ist...; es könnte auch anders "gelegt" sein. z.B. nur drei 0en.):
$z = [mm] \overbrace{\overbrace{\underbrace{0000}_{=uv, \text{ da} \leq n_0}0}^{=n_0}00000}^{=2n_0} [/mm] 11111 00000$
Wenn ich jetzt den Beweis noch bis zum Ende mache, komm ich auf das hier:
$z = [mm] 0^{2n_0} 1^{n_0} 0^{n_0} [/mm] = [mm] 0^{n_0} 0^{n_0} 1^{n_0} 0^{n_0}$
[/mm]
mit i=2:
$z = uv^iw = [mm] 0^{n_0} \left(0^{n_0}\right)^2 1^{n_0} 0^{n_0} [/mm] = [mm] 0^{n_0} 0^{2n_0} 1^{n_0} 0^{n_0} [/mm] = [mm] 0^{n_0} [/mm] z [mm] \notin [/mm] L$, weil ein [mm] 0^{n_0} [/mm] zu viel!
mit $u = [mm] 0^{n_0}, [/mm] v = [mm] 0^{n_0}, [/mm] w = [mm] 1^{n_0} 0^{n_0}$
[/mm]
Passt das jetzt vielleicht?
Ich hoffe, du antwortest jetzt noch. Ich hatte die letzten Tage anderweitig sehr viel um die Ohren, weshalb nicht sofort antworten konnte! Danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:28 Sa 09.06.2012 | | Autor: | Helbig |
>
> Ich hoffe, du antwortest jetzt noch. Ich hatte die letzten
> Tage anderweitig sehr viel um die Ohren, weshalb nicht
> sofort antworten konnte! Danke!
Ich finde hier gar keine Frage auf die ich antworten könnte! Aber auf jeden Fall hast Du mich jetzt verstanden!
Weiter so!
Grüße Wolfgang
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:29 Sa 09.06.2012 | | Autor: | bandchef |
Sehr gut. Ich denke, es hat sich ein Edit überschnitten. Vielleicht magst du meine Frage nochmal neuladen, dann kannst du den Rest auch noch sehen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:56 Sa 09.06.2012 | | Autor: | Helbig |
> mit i=2:
>
> [mm]z = uv^iw = 0^{n_0} \left(0^{n_0}\right)^2 1^{n_0} 0^{n_0} = 0^{n_0} 0^{2n_0} 1^{n_0} 0^{n_0} = 0^{n_0} z \notin L[/mm],
> weil ein [mm]0^{n_0}[/mm] zu viel!
> mit [mm]u = 0^{n_0}, v = 0^{n_0}, w = 1^{n_0} 0^{n_0}[/mm]
>
> Passt das jetzt vielleicht?
>
Nein, das paßt jetzt wieder nicht, weil Du unzulässiger Weise [mm] $v=0^{n_0}$ [/mm] angenommen hast. Du darfst aber nur [mm] $v=0^k$ [/mm] annehmen, wobei [mm] $1\le [/mm] k$ ist, da $v$ nach dem PL von [mm] $\epsilon$ [/mm] verschieden ist.
Grüße,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:08 Sa 09.06.2012 | | Autor: | bandchef |
Hm ok, hab ich mir ja schon fast gedacht, dass es nicht richtig ist.
Du schreibst dass ich [mm] $v^k$ [/mm] mit $k [mm] \geq [/mm] 1$ schreiben muss. Wie notiert man das jetzt? Und was ist nun eigentlich das k? Dieses k taucht in meinen Unterlagen auch immer wieder auf, richtig verstanden hab ich das aber noch nicht. Nochmal alles:
Annahme: L ist regulär.
Sei $ [mm] n_0 [/mm] $ die Konstante des PL, dann gilt: $ [mm] n_0 \geq [/mm] 1 $ und $ [mm] n_o \in \mathbb [/mm] N $
$ z = [mm] 0^{2n_0} 1^{n_0} 0^{n_0} [/mm] $ mit $ |z| [mm] \geq n_0 [/mm] $ und $ z [mm] \in \mathbb [/mm] N $ sowie $z [mm] \in [/mm] L$
Sei $ [mm] \,z=uvw [/mm] $ eine Zerlegung von z mit: $ |uv| [mm] \leq n_0 [/mm] $ und $ |v| [mm] \geq [/mm] 1 $:
$ z = uvw = [mm] 0^{2n_0} 1^{n_0} 0^{n_0} [/mm] = [mm] 0^{n_0} 0^{n_0} 1^{n_0} 0^{n_0} [/mm] $ mit $ u = [mm] 0^{n_0}, [/mm] v = [mm] 0^{n_0}, [/mm] w = [mm] 1^{n_0} 0^{n_0} [/mm] $
(Stimmt's jetzt schon mal bis hierhin?)
mit i=2:
$z = uv^2w = [mm] 0^{n_0} \left(0^k\right)^2 1^{n_0} 0^{n_0}$
[/mm]
Ab hier muss ich also irgendwie mit diesem k notieren? Wie geht das dann?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:18 Sa 09.06.2012 | | Autor: | Helbig |
> [mm]z = uvw = 0^{2n_0} 1^{n_0} 0^{n_0} = 0^{n_0} 0^{n_0} 1^{n_0} 0^{n_0}[/mm]
> mit [mm]u = 0^{n_0}, v = 0^{n_0}, w = 1^{n_0} 0^{n_0}[/mm]
>
>
> (Stimmt's jetzt schon mal bis hierhin?)
Nein! Du hast schon wieder $v$ definiert. Und das darfst Du nicht!
Du mußt Deinen Beweis führen, ohne zu wissen, wie $u$, $v$, $w$ aussehen.
Bis jetzt wissen wir, daß $v$ aus einer oder mehr Nullen besteht und diese links von den Einsen stehen. Und wir wissen, daß [mm] $2n_0$ [/mm] Nullen links von [mm] $n_0$ [/mm] Einsen stehen und [mm] $n_0$ [/mm] Nullen rechts von den Einsen stehen, weil ja unser $z$ in der Sprache ist.
Was passiert, wenn Du pumpst? Also statt $uvw$ $uvvw$ schreibst. Wieviele Nullen stehen dann links von den Einsen? Ist $uvvw$ noch in der Sprache?
>
>
> mit i=2:
> [mm]z = uv^2w = 0^{n_0} \left(0^k\right)^2 1^{n_0} 0^{n_0}[/mm]
>
> Ab hier muss ich also irgendwie mit diesem k notieren? Wie
> geht das dann?
Das $k$ ist einfach die Länge von $v$.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:26 Sa 09.06.2012 | | Autor: | bandchef |
Annahme: L ist regulär.
Sei $ [mm] n_0 [/mm] $ die Konstante des PL, dann gilt: $ [mm] n_0 \geq [/mm] 1 $ und $ [mm] n_o \in \mathbb [/mm] N $
$ z = [mm] 0^{2n_0} 1^{n_0} 0^{n_0} [/mm] $ mit $ |z| [mm] \geq n_0 [/mm] $ und $ z [mm] \in \mathbb [/mm] N $ sowie $ z [mm] \in [/mm] L $
Sei $ [mm] \,z=uvw [/mm] $ eine Zerlegung von z mit: $ |uv| [mm] \leq n_0 [/mm] $ und $ |v| [mm] \geq [/mm] 1 $:
$ z = uvw = [mm] 0^{2n_0} 1^{n_0} 0^{n_0} [/mm] = [mm] 0^{n_0} 0^{n_0} 1^{n_0} 0^{n_0} [/mm] $
So jetzt sollte es bis hierhin ja stimmen. u, v und w hab ich nun NICHT definiert.
Zitat: "Bis jetzt wissen wir, daß v aus einer oder mehr Nullen besteht und diese links von den Einsen stehen. Und wir wissen, daß $ [mm] 2n_0 [/mm] $ Nullen links von $ [mm] n_0 [/mm] $ Einsen stehen und $ [mm] n_0 [/mm] $ Nullen rechts von den Einsen stehen, weil ja unser z in der Sprache ist."
Dass v aus einer oder mehr 0en besteht wissen wir wegen den Pumping-Lemma-Eigenschaft, da es ja heißt: $ |v| [mm] \geq [/mm] 1 $. [mm] "2n_0" [/mm] 0en links [mm] $n_0$ [/mm] 1en sowie [mm] $n_0$ [/mm] 0en rechts von den 1en ist auch klar, da somit das Wort z nach wie vor in der Sprache ist. Soweit hab ich das verstanden
Zitat: "Was passiert, wenn Du pumpst? Also statt uvw uvvw schreibst. Wieviele Nullen stehen dann links von den Einsen? Ist uvvw noch in der Sprache?"
Um deine Frage nach der Anzahl der 0en links von den 1en zu beantworten: Wenn ich nun mit i=2 pumpe, dann steht die doppelte Anzahl 0en links von den 1en.
Notationstechnisch sieht doch das dann so aus, dass mir das k also die Länge des zu pumpenden v's angibt. Richtig umsetzen kann ich das aber jetzt noch nicht. Ich weiß ja laut PL nur, dass $|v| [mm] \geq [/mm] 1$ sein muss, somit kann ich doch keine konkrete Aussage über die Länge machen, oder?
$z = uv^2w = uvvw = ...?$
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:02 Sa 09.06.2012 | | Autor: | Helbig |
> So jetzt sollte es bis hierhin ja stimmen. u, v und w hab
> ich nun NICHT definiert.
Ich bin stolz auf Dich!
>
> Zitat: "Bis jetzt wissen wir, daß v aus einer oder mehr
> Nullen besteht und diese links von den Einsen stehen. Und
> wir wissen, daß [mm]2n_0[/mm] Nullen links von [mm]n_0[/mm] Einsen stehen
> und [mm]n_0[/mm] Nullen rechts von den Einsen stehen, weil ja unser
> z in der Sprache ist."
>
> Dass v aus einer oder mehr 0en besteht wissen wir wegen den
> Pumping-Lemma-Eigenschaft, da es ja heißt: [mm]|v| \geq 1 [/mm].
> [mm]"2n_0"[/mm] 0en links [mm]n_0[/mm] 1en sowie [mm]n_0[/mm] 0en rechts von den 1en
> ist auch klar, da somit das Wort z nach wie vor in der
> Sprache ist. Soweit hab ich das verstanden
>
>
>
> Zitat: "Was passiert, wenn Du pumpst? Also statt uvw uvvw
> schreibst. Wieviele Nullen stehen dann links von den
> Einsen? Ist uvvw noch in der Sprache?"
>
> Um deine Frage nach der Anzahl der 0en links von den 1en zu
> beantworten: Wenn ich nun mit i=2 pumpe, dann steht die
> doppelte Anzahl 0en links von den 1en.
Fast! Da ein $v$ zusätzlich links von den Einsen steht, stehen dort [mm] $2*n_0+k$ [/mm] Nullen, also nicht doppelt soviele wie vorher.
>
> Notationstechnisch sieht doch das dann so aus, dass mir das
> k also die Länge des zu pumpenden v's angibt. Richtig
> umsetzen kann ich das aber jetzt noch nicht. Ich weiß ja
> laut PL nur, dass [mm]|v| \geq 1[/mm] sein muss, somit kann ich doch
> keine konkrete Aussage über die Länge machen, oder?
Nein, aber das brauchst Du auch nicht. Es reicht, daß die Nullen von $vv$ links von den Einsen stehen.
Wieviel Nullen stehen in $uvw$ links von den Einsen und wieviele in $uvvw$?
Du mußt Dir nur klarmachen, daß $uvvw$ nicht in $L$ liegt.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:15 Sa 09.06.2012 | | Autor: | bandchef |
Annahme: L ist regulär.
Sei $ [mm] n_0 [/mm] $ die Konstante des PL, dann gilt: $ [mm] n_0 \geq [/mm] 1 $ und $ [mm] n_o \in \mathbb [/mm] N $
$ z = [mm] 0^{2n_0} 1^{n_0} 0^{n_0} [/mm] $ mit $ |z| [mm] \geq n_0 [/mm] $ und $ z [mm] \in \mathbb [/mm] N $ sowie $ z [mm] \in [/mm] L $
Sei $ [mm] \,z=uvw [/mm] $ eine Zerlegung von z mit: $ |uv| [mm] \leq n_0 [/mm] $ und $ |v| [mm] \geq [/mm] 1 $:
$ z = uvw = [mm] 0^{2n_0} 1^{n_0} 0^{n_0} [/mm] = [mm] 0^{n_0} 0^{n_0} 1^{n_0} 0^{n_0} [/mm] $
mit i=2:
$ z = uv^2w = uvvw = ...?$ Dort wo diese 3 Punkte nun stehen muss ich ja eigentlich noch einen Ausdruck angeben. Wie mach ich das nun? Damit ich diesen Ausdruck hinschreiben kann, muss ich ja wissen wo in meinem Wort z ich die Schleife für's pumpen setzen muss. Dafür wiederum muss ich wissen welcher Teil das v ist!
Zitat: "Fast! Da ein $ v $ zusätzlich links von den Einsen steht, stehen dort $ [mm] 2\cdot{}n_0+k [/mm] $ Nullen, also nicht doppelt soviele wie vorher."
Ich gehe mal davon aus, dass das zustäzliche v links von den 1en durch das pumpen mit 2 kommt. Wo soll's auch anders herkommen?
Dieses $ [mm] 2\cdot{}n_0+k [/mm] $ kann ich jetzt noch nicht so ganz zu ordnen. Kommt dieses $2 [mm] \cdot n_0$ [/mm] nun durch das pumpen mit 2, oder ist das das $2 [mm] \cdot n_0$ [/mm] von der Sprache, dass von weiter oben noch gilt? Das dazu addierte k ist also die Länge des v's. Da laut PL-Eigenschaft $|v| [mm] \geq [/mm] 1$ sein muss, muss somit auch [mm] $k\geq [/mm] 1$ sein. Aber kommen durch das pumpen mit 2 nicht auch [mm] $2\cdot [/mm] k$ hinzu? Also komplett dann so: $ [mm] 2\cdot{}n_0+ 2\cdot [/mm] k $
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:04 Sa 09.06.2012 | | Autor: | Helbig |
> Dieses [mm]2\cdot{}n_0+k[/mm] kann ich jetzt noch nicht so ganz zu
> ordnen. Kommt dieses [mm]2 \cdot n_0[/mm] nun durch das pumpen mit
> 2, oder ist das das [mm]2 \cdot n_0[/mm] von der Sprache, dass von
> weiter oben noch gilt? Das dazu addierte k ist also die
> Länge des v's. Da laut PL-Eigenschaft [mm]|v| \geq 1[/mm] sein
> muss, muss somit auch [mm]k\geq 1[/mm] sein. Aber kommen durch das
> pumpen mit 2 nicht auch [mm]2\cdot k[/mm] hinzu? Also komplett dann
> so: [mm]2\cdot{}n_0+ 2\cdot k[/mm]
In dem Wort $uvw$ stehen links der Einsen [mm] $2*n_0$ [/mm] Nullen. Jetzt kommt links der Einsen ein weiteres $v$ hinzu und bring weitere $k$ Nullen in das Wort $uvvw$. Wieviele Nullen stehen jetzt links der Einsen?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:24 Sa 09.06.2012 | | Autor: | bandchef |
Zitat: "Wieviele Nullen stehen jetzt links der Einsen?"
Nun ja da hast du wohl recht gehabt! Es stehen natürlich $2 [mm] \cdot n_0 [/mm] + k$ 1en, da $|v| [mm] \geq [/mm] 1$ und die Länge von v mit k angegeben wird!
Wenn nun durch das Pumpen mit i=2 ein weiteres v der Länge k hinzukommt ist die Anzahl der 0en links der 1en um genau dieses k zu groß und somit ist nach dem Pumpen das Wort z nicht mehr in L enthalten.
Ich denke, dass ich das jetzt soweit verstanden habe. Aber was ist nun mit der Notation?
i=2:
$z = uv^2w = uvvw = ...?$
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:43 So 10.06.2012 | | Autor: | Helbig |
>
> Ich denke, dass ich das jetzt soweit verstanden habe. Aber
> was ist nun mit der Notation?
>
> i=2:
> [mm]z = uv^2w = uvvw = ...?[/mm]
Unser Beweis ist eigentlich fertig. Wir können, und ihr müßt wahrscheinlich, dies jetzt etwas anders schreiben, müssen dabei aber höllisch aufpassen, daß wir über die Zerlegung von $z=uvw$ nicht mehr festlegen, als nach Voraussetzung gegeben ist.
Aus Stilgründen sollten wir möglichst wenig Namen einfügen. Den Längen von $v$ und $u$ geben wir gar keine Namen. Es ist auch Blödsinn, die Konstante [mm] $n_0$ [/mm] zu nennen, wenn weit und breit kein [mm] $n_1$ [/mm] zu sehen ist. Wir nennen sie daher $n$.
Sei also [mm] $L=\bigl\{0^i1^j0^k:i=j+k\bigr\}$. [/mm] Wenn $L$ regulär wäre, gäbe es ein $n>0$, so daß es zu jedem [mm] $z\in [/mm] L$ mit [mm] $n\le [/mm] |z|$ eine Zerlegung $z=uvw$ gibt mit $0<|v|$, [mm] $|uv|\le [/mm] n$ und [mm] $uv^\* w\subseteq [/mm] L$.
Wir setzen [mm] $z=0^{2n}1^n0^n$. [/mm] Dann ist [mm] $z\in [/mm] L$ und [mm] $n\le [/mm] |z|$.
Sei $z=uvw$ eine Zerlegung nach dem PL. Weil [mm] $|uv|\le [/mm] n$ ist, gibt es ein [mm] $m\in \IN$ [/mm] mit [mm] $z=0^{2n}1^n0^n=uvw=0^{|u|}0^{|v|}0^m1^n0^n$.
[/mm]
(Ohne die Voraussetzung [mm] $|uv|\le [/mm] n$ könnte $v$ ja bis zu den Einsen reichen, und dann könnten wir $z$ nicht wie oben darstellen.)
Nach dem PL ist auch [mm] $uw=0^{|u|}0^m1^n0^n$ [/mm] in $L$.
Weil [mm] $\,|v|> [/mm] 0$ ist, ist $|u|+m=2n-|v| < 2n$ und daher ist $uw$ im Widerspruch zum PL nicht in $L$.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:17 So 10.06.2012 | | Autor: | bandchef |
Zitat: "Unser Beweis ist eigentlich fertig. Wir können, und ihr müßt wahrscheinlich, dies jetzt etwas anders schreiben, müssen dabei aber höllisch aufpassen, daß wir über die Zerlegung von z=uvw nicht mehr festlegen, als nach Voraussetzung gegeben ist.
Aus Stilgründen sollten wir möglichst wenig Namen einfügen. Den Längen von v und u geben wir gar keine Namen. Es ist auch Blödsinn, die Konstante $ [mm] n_0 [/mm] $ zu nennen, wenn weit und breit kein $ [mm] n_1 [/mm] $ zu sehen ist. Wir nennen sie daher n.
Sei also $ [mm] L=\bigl\{0^i1^j0^k:i=j+k\bigr\} [/mm] $. Wenn L regulär wäre, gäbe es ein n>0, so daß es zu jedem $ [mm] z\in [/mm] L $ mit $ [mm] n\le [/mm] |z| $ eine Zerlegung z=uvw gibt mit 0<|v|, $ [mm] |uv|\le [/mm] n $ und $ uv^* [mm] w\subseteq [/mm] L $."
Wir setzen $ [mm] z=0^{2n}1^n0^n [/mm] $. Dann ist $ [mm] z\in [/mm] L $ und $ [mm] n\le [/mm] |z| $."
Ich denke, diesen Formalismus inkl. aller textuellen Formulierungen kann ich wohl als "Standardgerüst" mitnehmen, oder? Aber muss man nicht noch irgendwie reinbringen, dass n die Konstante des PL ist? Haben wir in der Schule zumindestens immer.
Zitat: "Sei z=uvw eine Zerlegung nach dem PL. Weil $ [mm] |uv|\le [/mm] n $ ist, gibt es ein $ [mm] m\in \IN [/mm] $ mit $ [mm] z=0^{2n}1^n0^n=uvw=0^{|u|}0^{|v|}0^m1^n0^n [/mm] $."
(Ohne die Voraussetzung $ [mm] |uv|\le [/mm] n $ könnte v ja bis zu den Einsen reichen, und dann könnten wir z nicht wie oben darstellen.)
Nach dem PL ist auch $ [mm] uw=0^{|u|}0^m1^n0^n [/mm] $ in L.
Weil $ [mm] \,|v|> [/mm] 0 $ ist, ist |u|+m=2n-|v| < 2n und daher ist uw im Widerspruch zum PL nicht in L."
Das mit dem m hab ich in meinen Unterlagen bisher noch nie gelesen. Aber was in meinen Aufgaben, die wir auch in der Schule gelöst haben, immer drin war, eine Betrachtung die immer ein festes i (der Wert mit dem gepumpt weden soll) hatte. Das fehlt mir hier jetzt auf einmal. Anstatt arbeitest du aber mit dem "m". Wenn ich mir deinen Beweis durchlese verstehe ich den auch, könnte den aber niemals so selbst aufschreiben. Ich meine damit jetzt nicht das erste (Teil-)Zitat, sondern das Zweite.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:03 So 10.06.2012 | | Autor: | Helbig |
>
> Ich denke, diesen Formalismus inkl. aller textuellen
> Formulierungen kann ich wohl als "Standardgerüst"
> mitnehmen, oder?
Nein. Es gibt leider kein Standardgerüst. Jeder Beweis ist anders. Insbesondere, was die Schreibweise betrifft. Ob ich eine Variable nun $m$ oder $k$ oder gar nicht benenne ist reine Stilsache. Wichtig sind allein die logischen Schlüsse -- leserfreundlich dargestellt.
> Aber muss man nicht noch irgendwie
> reinbringen, dass n die Konstante des PL ist? Haben wir in
> der Schule zumindestens immer.
Habe ich doch auch reingebracht. "Wenn $L$ regulär wäre, gäbe es ein $n>0$ ..."
>
>
>
>
> Zitat: "Sei z=uvw eine Zerlegung nach dem PL. Weil [mm]|uv|\le n[/mm]
> ist, gibt es ein [mm]m\in \IN[/mm] mit
> [mm]z=0^{2n}1^n0^n=uvw=0^{|u|}0^{|v|}0^m1^n0^n [/mm]."
>
> (Ohne die Voraussetzung [mm]|uv|\le n[/mm] könnte v ja bis zu den
> Einsen reichen, und dann könnten wir z nicht wie oben
> darstellen.)
>
> Nach dem PL ist auch [mm]uw=0^{|u|}0^m1^n0^n[/mm] in L.
>
> Weil [mm]\,|v|> 0[/mm] ist, ist |u|+m=2n-|v| < 2n und daher ist uw
> im Widerspruch zum PL nicht in L."
>
> Das mit dem m hab ich in meinen Unterlagen bisher noch nie
> gelesen. Aber was in meinen Aufgaben, die wir auch in der
> Schule gelöst haben, immer drin war, eine Betrachtung die
> immer ein festes i (der Wert mit dem gepumpt weden soll)
> hatte. Das fehlt mir hier jetzt auf einmal. Anstatt
Ja. Dieses $i$ habe ich hier nicht gebraucht. Welchen Wert hätte es in meinem Beweis?
> arbeitest du aber mit dem "m". Wenn ich mir deinen Beweis
> durchlese verstehe ich den auch, könnte den aber niemals
> so selbst aufschreiben. Ich meine damit jetzt nicht das
> erste (Teil-)Zitat, sondern das Zweite.
Das mag schon sein. Hier hilft üben, üben, üben. Lies Dir andere Beweise durch, und schreibe sie mit eigenen Worten und Mitteln auf.
Viel Erfolg,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:30 So 10.06.2012 | | Autor: | bandchef |
Zitat: "Ja. Dieses i habe ich hier nicht gebraucht. Welchen Wert hätte es in meinem Beweis?"
Ich denke du hast hier nicht aufgepumpt, sondern mit i=0 runtergepumpt, weil du im Beweis schreibst, dass uw nicht in L ist.
Stimmt das so?
Edit: Ich hab hier übrigens ein Beispiel gefunden wie unser Dozent es in der Schule löst: http://s7.directupload.net/file/d/2917/xgoh8c2o_jpg.htm. Es ist zwar eine andere Aufgabe, aber irgendwie für mich durchsichtiger. Er teil das n in k1+k2+k3 auf und pumpt dann ein k an irgendeiner Stelle... Das übrigens auch das was ich vor ein paar Fragen auch versucht habe. Was sagst du hierzu?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:18 So 10.06.2012 | | Autor: | Helbig |
> Zitat: "Ja. Dieses i habe ich hier nicht gebraucht. Welchen
> Wert hätte es in meinem Beweis?"
>
> Ich denke du hast hier nicht aufgepumpt, sondern mit i=0
> runtergepumpt, weil du im Beweis schreibst, dass uw nicht
> in L ist.
>
> Stimmt das so?
Ja!
>
>
> Edit: Ich hab hier übrigens ein Beispiel gefunden wie
> unser Dozent es in der Schule löst:
> http://s7.directupload.net/file/d/2917/xgoh8c2o_jpg.htm. Es
> ist zwar eine andere Aufgabe, aber irgendwie für mich
> durchsichtiger. Er teil das n in k1+k2+k3 auf und pumpt
> dann ein k an irgendeiner Stelle... Das übrigens auch das
> was ich vor ein paar Fragen auch versucht habe. Was sagst
> du hierzu?
Ich habs aufgerufen. Dann kam Werbung. Und dann hab ich wieder geschlossen.
Aber wie auch immer. Dieses Aufteilen von $n$ mag in dem Beweis sinnvoll sein. Nochmal: Jeder Beweis ist anders! Es gibt kein Schema. Und es ist müßig, einen Beweis auf einen anderen schematisch zu übertragen.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:43 So 10.06.2012 | | Autor: | bandchef |
Wenn du nun i=1 gewählt hättest, hättest du nicht widerlegt, oder? Denn dann wäre ja das gleiche rausgekommen. Und somit wäre es noch in der Sprache gewesen, oder?
Ich würde mich dann noch gern um die andere Übungsteilaufgabe kümmern. Soll ich dazu einen neuen Thread aufmachen, oder willst du hier, vorausgesetzt, du hilfst mir überhaupt noch weiter...
Die Moderatoren in diesem Forum haben mich aber schon mal belehrt, dass man doch bitte pro Übungsaufgabe einen neuen Thread machen soll.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:51 So 10.06.2012 | | Autor: | Helbig |
> Wenn du nun i=1 gewählt hättest, hättest du nicht
> widerlegt, oder? Denn dann wäre ja das gleiche
> rausgekommen. Und somit wäre es noch in der Sprache
> gewesen, oder?
Richtig! Aber jedes andere $i$ funktioniert, weil dann ja immer $|v|*(i-1)$ Nullen links der Einsen hinzukommen bzw. verschwinden.
>
>
> Ich würde mich dann noch gern um die andere
> Übungsteilaufgabe kümmern. Soll ich dazu einen neuen
> Thread aufmachen, oder willst du hier, vorausgesetzt, du
> hilfst mir überhaupt noch weiter...
Mach mal lieber einen neuen Thread auf.
Viel Erfolg,
Wolfgang
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:14 So 10.06.2012 | | Autor: | bandchef |
Neuen Thread hab ich gerade eröffnet.
|
|
|
|
