Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:20 So 28.04.2013 | | Autor: | bandchef |
| Aufgabe | Zeigen oder widerlegen Sie, dass die folgenden Sprachen regulär sind.
[mm] $L_2=\{0^k^3 | k \in \mathbb N_0\}$ [/mm] |
Hi Leute!
Wieder eine Aufgabe zum PL, das aber diesesmal wohl wirklich nicht regulär sein sollte.
Meine Lösung:
Sei L regulär, dann gibt es eine [mm] $n\in \mathbb [/mm] N$ mit der Eigenschaft das [mm] $\forall [/mm] z [mm] \in [/mm] L$, gilt: Es ex. eine Zerlegung von Z in uvw, d.h. z=uvw, mit [mm] $|uv|\leq [/mm] n$, $|v| [mm] \geq [/mm] 1$, $uv^iw$ mit $i [mm] \in \mathbb [/mm] N$.
Ich wähle: [mm] $z=a^{n^{3}} \in [/mm] L$, da: [mm] $|z|=n^3 \geq [/mm] n$
[mm] $n^3 [/mm] = |z| = |uvw| < |uv^2w| [mm] \leq n^3+n^2 [/mm] < [mm] n^3+2n^2+1$
[/mm]
Somit gilt: $uv^iw=uv^2w [mm] \notin [/mm] L$
Stimmt das soweit?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:07 Mo 29.04.2013 | | Autor: | tobit09 |
Hallo bandchef,
> [mm]L_2=\{0^k^3 | k \in \mathbb N_0\}[/mm]
> Wieder eine Aufgabe zum PL, das aber diesesmal wohl
> wirklich nicht regulär sein sollte.
(Wenn es [mm] $(0^k)^3$ [/mm] oder [mm] $0^{k3}$ [/mm] heißen soll (was gleichbedeutend wäre), ist die Sprache regulär.)
Vermutlich meinst du aber [mm] $0^{(k^3)}$.
[/mm]
> Meine Lösung:
>
>
> Sei L regulär, dann gibt es eine [mm]n\in \mathbb N[/mm] mit der
> Eigenschaft das [mm]\forall z \in L[/mm], gilt:
Nein, nur für die [mm] $z\in [/mm] L$ mit [mm] $|z|\ge [/mm] n$.
> Es ex. eine
> Zerlegung von Z in uvw, d.h. z=uvw, mit [mm]|uv|\leq n[/mm], [mm]|v| \geq 1[/mm],
> [mm]uv^iw[/mm] mit [mm]i \in \mathbb N[/mm].
Nicht "mit" [mm] $i\in\IN$, [/mm] sondern für ALLE [mm] $i\in\IN$!
[/mm]
> Ich wähle: [mm]z=a^{n^{3}} \in L[/mm], da: [mm]|z|=n^3 \geq n[/mm]
Das $a$ soll eine $0$ sein, nehme ich mal an... 
Dann gibt es eine Aufteilung $z=uvw$ mit ...
> [mm]n^3 = |z| = |uvw| < |uv^2w| \leq n^3+n^2 < n^3+2n^2+1[/mm]
Das [mm] "$\leq$" [/mm] ist mir etwas unklar (wenn auch nicht falsch).
[mm] $|uv^2w|=|u|+|v|+|v|+|w|=\underbrace{|uvw|}_{=n^3}+\underbrace{|v|}_{\le|uv|\le n}\le n^3+n$
[/mm]
> Somit gilt: [mm]uv^iw=uv^2w \notin L[/mm]
Warum gilt [mm] $uv^2w\notin [/mm] L$?
Wenn du
(*) [mm] $n^3<|uv^2w|<(n+1)^3$
[/mm]
zeigen kannst, kannst du wie folgt argumentieren:
Wäre [mm] $uv^2w\in [/mm] L$, so gäbe es ein [mm] $k\in\IN_0$ [/mm] mit [mm] $uv^2w=0^{k^3}$, [/mm] insbesondere [mm] $|uv^2w|=k^3$.
[/mm]
Im Falle [mm] $k\le [/mm] n$ hätten wir [mm] $|uv^2w|=k^3\le n^3$, [/mm] Widerspruch zu (*).
Im Falle $k>n$ hätten wir [mm] $k\ge [/mm] n+1$ und damit [mm] $|uv^2w|=k^3\ge (n+1)^3$, [/mm] Widerspruch zu (*).
> Stimmt das soweit?
![[ok]](/images/smileys/ok.gif "[ok]") Ja!
Viele Grüße
Tobias
|
|
|
|
