F2 Blatt11 Aufgabe 11.1
2004-06-26 16:54
Anonymer User
Hi Leute,
versuche gerade F2 Aufgaben zu bearbeiten und hab ein paar Probleme mit der Anwendung des Pumping-Lemmas der kontextfreien Sprachen.
Mein Wissenstand:
Also gegeben ist ja immer eine Sprache.
Mit dem Pumping Lemma kann man nur beweisen, dass eine Sprache nicht kontextfrei ist. Das natürlich nicht ausschliesst, dass es auch nicht kontextfreie Sprachen gibt, die die Pumping-Lemma Eigenschaften erfüllen.
Das Pumping-Lemma:
Für jede kontextfreie Sprache L aus Cf gibt es eine Zahl n aus N, so dass jedes Wort z aus L mit |z| >= n eine Zerlegung z = uvwxy besitzt, für die golgendes gilt:
(i): |vx|>=1
(ii): |vwx|<= n (n:= 2^k, k=|Vn|)
(iii): für alle i>=0 u v^i w x^i y aus L
(|z| ist genau die Anzahl der Knoten mit genau einem Nachfolger und u, v, w, x, y sind doch Teilwörter von z, oder?)
Nun die gegebene Sprache in 11.1 ist:
L11.1:={a^r b^s c^t| r,s,t aus N : (r+s = 2*t) und (s =< r)}
L11.1 lexikalisch geordnet:
L11.1={ lambda, aac, abc,aaaacc, aaabcc, aabbcc, aaaaaaccc, aaaaabccc, aaaabbccc, aaabbbccc, aaaaaaaacccc, aaaaaaabcccc, aaaaaabbcccc……..}
In diesem Fall handelt es sich doch um eine unendliche Menge, net wahr?
So, nun sollte man ein passendes Wort aus dieser Menge nehmen und die Pumping Kriterien durchgehen:
Im Skript steht ja 2^k =< |z| =< 2^q und das k ist gleich der Kardinalität der Nonterminale, heisst es dann in diesem Fall(wegen lambda), dass es keine Nonterminale in der Grammatik gibt, oder bezieht sich dann die Kardinalität nur auf die Nonterminale, die zur Bildung eines bestimmten Wortes benutzt werden?
So, ich nehme mal das Wort z = aaabbbccc = uvwxy und es muss gelten:
1. |vx|= |aaabbb|>=1
2. |vwx|=|aaabbb|=6 =< n
(n=2^k und woher weiss man, wie gross k ist? Muss man die Grammatik Syntax dazu herstellen?)
3. für alle i >= 0, u v^i w x^i y aus L, aber in diesem Fall geht das nicht, da für i=0 das Wort ccc entsteht und dieses Wort ist nicht aus der gegebenen Sprache.
Ich bin sicher, dass das absolut falsch ist, was ich gemacht habe, aber vielleicht kann jemand meinen Denkfehler erkennen und mir behilflich sein.
Bis denn
versuche gerade F2 Aufgaben zu bearbeiten und hab ein paar Probleme mit der Anwendung des Pumping-Lemmas der kontextfreien Sprachen.
Mein Wissenstand:
Also gegeben ist ja immer eine Sprache.
Mit dem Pumping Lemma kann man nur beweisen, dass eine Sprache nicht kontextfrei ist. Das natürlich nicht ausschliesst, dass es auch nicht kontextfreie Sprachen gibt, die die Pumping-Lemma Eigenschaften erfüllen.
Das Pumping-Lemma:
Für jede kontextfreie Sprache L aus Cf gibt es eine Zahl n aus N, so dass jedes Wort z aus L mit |z| >= n eine Zerlegung z = uvwxy besitzt, für die golgendes gilt:
(i): |vx|>=1
(ii): |vwx|<= n (n:= 2^k, k=|Vn|)
(iii): für alle i>=0 u v^i w x^i y aus L
(|z| ist genau die Anzahl der Knoten mit genau einem Nachfolger und u, v, w, x, y sind doch Teilwörter von z, oder?)
Nun die gegebene Sprache in 11.1 ist:
L11.1:={a^r b^s c^t| r,s,t aus N : (r+s = 2*t) und (s =< r)}
L11.1 lexikalisch geordnet:
L11.1={ lambda, aac, abc,aaaacc, aaabcc, aabbcc, aaaaaaccc, aaaaabccc, aaaabbccc, aaabbbccc, aaaaaaaacccc, aaaaaaabcccc, aaaaaabbcccc……..}
In diesem Fall handelt es sich doch um eine unendliche Menge, net wahr?
So, nun sollte man ein passendes Wort aus dieser Menge nehmen und die Pumping Kriterien durchgehen:
Im Skript steht ja 2^k =< |z| =< 2^q und das k ist gleich der Kardinalität der Nonterminale, heisst es dann in diesem Fall(wegen lambda), dass es keine Nonterminale in der Grammatik gibt, oder bezieht sich dann die Kardinalität nur auf die Nonterminale, die zur Bildung eines bestimmten Wortes benutzt werden?
So, ich nehme mal das Wort z = aaabbbccc = uvwxy und es muss gelten:
1. |vx|= |aaabbb|>=1
2. |vwx|=|aaabbb|=6 =< n
(n=2^k und woher weiss man, wie gross k ist? Muss man die Grammatik Syntax dazu herstellen?)
3. für alle i >= 0, u v^i w x^i y aus L, aber in diesem Fall geht das nicht, da für i=0 das Wort ccc entsteht und dieses Wort ist nicht aus der gegebenen Sprache.
Ich bin sicher, dass das absolut falsch ist, was ich gemacht habe, aber vielleicht kann jemand meinen Denkfehler erkennen und mir behilflich sein.
Bis denn
