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.)

Frage zu dieser Aufgabe

0 Punkte
73 Aufrufe
Hallo,

auch ich habe versucht den Beweis so zu führen wie die Fragestellerin.

Im Moment scheitere ich noch an dem Schritt, welchen Philippe in den letzten beiden Absätzen seines Foreneintrags erwähnt - also dem Nachweis, dass w'=a^(n^2-j) nicht aus der Sprache ist.

Könnte mir diesen nochmal jemand erklären?

Vielen Dank!
bezieht sich auf eine Antwort auf: a): Anderes Vorgehen bei Beweis erlaubt?
Gefragt 15, Jan 2017 in HU-1-4 von Anonym  

Eine Antwort

0 Punkte
Hallo,

wenn du von w'=a^(n^2-j) ausgehst, dann musst du quasi zeigen, dass n^2-j keine Quadratzahl ist.
Die nächst kleinere Quadratzahl wäre ja (n−1)^2=n^2−2n+1.
daher müsste gelten j= 2n-1 und da j =< n sein muss, ist das für hinreichend große j (größer 1) nicht gegeben und demnach ist das Wort nicht Teil der Sprache.

Grüße, Sören
Beantwortet 16, Jan 2017 von updrr updrr Eins-Komma-Null-Anwärter(in) (3,790 Punkte)  
...