Beispiel 4.4

[snax]

Scheinbar bin ich der einzige der sich hier ein bissi im Kreis dreht... ist es so Simpel das es hier nicht besprochen werden muss? :D

Angabe: L = {0^n 1^n 0^n 1^n | n >= 0}

Meine Herrangehensweise:
z = uvwxy |z| >= m |vx| >= 1 |vwx| =< m

z = a^m b^m a^m b^m

4m > m

dann habe ich für vx = a^k b^j

was mich zu z' = a^m-k b^m-j a^m b^m führt was NICHT Element L ist ....

Wäre der Widerspruch und die damit verbundene nicht vorhandene Kontextfreiheit so richtig gezeigt? Hat jemand andere Überlegungen zu dem Beispiel?

Thanks in advance...

[grinser]

ich weiß ja nicht obs so geht, aber das werdet ihr mir vielleicht sagen können:

erst mal habe ich mir nur 0^n 1^n angesehen, weil ja 0^n 1^n 0^n 1^n nur die verknüpfung von 0^n 1^n mit sich selbst ist und ja die kontextfreien sprachen lt. folie 103 abgeschlossen gegenüber der verknüpfung sind. wenn also der teil nicht kontextfrei ist kann es die ganze auch nicht sein.

dann wähle ich als n=4 und teile das wort folgendermaßen auf:

w=(000)(0)(1)(11)(11)
u v x y z

wenn ich nun v und y pumpe (zB. i=2), dann ist
wi = 000 00 1 1111 11

nicht mehr element von L und daher nicht kontextfrei.
was meint ihr?

[bsoykal]

@ grinser

wenn du n=4 waehlst dann kannst du nicht 00001111 bekommen.


0000111100001111

das ist was du bekommen wirst .

[chillin]

also ich bin mir immer noch nicht sicher ob ichs versteh...
ich habs so gelöst:

w= 0^m 1 0^m 1 (2m+2 > m)

d.h. mein xy kann nur aus 0 bestehen

x= 0^k
y= 0^l l =! 0
z= 10^m1 (wobei k+l=m => k=m-l)

w0 = 0^k (0^l)^0 10^m1 => xy°z = 0^m-l 10^m1

da das aber ein widerspruch ist (weil m-l < m), ist L nicht regulär!
Stimmt das so? Kann vielleicht jemand der sich da auskennt uns hier recht geben :rolleyes:

edit: oke...falsche angabe... das is für {ww | w ∈ {0,1}*} viell. richtig aber nicht für 0n1n0n1n ...oder
edit2: oke...kontextfrei...gaanz falsche baustelle...hehe

[schrankk]

Scheinbar bin ich der einzige der sich hier ein bissi im Kreis dreht... ist es so Simpel das es hier nicht besprochen werden muss? :D

Angabe: L = {0^n 1^n 0^n 1^n | n >= 0}

Meine Herrangehensweise:
z = uvwxy |z| >= m |vx| >= 1 |vwx| =< m

z = a^m b^m a^m b^m

4m > m

dann habe ich für vx = a^k b^j

was mich zu z' = a^m-k b^m-j a^m b^m führt was NICHT Element L ist ....

Wäre der Widerspruch und die damit verbundene nicht vorhandene Kontextfreiheit so richtig gezeigt? Hat jemand andere Überlegungen zu dem Beispiel?

Thanks in advance...
und wie bist du auf a und b gekommen, wenn die gegebene Sprache 1 und 0 enthält?! ;) aber da hast du dich sicher einfach vertippt...

das Wort hab ich sebe ausgewählt, also z=(0^n 1^n 0^n 1^n). Dann gibt es aber 3 Fälle, wo vxy liegen könnte (und entsprechend aus welche Symbole bestehen könnte)...

1) vxy liegt in der ersten Hälfte des Wortes, und somit vxy = 0^k 1^j. Man führt es zum Widerspruch, indem es gezeigt wird, dass diese erste Hälfte dann entweder weniger (mehr) 1 oder 0 enthalten wird, als es in zweite Hälfte immer liegt... Da entweder j>0 oder k>0 sein sollte, liegt (0^(n-k) 1^(n-j) 0^n 1^n) nicht mehr in gegebene Sprache.

2) vxy liegt in der zweiten Hälfte des Wortes. vxy = 0^k 1^j. Gleiche Vorgehensweise, nur (0^n 1^n 0^(n-k) 1^(n-j)) nicht mehr in der Sprache liegt...

3) vxy liegt in der Mitte. vxy = 1^k 0^j. Gleiche Vorgehensweise, nur in diesem Fall das Wort (0^n 1^(n-k) 0^(n-j) 1^n) nicht mehr in der Sprache liegt...

peace. :thumb:

[bsoykal]

sehr gut :) und sieht richtig aus :):):thumb:

[Al Kupone]

ich glaube es geht einfacher.. da alle symbole gleich oft vorkommen gilt: |w|o = |w|1
unser wort schaut so aus 0^m 1^m 0^m 1^m und unser w = 4m > m
wenn wir jetzt für unser V^i X Y^i ein i = 0 verwenden, geht das ganze in die brüche,denn auf jeder seite werden die anzahl der 0 ungleich der der 1 sein.
bsp:
m = 5 i = 0
00000111110000011111 egal wie die zerlegung aussieht,da wo unser XVY ist, werden immer sysmbole fehlen und somit gilt |w|_o ungleich |w|_1 und falls VXY = 011 ist (zerlegung auf der linken seite des wortes, angenommen 0 = v und der zweite 1 =Y) kommen zwar auf jeder seite die gleiche anzahl an 0 und 1, aber auf der rechten seite des wortes werden immer noch 5*0 und 5*1 sein (also 000011110000011111),somit ist das ganze widerlegt.