3.2

[Auron]

w= a^2^m \mid w \mid=2^m \geq m

w= a^m a^{{2^m}-m}

w= \underbrace {a^j}_{x} \underbrace {a^k}_{y} \underbrace {a^{{2^m}-m}}_{z}
j+k=m wobei k>0

\mid xy \mid=j+k \leq m

w_{i}=a^j (a^k)^i a^{{2^m}-m}

i= 2 \Rightarrow w_{2}= a^j a^{2k} a^{{2^m}-m}

\mid w_{2} \mid= (j+2k) + 2^m -m = m + k + 2^m - m = 2^m + k

da k aber > 0 sein muss wäre auch a^{{2^m}+1} und damit beliebige Wörter mit ungerader Anzahl an a was aber in der Sprache nicht akzeptiert wird.

[tonico]

w= a^j a^k a^((2^m)-m) j+k=m für k>0 |xy|= j+k <= m

Hm, mit m=4 kann ich nach obiger Beschreibung folgendes Wort erzeugen:

w = a^2 a^2 a^((2^4)-4) = aa aa aaaaaaaaaaaa = a^20

20 kann man aber nicht als 2^n darstellen, also ist w nicht in L.

Ich bin gerade am Prüfen ob es mit w = a^2m a^2m funktioniert ...

[thoreon]

Hi,

Also ich bekomme a^16 und nicht a^20:
a^2 a^2 a^((2^4)-4) = a^16
2^4 = 16 - 4 = 12 + 2 + 2 = 16

Und da 16 = 2^4 ist, würde dieses Wort in L liegen.

Lg
Thomas

[tonico]

Ja, sorry, hab mich verrechnet :)

[thoreon]

:) Passt schon, wollt nur drauf aufmerksam machen :)
Ansonsten denk ich, passt die Lösung von Auron.

Lg
Thomas

[axestr]

da k aber > 0 sein muss wäre auch [tex]a^{{2^m}+1} und damit beliebige Wörter mit ungerader Anzahl an a was aber in der Sprache nicht akzeptiert wird.


Du weisst nicht, wie hoch k ist! Wenn k gerade ist, dann ist 2^m + k sicher auch gerade. Ich habe so argumentiert, dass 2^m quadratisch steigt, aber jede Zerlegung von x(y)^iz nur linear. Dann muss man nur beweisen, das es für y1=x+i.y+z und y2=2^m ein y1 gibt, dass nicht durch y2 dargestellt werden kann.

Lg, Axel.

[da_pat]

Du weisst nicht, wie hoch k ist! Wenn k gerade ist, dann ist 2^m + k sicher auch gerade. Ich habe so argumentiert, dass 2^m quadratisch steigt, aber jede Zerlegung von x(y)^iz nur linear. Dann muss man nur beweisen, das es für y1=x+i.y+z und y2=2^m ein y1 gibt, dass nicht durch y2 dargestellt werden kann.

Lg, Axel.

würde es nicht reichen i=0 anzunehmen? denn dann wäre a^(k^i) = a^1 und es würde für die wortlänge 2m+1 herauskommen, was ja nicht in a^(2^n) liegt.

lg,
thomas

[axestr]

würde es nicht reichen i=0 anzunehmen? denn dann wäre a^(k^i) = a^1 und es würde für die wortlänge 2m+1 herauskommen, was ja nicht in a^(2^n) liegt.


Obacht: y ist ein Wort! Keiner sagt, dass |y|=1 ist. Man weiss nur, dass |xy|<=m ist, also kann auch |x|=0 und |y|=m sein.
dann ist bei x(y)^0z die Wortlängen 2m-m=m, und wenn dann z.B. m gleich zwei ist, dann ist 2m=4=2^2, und m=2=2^1.

Lg, Axel.

[Auron]

Du weisst nicht, wie hoch k ist! Wenn k gerade ist, dann ist 2^m + k sicher auch gerade.
Lg, Axel.

Schön und gut, dann ist eben 2^m + k bei k=2b (= gerade) gerade wobei noch immer k > 0 sein muss
Dann liegt aber z.B. 2^m + 2 ja auch nicht in unserer Sprache, denn 2^m + 2 nehmen wir an m=2 2^2 + 2= 6 und das ist zwar gerade aber keine gültige 2er Potenz.
auch für k=2^2=4 gilt 2^4 + 2 = 18 und das gilt dann auch für jedes beliebige m

Auch bei k=2^2=4 gilt 2^4 + 4 = 20 , 2^5 + 4 = 36-> keine 2er Potenz
usw.

Also ändere ich meine Begründung ein wenig ab und sag a^{{2^m} + k} liegt deshalb nicht in unserer Sprache weil das k (wobei m >= k > 0 gelten muss) unsere 2er Potenz um k Stellen verschiebt und uns damit "aus unserer Sprache rausschiebt".
Und liegt damit nicht mehr in unserer Sprache.

[axestr]

a^{{2^m} + k}

So ähnlich habe ich es gelöst - ohne Garantie auf Richtigkeit ;-)
Ich habe a^2^(m+ki), k>0, i ist da i aus ... ah geh, da ist mein PDF:
http://straschil.com/skripten/TheoInf_2007W_Axel_2007-10-25.pdf

Auch ganz gut:
http://www-users.rwth-aachen.de/clemens.adolphs/wordpress/wp-content/2006/08/pumping_lemma.pdf

Lg, Axel.

[cherrybonbon]

[/URL] Auch ganz gut:
[URL]http://www-users.rwth-aachen.de/clemens.adolphs/wordpress/wp-content/2006/08/pumping_lemma.pdf (http://straschil.com/skripten/TheoInf_2007W_Axel_2007-10-25.pdf)


danke für den super link