Wo ist hier der Definitionsbereich von k angegeben?

Question

Ich hätte zu dieser Aufgabe ein paar Fragen.

1) Wo ist hier der Definitionsbereich von k angegeben? Fehlt der nicht? Klar fliegt k am Ende raus, doch muss es der Definitionsbereich nicht vollständigkeitshalber auch dabei stehen?

2) Ich habe die Aufgabe entwas anders gelöst, indem ich a^2n in a^n * a^n umgeformt habe und würde gern wissen, ob folgender Lösungsweg erlaubt ist.

Annahme: L wird von EA erkannt.

EA A habe n element No Zustände. Wähle w = a^2 ^n =a^ (2*n) = a^n * a^n mit |w| >= n und w element L.

Sei w = xyz eine beliebige Partiton von w. Dann gilt laut PPL:

      (1) |xy| <= n

      (2) |y| >= 1

      (3) Für alle i element N0: xy^iz element L

aus (1) |xy| <= n folgt xy = a^j mit j >= 0

aus (2) |y| >=1 folgt y = a^k, x=a^(j-k), z= a^(n-j)a^n mit 1<=k<=n

Wähle nun i = 0, damm folgt xy^0z = xz = a^(j-k)a^(n-j)a^n = a^(n-k)a^n nicht element L.

Widerspruch zur Annahme und damit wird L nicht von einem EA akzeptiert.

 

3) Ich hatte auch überlegt für i = 2 einsetzen, dann würde da am Ende a^(n+k) a^n stehen, aber das ist für mich eigentlich kein logischer Unterschied, ob es nun + oder - k heißt, oder? Im Endeffekt sieht man doch durch das k, dass es sich nicht mehr um eine 2er Potenz handeln kann, da k den Wert 1 annehmen kann und ob ich nun 1 abziehe oder dazuaddiere macht keinen Unterschied, oder?

Answer 1

Hallo,

zu 1):

Du hast Recht, das fehlt. Vergiss aber nicht: Dies sind 'nur' Lösungsskizzen und nicht immer 100% vollständig.

zu 2):

Zunächst ist a^2^n nicht a^2*n. Du meintest wohl (a^2)^n, das ist etwas anderes!

Zu deinem Beweis: 

Deine Schlussfolgerung st nich 100% sicher, du musst sicherstellen, dass das Wort, dass nach dem Pumpen entsteht nicht wieder Teil der Sprache ist. Dabei musst du beachten, dass das resultierende Wort wieder drin sein könnte, nur mit einer anderen natürlichen Hochzahl!

Mehr kann ich wegen deines Rechenfehlers leider nicht sagen.

Zu 3):

Bei i>1 könnte dasselbe Problem entstehen. Dabei kann k natürlich den Wert annehmen, aber auch alle anderen Werte zwischen 1 und n. Und um den Beweis korrekt zu führen, muss deine Schlussfolgerung für alle k gelten.

Gruß,

Adam(Tutor)