Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:58 Di 11.09.2012 | | Autor: | Parkan |
| Aufgabe | | Zeigen Sie das die Sprache [mm]L= { a^k b^{2k}} | k \in \IN[/mm] nicht regulär ist. |
Ich bin nicht sicher ob ich das PL richtig verstanden habe und bitte meine Lösung zu Prügfen.
Ich wähle
u= leeres Wort
v = [mm]a^n[/mm]
w= [mm]b^{2n}[/mm]
Jetzt wähle ich ein i aus den Natürlichenzahlen mit dem ich das v potenziere.
i=2
Daraus folgt
[mm]uv^2w[/mm] = [mm]\epsilon* v^n v^n w = a^{2n}b^{2n}[/mm]
Dieses Wort ist aber nicht in L.
Danke
Janina
|
|
| |
|
Hallo Janina,
> Zeigen Sie das die Sprache [mm]L= { a^k b^{2k}} | k \in \IN[/mm]
> nicht regulär ist.
>
> Ich bin nicht sicher ob ich das PL richtig verstanden habe
> und bitte meine Lösung zu Prügfen.
>
> Ich wähle
> u= leeres Wort
> v = [mm]a^n[/mm]
> w= [mm]b^{2n}[/mm]
Du musst eine beliebige Zerlegung betrachten!
Der Beweis geht ja indirekt, du nimmst an, L wäre regulär.
Dann ex. diese Pumpingzahl n, so dass die Bedingungen des PL für alle Wörter [mm]x\in L[/mm] mit Länge mind. $n$ erfüllt sind.
Das müsste auch speziell für [mm]x=a^nb^{2n}[/mm] gelten.
[mm]|x|=3n[/mm] und sei [mm]x=uvw[/mm] eine bel. Zerlegung von x, die die Bedingungen des PL erfüllt.
Nun überlege mal, wie u und v aussehen müssen ...
> Jetzt wähle ich ein i aus den Natürlichenzahlen mit dem
> ich das v potenziere.
> i=2
> Daraus folgt
> [mm]uv^2w[/mm] = [mm]\epsilon* v^n v^n w = a^{2n}b^{2n}[/mm]
> Dieses Wort
> ist aber nicht in L.
So ähnlich ergibt sich das am Ende auch ...
>
> Danke
> Janina
>
>
Gruß
schachuzipus
|
|
|
|
