Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Wo ist hier der Definitionsbereich von k angegeben?

+1 Punkt
35 Aufrufe

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?

Gefragt 16, Okt 2015 in 2012-B-01 von updkn updkn Info-Genie (6,630 Punkte)  

Eine Antwort

+1 Punkt

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)

Beantwortet 16, Okt 2015 von updkn updkn Info-Genie (6,630 Punkte)  
...