Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:49 Di 14.05.2013 | | Autor: | bandchef |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| Aufgabe | Zeigen oder widerlegen Sie, dass die folgende Sprache kontextfrei sind.
$L=\{0^{k^3}} 1^k|k \in \mathbb N_0\}$ |
Behauptung: L ist nicht kontextfrei.
Sei [mm]L[/mm] eine kontextfreie Sprache, dann gibt es eine
Konstante [mm]n \in \mathbb N[/mm], so dass sich jedes [mm]z \in L[/mm] mit
[mm]|z|\geq n[/mm], so als z=uvwxy schreiben lässt, dass [mm]|vwx|\leq n[/mm],
[mm]|vx|\geq 1[/mm] und [mm]u v^i w x^i y \in L[/mm] für alle [mm]i \geq 0[/mm]
gilt:
wähle: [mm] $z=0^{n^{3}}1^n$, [/mm] $|z| = [mm] n^3+n \leq [/mm] n$
Dieses Wort liegt genau dann nicht in L, wenn:
[mm] $n^3+n=|z|=|uvwxy|<|uv^2wx^2y| \leq n^3+n^2+n [/mm] < [mm] n^3+n^2+n+1$.
[/mm]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:10 Di 14.05.2013 | | Autor: | tobit09 |
Hallo bandchef,
> Zeigen oder widerlegen Sie, dass die folgende Sprache
> kontextfrei sind.
> Behauptung: L ist nicht kontextfrei.
Um welche Sprache $L$ geht es denn überhaupt? 
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:46 Mi 15.05.2013 | | Autor: | bandchef |
Oh entschuldige bitte. Da war ich wohl zu eifrig  Hab in der Frage die Sprache ergänzt!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 04:34 Do 16.05.2013 | | Autor: | tobit09 |
Hallo bandchef,
> Behauptung: L ist nicht kontextfrei.
Angenommen, L wäre kontextfrei.
> dann gibt es eine
> Konstante [mm]n \in \mathbb N[/mm], so dass sich jedes [mm]z \in L[/mm] mit
> [mm]|z|\geq n[/mm], so als z=uvwxy schreiben lässt, dass [mm]|vwx|\leq n[/mm],
> [mm]|vx|\geq 1[/mm] und [mm]u v^i w x^i y \in L[/mm] für alle [mm]i \geq 0[/mm]
> gilt:
>
> wähle: [mm]z=0^{n^{3}}1^n[/mm], [mm]|z| = n^3+n \leq n[/mm]
>
> Dieses Wort liegt genau dann nicht in L, wenn:
Glücklicherweise liegt das Wort $z$ auf jeden Fall in $L$.
Also existiert eine Zerlegung $z=uvwxy$ mit ...
> [mm]n^3+n=|z|=|uvwxy|<|uv^2wx^2y| \leq n^3+n^2+n < n^3+n^2+n+1[/mm].
Wie kommst du auf die Abschätzung bei dem [mm] $\leq$?
[/mm]
Die Idee, mit einer Abschätzung zu zeigen, dass [mm] $uv^2wx^2y\notin [/mm] L$, ist sehr elegant!
Wenn du zeigen kannst, dass
[mm] $n^3+n<|uv^2wx^2y|<(n+1)^3+(n+1)$,
[/mm]
kann $|uv^2wx^2y|$ nicht von der Form [mm] $k^3+k$ [/mm] für ein [mm] $k\in\IN_0$ [/mm] sein. Also kann $uv^2wx^2y$ nicht in $L$ liegen.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:26 Do 16.05.2013 | | Autor: | bandchef |
Ich probier's nochmal. Ich werde allerdings jetzt nur den letzten Schritt, die Abschätzung hinschreiben:
[mm]n^3+n=|z|=|uvwxy|<|uv^2wx^2y| \leq n^3+n+2n < (n+1)^3+(n+1) = n^3+3n^2+4n+2[/mm]
D.h.: $|uv^2wx^2y|$, ist eine Zahl der Form [mm] $n^3+n$ [/mm] die zwischen [mm] $n^3+n$ [/mm] und [mm] $n^3+3n^2+4n+2$ [/mm] liegt. Widerspruch!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:56 Fr 17.05.2013 | | Autor: | tobit09 |
> Ich probier's nochmal. Ich werde allerdings jetzt nur den
> letzten Schritt, die Abschätzung hinschreiben:
>
> [mm]n^3+n=|z|=|uvwxy|<|uv^2wx^2y| \leq n^3+n+2n < (n+1)^3+(n+1) = n^3+3n^2+4n+2[/mm]
>
> D.h.: [mm]|uv^2wx^2y|[/mm], ist eine Zahl der Form [mm]n^3+n[/mm] die
> zwischen [mm]n^3+n[/mm] und [mm]n^3+3n^2+4n+2[/mm] liegt. Widerspruch!
![[ok]](/images/smileys/ok.gif "[ok]")
|
|
|
|
