Pumping-Lemma Wortwahl

Question

Hallo,

mal eine Frage zur Wortwahl beim Pumping-Lemma:

Bei der Aufgabe im Buch ist es ja so, dass für alle Wörte der Sprache einfach nur Anzahl Einsen in w = Anzahl Nullen in w sein muss. Nun wird aber als zu testendes Wort 0^n1^n gewählt. Das deckt ja aber jetzt nicht die komplette Sprache ab, sondern nur Wörter der Form 01,0011,000111, etc. . Allerdings werden durch das Wort Wörter wie 0101, 1001, etc. also alle Wörter in denen zwar die Anzahl der Einser = der Anzahl der Nullen ist, aber nicht unbedingt alle Nullen und Einsen hintereinander stehen, ja nicht abgedeckt, obwohl diese noch Bestandteil der Sprache wären, Deswegen die Frage: Muss man bei der Wortwahl ein Wort wählen, dass die komplette Sprache abdeckt, oder reicht ein Wort das zumindest einen Teilbereich der Sprache abdeckt? Dass es nicht reicht ein spezifisches Wort zu testen wurde ja schon beantwortet.

Danke schon mal!

Answer 1

Hallo uoioh,

da das Pumping Lemma ein Widerspruchsbeweis ist, genügt es hier, einen möglichen Aufbau des Wortes zu verwenden und für diesen zu zeigen, dass die Bedingungen dafür nicht alle erfüllt sind. Hat man es für ein Wort bewiesen, ist der Widerspruch erfüllt.

Ich glaube, das mit dem Testen des einzigen Wortes hast du falsch verstanden. Es genügt uns, für ein Wort zu zeigen, dass alle möglichen Zerlegungen in x, y und z dazu führen, dass eine der drei Bedingungen (1), (2) oder (3) nicht erfüllt ist.

Ein Problem gibt es nur, wenn du ein Wort wählst, und die Bedingungen nach dem Pumpen zufällig immer noch alle korrekt sind. Das ist bei den Aufgaben im Normalfall aber nicht so.

Viele Grüße
Hannah (Tutorin)