Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:27 Do 28.07.2011 | | Autor: | GK13 |
| Aufgabe | | Zeige, dass die Sprache L = [mm] {a^{p}| p \in \IN ist Primzahl} [/mm] nicht regulär ist. |
Hallo!
Ich habe Probleme mit dem Pumping Lemma.
Ich habe das Prinzip verstanden; auch, warum die best. Eigenschaften zutreffen müssen, aber wenn ich selbst vor eine Aufgabe sitze, weiß ich nicht weiter.
Ich hab den Beweis auch schon im Internet gefunden, aber leider kann ich ihn nicht nachvollziehen.
Ich will also einen Widerspruchsbeweis führen, soweit, so gut.
Sei k [mm] \in \IN [/mm] Pumping Konstante.
Ich wähle mir also ein beliebiges Wort w [mm] \in [/mm] L mit |w| [mm] \ge [/mm] k, mit
|uv| [mm] \le [/mm] k und |v| [mm] \ge [/mm] 1.
Und jetzt steh ich ein bisschen doof da.
Ich weiß, dass ich jetzt aus den zwei Bedingungen etwas folgern muss und am Ende vermutlich darauf komme, dass es so keine Primzahl mehr sein kann..
kann mir vielleicht jemand weiterhelfen? Ich weil meine Erklärungen sind etwas dürfitg, aber ich hab mir wirklich schon viel dazu durchgelesen und versteh es einfach nicht!
Lg
GK13
|
|
| |
|
Hallo GK13,
> Zeige, dass die Sprache L = [mm]{a^{p}| p \in \IN ist Primzahl}[/mm]
> nicht regulär ist.
> Hallo!
>
> Ich habe Probleme mit dem Pumping Lemma.
> Ich habe das Prinzip verstanden; auch, warum die best.
> Eigenschaften zutreffen müssen, aber wenn ich selbst vor
> eine Aufgabe sitze, weiß ich nicht weiter.
> Ich hab den Beweis auch schon im Internet gefunden, aber
> leider kann ich ihn nicht nachvollziehen.
Wo und was genau konntest du daran nicht nachvollziehen?
Es läuft doch darauf hinaus, dass du ein w hernimmst, es geeignet "aufpumpst", so dass dann die Wortlänge des aufgepumpten Wortes nicht mehr prim ist.
> Ich will also einen Widerspruchsbeweis führen, soweit, so
> gut.
> Sei k [mm]\in \IN[/mm] Pumping Konstante.
> Ich wähle mir also ein beliebiges Wort w [mm]\in[/mm] L mit |w| [mm]\ge[/mm] k, mit
> |uv| [mm]\le[/mm] k und |v| [mm]\ge[/mm] 1.
> Und jetzt steh ich ein bisschen doof da.
> Ich weiß, dass ich jetzt aus den zwei Bedingungen etwas
> folgern muss und am Ende vermutlich darauf komme, dass es
> so keine Primzahl mehr sein kann..
Genau!
Wenn du dir ein [mm]w\in L[/mm], [mm] $w=a^p$ [/mm] mit [mm]|w|=p\ge k+2[/mm] hernimmst (wieso geht das? p muss ja prim sein ...)
und eine Zerlegung [mm]w=uvx[/mm] mit [mm]|uv|\le k[/mm] und natürlich [mm]v\neq\varepsilon[/mm], dann ist [mm]\red{|ux|\ge 2}[/mm].
Ist dir klar, warum?
Dann schaue dir das aufgepumpte Wort [mm]uv^{|ux|}x[/mm] an und seine Länge (zeigen willst du, dass die Länge keine Primzahl ist):
[mm]\left|uv^{|ux|}x\right|=|ux|+|ux|\cdot{}|v|[/mm]
Klar, wieso?
[mm]=\underbrace{\red{|ux|}}_{\ge 2}\cdot{}\underbrace{(1+|v|)}_{\ge 2, \ \text{da} \ |v|\neq\varepsilon, \ \text{also} \ |v|\ge 1}[/mm]
Also ist die Länge des so aufgepumpten Wortes ein Produkt aus zwei Faktoren, die beide [mm]\ge 2[/mm] sind, das kann also keine Primzahl sein.
Damit hast du den gewünschten Widerspruch und deine Annahme ist falsch.
[mm]L[/mm] ist also nicht regulär
> kann mir vielleicht jemand weiterhelfen? Ich weil meine
> Erklärungen sind etwas dürfitg, aber ich hab mir wirklich
> schon viel dazu durchgelesen und versteh es einfach nicht!
>
> Lg
>
> GK13
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:44 Do 28.07.2011 | | Autor: | GK13 |
Vielen Dank für die superschnelle Antwort.
Ich habs trotzdem noch nicht ganz durchstiegen.
> Genau!
>
> Wenn du dir ein [mm]w\in L[/mm], [mm]w=a^p[/mm] mit [mm]|w|=p\ge k+2[/mm] hernimmst
> (wieso geht das? p muss ja prim sein ...)
>
und k könnte 0 sein, und daher k+2?
> und eine Zerlegung [mm]w=uvx[/mm] mit [mm]|uv|\le k[/mm] und natürlich
> [mm]v\neq\varepsilon[/mm], dann ist [mm]\red{|ux|\ge 2}[/mm].
>
> Ist dir klar, warum?
nicht wirklich. ich weiß jetzt |uv| [mm] \le [/mm] k und v [mm] \ne \epsilon, [/mm] wieso kann ich dann auf |ux| schließen?
> Dann schaue dir das aufgepumpte Wort [mm]uv^{|ux|}x[/mm] an und
> seine Länge (zeigen willst du, dass die Länge keine
> Primzahl ist):
Warum Pumpe ich jetzt mit |ux|?? Das versteh ich nicht ganz, allgemein, welche Zahl ich zum pumpen nehmen soll.
>
> [mm]\left|uv^{|ux|}x\right|=|ux|+|ux|\cdot{}|v|[/mm]
>
> Klar, wieso?
Leider schon wieder nicht..
>
> [mm]=\underbrace{\red{|ux|}}_{\ge 2}\cdot{}\underbrace{(1+|v|)}_{\ge 2, \ \text{da} \ |v|\neq\varepsilon, \ \text{also} \ |v|\ge 1}[/mm]
Ab hier versteh ich es wieder und auch, warum es keine Primzahl sein kann!
Kannst du mir bei den anderen Teilen nochmal weiterhelfen?!
Ach und allgemein fiel mir noch die Frage ein, ob es nun wichtig ist, ob ich auf- oder abpumpe, oder ob eines "reicht" bzw in manchen Fällen nur eines richtig ist?!
Lg!
|
|
|
| |
|
Hallo nochmal,
musste gerade ein wenig knechten, daher die späte Antwort ...
> Vielen Dank für die superschnelle Antwort.
> Ich habs trotzdem noch nicht ganz durchstiegen.
>
>
> > Genau!
> >
> > Wenn du dir ein [mm]w\in L[/mm], [mm]w=a^p[/mm] mit [mm]|w|=p\ge k+2[/mm] hernimmst
> > (wieso geht das? p muss ja prim sein ...)
> >
> und k könnte 0 sein, und daher k+2?
>
> > und eine Zerlegung [mm]w=uvx[/mm] mit [mm]|uv|\le k[/mm] und natürlich
> > [mm]v\neq\varepsilon[/mm], dann ist [mm]\red{|ux|\ge 2}[/mm].
> >
> > Ist dir klar, warum?
>
> nicht wirklich. ich weiß jetzt |uv| [mm]\le[/mm] k und v [mm]\ne \epsilon,[/mm]
> wieso kann ich dann auf |ux| schließen?
Na, das gesamte Wort [mm]uvx[/mm] soll mindestens Länge [mm]k+2[/mm] haben, also [mm]|w|=|uvx|\ge k+2[/mm].
Das Teilwort [mm]uv[/mm] darf nach dem PL höchstens Länge [mm]k[/mm] haben, also [mm]|uv|\le k[/mm]
Dann muss der Rest, also [mm]x[/mm] doch mindestens Länge 2 haben, also [mm]|x|\ge 2[/mm], damit gilt doch erst recht für das noch längere Wort [mm]ux[/mm], dass [mm]|ux|\ge 2[/mm] ist.
>
> > Dann schaue dir das aufgepumpte Wort [mm]uv^{|ux|}x[/mm] an und
> > seine Länge (zeigen willst du, dass die Länge keine
> > Primzahl ist):
>
> Warum Pumpe ich jetzt mit |ux|??
Weil es klappt ...
> Das versteh ich nicht
> ganz, allgemein, welche Zahl ich zum pumpen nehmen soll.
Das ist die Crux, da gibt es kein Patentrezept.
Da muss man etwas rumbasteln. Ich habe mir diesen Trick auch nicht selber überlegt, sondern mir einen Beweis zu der Aufgabe angesehen ...
>
> >
> > [mm]\left|uv^{|ux|}x\right|=|ux|+|ux|\cdot{}|v|[/mm]
> >
> > Klar, wieso?
>
> Leider schon wieder nicht..
Na, das sollte aber doch klar sein...
Ein Wort [mm]abc[/mm] hat die Länge [mm]|abc|[/mm].
Und das setzt sich doch zusammen aus der Summe der Länge der Einzelteile
[mm]|abc|=|a|+|b|+|c|[/mm] oder auch [mm]=|ab|+|c|[/mm] oder [mm]|ac|+|b|[/mm] ...
Bsp.: nehmen wir ein Wort über dem Alphabet [mm]\Sigma=\{0,1\}[/mm], etwa [mm]abc[/mm] mit [mm]a=11[/mm], [mm]b=000[/mm], [mm]c=1[/mm]
Also [mm]abc=110001[/mm] und damit [mm]|abc|=6[/mm]
Jetzt schaue dir die "Zerlegungen", die ich oben hingeschrieben habe, mal an.
Im Beweis folgt in einem Zwischenschritt erstmal
[mm]\left|uv^{|ux|}x\right|=\left|ux\right|+\left|v^{|ux|}\right|[/mm]
Und [mm]v^{|ux|}[/mm] bedeutet ja einfach [mm]|ux|[/mm]-mal [mm]v[/mm] aneinandergereiht, also [mm]\underbrace{vvv...v}_{|ux|-mal}[/mm]
Wenn [mm]v[/mm] also die Länge [mm]|v|[/mm] hat, dann hat [mm]v^{|ux|}[/mm] folglich die Länge [mm]\left|v^{|ux|}\right|=|ux|\cdot{}|v|[/mm]
>
> >
> > [mm]=\underbrace{\red{|ux|}}_{\ge 2}\cdot{}\underbrace{(1+|v|)}_{\ge 2, \ \text{da} \ |v|\neq\varepsilon, \ \text{also} \ |v|\ge 1}[/mm]
>
> Ab hier versteh ich es wieder und auch, warum es keine
> Primzahl sein kann!
> Kannst du mir bei den anderen Teilen nochmal
> weiterhelfen?!
> Ach und allgemein fiel mir noch die Frage ein, ob es nun
> wichtig ist, ob ich auf- oder abpumpe,
Was meinst du mit "abpumpen"?
Wenn du den Mittelteil, also [mm]v[/mm] "hoch 0" nimmst, also [mm]uv^0x[/mm] betrachtest?
> oder ob eines
> "reicht" bzw in manchen Fällen nur eines richtig ist?!
Für die Gültigkeit des PL muss ja für jedes [mm]i\in\IN_0[/mm] das Wort [mm]uv^{i}x[/mm] in L liegen.
Du musst also im Widerspruchsbeweis irgendwie ein [mm]i\in\IN_0[/mm] finden, so dass [mm]uv^{i}x[/mm] nicht mehr zur Sprache gehört.
Hier tut es halt [mm]i=|ux|[/mm]
>
> Lg!
Gruß
schachuzipus
|
|
|
|
