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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

1 Pluspunkt 1 Minuspunkt
47 Aufrufe

Ich weiß, die Frage wurde hier jetzt schon ein paar mal gestellt. Aber ich kann das leider immer noch nicht nachvollziehen.

In der Musterlösung steht:

\( (1) |xy| \leq n \),
\( (2) |y| \leq  1 \).
Daraus folgt:
\( x = a^{i_x}\) mit \(1 \leq i_x \leq n \),
\( y = a^{i_y} \) mit \( 1 \leq i_y \leq n \),
\( z = a^{i_z} \) mit \( (i_x + i_y + i_z) = n^2 \)

Wenn jedoch im Extremfall \( i_x=n \) sowie \( i_y=n \), was ja laut den Folgerungen möglich wäre, dann hab ich doch \( xy = a^{2n} \), also \( |xy| = 2n \) und somit wäre doch die Bedingung (1) verletzt. Oder habe ich da einen Denkfehler drin?

 

in HU-1-4 von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Hallo,

da hast du sicherlich recht. Genauer müsste es heißen, dass \( i_x + i_y \leq n \). Dann ist Bedingung (1) erfüllt.

Gruß,

Marius (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
...