Pumping Lemma ktf < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
in dem Beweis für das Pumping Lemma für kontextfreie Sprachen, wie z.B. hier http://de.wikipedia.org/wiki/Pumping-Lemma wird am Anfang eine Variable k= [mm] 2^{Anzahl der Nichtterminale} [/mm] gesetzt. Warum?
Kommt das daher, weil die Grammatik in CNF sein muss und da höchstens zwei Nichtterminale auf der rechten Seite sein dürfen? Das steht nämlich nirgendwo erklärt.
Und das Ende des Beweises verstehe ich auch nicht richtig. Wie kommt man dann auf die Worteinteilung w=uvxyz ? Warum genau 5 Teilwörter?
Liebe Grüße
Judith
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:04 Sa 14.01.2012 | | Autor: | felixf |
Hallo Judith
> in dem Beweis für das Pumping Lemma für kontextfreie
> Sprachen, wie z.B. hier
> http://de.wikipedia.org/wiki/Pumping-Lemma wird am Anfang
> eine Variable k= [mm]2^{Anzahl der Nichtterminale}[/mm] gesetzt.
> Warum?
Weil der Ableitungsbaum eines Wortes der Laenge [mm] $\ge [/mm] k$ mindestens $k$ Nodes umfasst.
Ein Baum mit maximal vielen Elementen, der Blaetter in der Tiefe $h$ hat aber keines der Tiefe $h + 1$ (es gibt also einen Pfad [mm] $v_0, v_1, \dots, v_h$ [/mm] mit [mm] $v_i$ [/mm] in der Hoehe $i$) hat hoechstens $1 + 2 + 4 + 8 + [mm] \dots [/mm] + [mm] 2^h [/mm] = [mm] 2^{h+1} [/mm] - 1$ viele Nodes.
Wenn $h$ die maximale Hoehe ist, die im Ableitungsbaum vom Wort $x$ auftritt, dann gilt also [mm] $2^{h+1} [/mm] - 1 [mm] \ge [/mm] $ der Anzahl der Nodes im Ableitungsbaum. Da diese [mm] $\ge [/mm] |x| = [mm] 2^{|N|}$ [/mm] ist, folgt also [mm] 2^{h+1} [/mm] - 1 [mm] \ge 2^{|N|}$. [/mm] Dies impliziert $h + 1 > |N|$, also $h [mm] \ge [/mm] |N|$.
Es gibt also einen Pfad im Ableitungsbaum [mm] $v_0, \dots, v_h$ [/mm] mit [mm] $v_i$ [/mm] auf Hoehe $i$ und mit $h [mm] \ge [/mm] |N|$. Da man [mm] $v_0, \dots, v_h$ [/mm] Elementen aus $N$ zuordnen kann, muss es nach dem Taubenschlagprinzip mindestens zwei Indices $0 [mm] \le [/mm] i < j [mm] \le [/mm] h$ geben so dass [mm] $v_i$ [/mm] und [mm] $v_j$ [/mm] das Gleiche Element aus $N$ zugeordnet bekommen.
Wenn du $n$ als etwas kleineres als [mm] $2^{|N|}$ [/mm] waehlst, kann $h < |N|$ sein (so das trotzdem [mm] $2^{h+1} [/mm] - 1 [mm] \ge [/mm] n$ gilt). In dem Fall kann es sein, dass es keinen solchen Pfad im Ableitungsbaum gibt, so dass [mm] $v_i, v_j$ [/mm] das gleiche Element aus $N$ zugeordnet bekommen fuer $i < j$.
> Kommt das daher, weil die Grammatik in CNF sein muss und
> da höchstens zwei Nichtterminale auf der rechten Seite
> sein dürfen? Das steht nämlich nirgendwo erklärt.
Schau dir mal aus, wie so ein Ableitungsbaum aussieht fuer eine Grammatik in CNF.
> Und das Ende des Beweises verstehe ich auch nicht richtig.
> Wie kommt man dann auf die Worteinteilung w=uvxyz ? Warum
> genau 5 Teilwörter?
Hast du dir die Grafik auf der Wikiseite mal angeschaut? Also ![[]](/images/popup.gif) diese hier?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:34 Mo 16.01.2012 | | Autor: | judithlein |
Ok. Ich denke ich habe es. Ansonsten frage ich hier noch mal.
Danke!
|
|
|
|
![[]](http://de.wikipedia.org/w/index.php?title=Datei:Pumping_Lemma_f%C3%BCr_kontextfreie_Sprachen.svg&filetimestamp=20110213181300){kind=small}
diese hier