Pumping Lemma kontextfreier Sprachen

Pumping Lemma für kontextfreie Sprachen

Das besondere an dem Pumping Lemma für kontextfreie Sprachen ist, dass es in diesem Fall mindestens zwei Pumpstellen geben muss. Laut dem Pumping Lemma für kontextfreie Sprachen wird ein Wort z zerlegt in die Teile u,v,w,x und y, so dass die Zerlegung von z: z = uvwxy folgende Bedingungen erfüllen muss:

1)   |vwx| ≤ n, sprich für eine eingabe eines beliebig langen Wortes z=uvwxy ist das Teilwort vwx längenmässig beschränkt.

2)   |vx| ≥ 1, sprich dass Teilwort vx darf nicht das leere Wort sein!

3)   Die Stellen v und x der Zerlegung z=uvwxy dürfen beliebig oft gepumpt werden, jedoch beide gleichoft. Das heißt uviwxiy muss für alle i aus den natürlichen Zahlen vereinigt mit der Null wieder Element der betrachteten kontextfreien Sprachen sein!

Eine kontextfreie Sprache muss obenstehendes Pumping Lemma erfüllen. Wird obestehendes Pumping Lemma also verletzt, dann ist die betrachtete Sprache nicht kontextfrei.