allgemeine Fragen zum Pumping-Lemma

Question

Hallo beisammen,

habe nicht direkt eine Frage zu der Aufgabe, sondern zum Pumping-Lemma:

1) Woher weiß ich n, die Anzahl der Zustände?
2) Wenn ich das Pumping-Lemma auf den Automaten L5 in AÜ-1-2 anwende, nehme ich bspw. als Wort 0000111. x auf die 0er, y auf die erste 1 und z auf die zwei restlichen 1er. Nun pumpe ich y. Dann bekomme ich mehr als 3 Einsen und der Widerspruch ist geführt. Was mache ich falsch? Denn es gibt ja in dieser Aufgabe einen EA, der L5 erkennt.

LG und danke im Voraus!

Andi

Answer 1

Hallo,

1) die Anzahl der Zustände ist meist nicht bekannt. Man kann aber für jedes n ein längeres Wort kreieren, meistens indem einfach bestimmte Zeichen(folgen) n-mal wiederholt werden, z.B. 0^n.

2) Gültige Zerlegung: x = irgendeine Anzahl an Nullen; y = eine Null; z weitere Nullen und der Rest (bei deinem Beispiel 111). Dann kann y beliebig aufgepumpt werden. Generell besagt die Umkehrung des Pumpinglemmas (mit der wir den Widerspruch zeigen wollen), dass ein Wort nicht erkannt wird, wenn es überhaupt keine gültige Zerlegung mit den 3 Bedingungen gibt, dass also für jede Zerlegung das Aufpumpen verletzt ist. Irgendeine Zerlegung zu finden, die das Pumpinglemma verletzt, reicht also nicht aus.

MfG, Jakob

Answer 2

Hallo,

was hier sehr wichtig ist, und deshalb wiederhole ich es nochmal, obwohl es Jakob eigentlich schon gesagt hat, ist, dass man sich beim PPL nicht einfach Wörter konstanter Länge anschauen kann, denn diese kann man immer mit einem endlichen Automaten ohne Schleife erkennen. Habe ich ein Wort der Länge k, kann ich immer einen Automaten mit k+1 Zuständen bauen, der keine Schleife braucht und das Wort erkennt.

Anstelle einzelner Wörter betrachten wir beim PPL immer Wortklassen. Bspw. ist anbn nicht ein Wort, sondern abhängig von n eine beliebig große Menge von Wörtern. Jetzt können wir sagen, dass n von der Anzahl der Zustände des Automaten abhängt. Damit drehen wir den Spieß um, denn dann kann keiner sagen: Dann nehme ich halt einfach einen größeren Automaten. Wenn der Automat größer wird, wird eben auch das Wort länger. Die Grundidee des PPL ist dann, dass Wörter, die mindestens so lang sind wie die Anzahl der Zustände des Automaten, nur erkannt werden können, wenn der Automat eine Schleife hat. Und hat er eine Schleife, kann man diese beliebig oft durchlaufen, was einem "Pumpen" der Worts entspricht.

Viele Grüße

Lukas König