Pump Lemma kontextfrei < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Zeigen oder widerlegen Sie, dass die folgende Sprache kontextfrei sind.
[mm] $L=\{1^n0^m1^k|n,m,k \in \mathbb N_0 \text{ und } n |
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=1^n 0^{n+1} 1^{n+2} \in [/mm] L, |z| = n+(n+1)+(n+2) = 3n+3 [mm] \geq [/mm] n$
Wenn ich |vwx| in den vordersten Wortteil lege (also in die 1en) und dort aufpumpe, passt das gepumpte Wort nicht mehr zur Forderung, dass n<m (bzw. die Länge der Nullen ist nicht mehr kleiner als die Länge der nachfolgenden 1en) sein muss, womit ich einen Widerspruch habe und $uv^2wx^2y [mm] \notin [/mm] L$ gilt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Di 21.05.2013 | | Autor: | bandchef |
Ich pushe ja ungerne, aber kann mir vielleicht jemand sagen, ob ich mit meiner Lösung am richtigen Weg bin?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:33 Do 23.05.2013 | | Autor: | tobit09 |
Hallo bandchef,
> [mm]L=\{1^n0^m1^k|n,m,k \in \mathbb N_0 \text{ und } n
>
>
>
> Behauptung: L ist nicht kontextfrei.
![[ok]](/images/smileys/ok.gif "[ok]")
Angenommen $L$ wäre kontextfrei.
Das ergänze ich dir jetzt zum gefühlt 10. Mal. Es wäre schön, wenn du die Widerspruchsannahme in Zukunft selbst formulieren würdest. Also nicht die allgemeine Formulierung des Pumping Lemmas notieren, sondern:
Angenommen, unser $L$ wäre kontextfrei. Dann gäbe es nach dem Pumping Lemma ein [mm] $n\in\IN$, [/mm] so dass...
> 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=1^n 0^{n+1} 1^{n+2} \in L, |z| = n+(n+1)+(n+2) = 3n+3 \geq n[/mm]
Gute Wahl!
> Wenn ich |vwx| in den vordersten Wortteil lege (also in die
> 1en) und dort aufpumpe, passt das gepumpte Wort nicht mehr
> zur Forderung, dass n<m (bzw. die Länge der Nullen ist
> nicht mehr kleiner als die Länge der nachfolgenden 1en)
> sein muss, womit ich einen Widerspruch habe und [mm]uv^2wx^2y \notin L[/mm]
> gilt.
Damit hast du korrekt den Spezialfall behandelt, dass vwx im vordersten Wortteil liegt. Nun gilt es, sämtliche andere denkbaren Fälle durchzugehen.
(Denk daran: Nicht die Zerlegung selbst wählen, sondern eine beliebig vorgegebene entgegennehmen.)
Ich habe gerade leider keine Zeit, mir Gedanken zu machen, wie man alle denkbaren Zerlegungen am geschicktesten in möglichst wenige aber dennoch jeweils handhabbare Fälle aufteilt. Daher lasse ich die Frage mal als nur teilweise beantwortet markiert.
Dies soll dich jedoch nicht daran hindern, selbst verschiedene Fälle durchzuspielen, bis du hoffentlich alle erfasst hast.
Viele Grüße
Tobias
|
|
|
|
