Pumping Lemma regulär < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Beweisen oder widerlegen sie regularität: [mm] $L=\{0^{k^3}| k\in \mathbb N\} [/mm] |
Behauptung: L ist regulär.
Sei L regulär, dann gibt es ein $n [mm] \in \mathbb [/mm] N$ so dass sich jedes $z [mm] \in [/mm] L$ mit [mm] $\|z| \leq [/mm] n$ so als $z=uvw$ schreiben lässt, dass [mm] $|uv|\leq [/mm] n$, $|v| [mm] \geq [/mm] 1$ und $uv^iw$ für alle $i [mm] \geq [/mm] 0$ gilt:
wähle: [mm] $z=0^{n^3}$, [/mm] $|z| = [mm] n^3 \geq [/mm] n$
[mm] $n^3 [/mm] = |z| = |uvw| < |uv^2w| [mm] \leq n^3+n [/mm] < [mm] (n+1)^3$
[/mm]
D.h.: $|uv^2w| ist eine kubische Zahl zwischen [mm] $n^3$ [/mm] und [mm] $(n+1)^3$. [/mm] Widerspruch!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Sa 18.05.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:09 So 19.05.2013 | | Autor: | tobit09 |
Hallo bandchef,
vielleicht bist du ja trotz abgelaufener Fälligkeit noch an einer Reaktion interessiert:
> Beweisen oder widerlegen sie regularität: [mm]$L=\{0^{k^3}| k\in \mathbb N\}[/mm]
>
> Behauptung: L ist regulär.
Da hast du das Wort "nicht" vergessen.
Angenommen, L wäre regulär.
>
> Sei L regulär, dann gibt es ein [mm]n \in \mathbb N[/mm] so dass
> sich jedes [mm]z \in L[/mm] mit [mm]\|z| \leq n[/mm] so als [mm]z=uvw[/mm] schreiben
> lässt, dass [mm]|uv|\leq n[/mm], [mm]|v| \geq 1[/mm] und [mm]uv^iw[/mm]
[mm] "$\in [/mm] L$" nicht vergessen.
> für alle [mm]i \geq 0[/mm]
> gilt:
>
> wähle: [mm]z=0^{n^3}[/mm], [mm]|z| = n^3 \geq n[/mm]
>
> [mm]n^3 = |z| = |uvw| < |uv^2w| \leq n^3+n < (n+1)^3[/mm]
>
> D.h.: $|uv^2w| ist eine kubische Zahl zwischen [mm]$n^3$[/mm] und
> [mm]$(n+1)^3$.[/mm] Widerspruch!
![[ok]](/images/smileys/ok.gif "[ok]") Außer den Flüchtigkeitsfehlern alles richtig!
Viele Grüße
Tobias
|
|
|
|
