Theoretische Informatik Beweis so ausreichend?
Moin, ich wüsste gerne, ob das hier richtig ist und wenn nein, was könnte ich besser machen?
1 Antwort
Der Beweis funktioniert so nicht, weil du immer nur eine einzelne Zerlegung betrachtest. Du musst zeigen, dass es für jede Zerlegung von w in Bestandteile x,y,z mit |xy| <= n so eine Zahl k gibt.
Beispiel: In deinem Fall n = 3 hast du das Wort w = ab gewählt.
x = ε, y = a und z = b ist eine mögliche Zerlegung von w, und für diese geht das Aufpumpen tatsächlich schief.
Aber x = ε, y = ab, z = ε ist ebenfalls eine Zerlegung mit |xy| <= n und w = xyz. Und egal wie weit man aufpumpt, das Ergebnis wird immer in der Sprache liegen.
Du musst ein Wort w finden, bei dem das Aufpumpen für alle möglichen Zerlegungen (die die Bedingungen erfüllen) schiefgeht.