a): Anderes Vorgehen bei Beweis erlaubt?

Question

Hallo,

wieso kann ich im Aufgabenteil a) den gegenbeweis nicht wie folgt führen:\( xy= a^{k}\) und \(y= a^{j}\) und \(z=a^{{n^2}-k} \) dann wäre \( xz : a^{{n^2}-j} \) und somit keine Sprache die ein endlicher Automat akzeptiert. Wieso darf ich das hier nicht mit diesem Vorgehen beweisen?

Beste Grüße

Anna

Answer 1

Hallo zusammen,

Das funktioniert m.E. auch, im Prinzip machst du das Gleiche wie in der Lösung nur mit i=0 statt i=2. Eines der beiden zu zeigen ist ausreichend.

Allerdings musst du begründen, warum \( w'=xz=a^{{n^2}-j} \) nicht aus der Sprache ist. Das wiederum liegt daran, dass \( (n-1)^{2} = n^{2} - 2n + 1 \).

Da der Exponent von z wegen \( j \leq n \) nur im Fall n=1 den gleichen Wert annimmt, ist das Wort nicht Teil der Sprache.

Ich hoffe, ich konnte euch weiterhelfen.

Viele Grüße

Philippe