jaquo1995
Grünschnabel
Dabei seit: 12.01.2014
Beiträge: 1
 |
|
| pumping Lemma für kontextfreie Sprachen |
     |
Meine Frage:
Hallo.
Ich habe die Aufgabe zu zeigen, dass die Sprache
L={xcy|x,y?{a,b}*, |x|_a =|y|_a , |x|_b =|y|_b}
nicht vom Typ 2 ist. Dies soll ich mithilfe des pumping Lemmas zeigen.
Meine Ideen:
Soweit swo gut. Es muss also eine Zerlegung z=uvwxy geben, sodass |vx|>= 1 und |vwx|<=n und uv^iwx^iy?L für alle i>=1.
Die vorraussetzungen sind mir klar, ich habe allerdings ein problem mit dem ansatz.
Bei der Sprache L={a^n b^2^n | n?natürliche Zahl} ist der Ansatz klar. n ist die Pumping lemma zahl und dann unterscheidet man die fälle was v und x sein können. das versteh ich ja auch.
ich verstehe nur nicht inwiefern man bei der ersten sprache n setzt um dann mit den fällen weiter zu machen.
erst hatte ich gedacht man könnte das vereinfachen indem man sagt, wenn |x|_a =|y|_a und |x|_b =|y|_b dann |x|=|y|, also z=x^n c y^n. das kann aber nicht richtig sein.. oder?
und ein anderer ansatz fällt mir nicht ein...
|
|
