Pumping Lemma für reguläre Sprachen anwenden?
Hallo, ich bin auf eine schwierige Aufgabe bezüglich des Pumping Lemmas für reguläre Sprachen gestoßen und ich komme nicht weiter bei der Zerlegung eines Wortes s in xyz. Es handelt sich um die Sprache L = {a^n b^m c b^m a | n, m aus den natürlichen Zahlen}.
Ich hatte als s ursprünglich a b^p c b^p a gewählt, aber ich verstehe nicht, wie man hieraus einen Widerspruch formen kann, denn wenn sich y bloß aus a's zusammensetzt, wird das Pumping Lemma hier ja erfüllt.
Danke im Voraus!
1 Antwort
Das Pumpinglemma muss für ALLE Wörter der Sprache gelten, wenn die Sprache regulär ist
Du musst für alle möglichen Pumpingkonstanten (also jede natürliche Zahl) eine Wort konstruieren, sodass das Pumpinglemma mit der Pumpingkonstante mit diesem Wort nicht erfüllt ist.