pumping Lemma für kontextfreie Sprachen |
| 12.01.2014, 15:41 | Auf diesen Beitrag antworten » |
| jaquo1995 | 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... |
|
|
|
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
