Hab das gleiche Problem wie immer. Das Beispiel aus der Vorlesungen is mir völlig klar, aber die Hausaufgabe scheint mal wieder viel komplizierter zu sein. Es hängt doch davon ab, wie das v in z=uvw aussieht. weiß allerdings nicht, wie ich das am besten wählen soll. Is auch irgendwie verwirrend, dass 2 Variblen, sprich m und n auftauchen. Kann mir jemand weiterhelfen? Find den Ansatz nicht.

das z musst du wählen, nicht das v,
fang doch einfach mit dem simpelsten z an was du dir denken kannst (mit |z| > k),
das sollte schon ausreichen,
dann ergibt sich für alle zerlegungen der gleiche standard-widerspruch:
u (v)^0 w nicht mehr in der sprache

sonst musst du schon genauer beschreiben, woran es scheitert

na das einfachste Wort is ja z=abb. Wenn dann also eine Zerlegung so aussieht: u=a^x, v=a^i, w=b^2x dann gilt ja für uv^0w = a^xb^2x, was ja akzeptiert wird. Wie gesagt, weiß ich nich, wie die Zerlegungen zu wählen sind. Oder geh ich da falsch ran?

na das einfachste Wort is ja z=abb.

wer sagt, dass das länger ist als k?

versuchs mit a^k b^(2k)..

Wenn dann also eine Zerlegung so aussieht: u=a^x, v=a^i, w=b^2x dann gilt ja für uv^0w = a^xb^2x, was ja akzeptiert wird.

(mal abgesehen davon, dass das z schon falsch gewählt wurde),
was hat dies mit dem ursprungswort z = abb zu tun?,
wieso ist u=a^x?, was ist das x? was ist das i?
da muss man schon korrekt arbeiten,

Wie gesagt, weiß ich nich, wie die Zerlegungen zu wählen sind. Oder geh ich da falsch ran?

das ist ganz einfach, du musst ALLE möglichen zerlegungen betrachten,



noch mal ein beispiel:
L = {a^n,b^n| n>=0}

jetzt kann man nicht z = ab wählen, denn das ist ja nicht
notwendigerweise länger als k,
stattdessen nimmt man zum beispiel z =a^k b^k

und betrachtet alle möglichen zerlegungen,
die sehen so aus:

v = a^y mit 1 <= y <= k
u = a^x mit 0 <= x <= k-y
w = a^k-x-y b^k

dann ist u v^0 w für alle möglichen zerlegungen:
u v^0 w = a^x a^k-x-y b^k = a^k-y b^k
und das ist nicht in L

ich glaub das hab ich soweit einigermassen verstanden, nur jetzt spezifisch bei der aufgabe rall ich nicht ganz wie man das n<=2m<=3n einarbeiten soll. Oda tut das gar nichts zur sache?

tut durchaus zur sache,
nach den bedingungen der sprache wie 'n<=2m<=3n' richtet sich,
welches wort z man wählen sollte und wie man für jede
zerlegung den wiederspruch zeigen kann,

beispiel
{a^n b^n} versus {a^n b^m 0<=n<=m}
z jeweils a^k b^k

beim ersten kann man den widerspruch zeigen wie unten
aufgeführt mit u v^0 w = a^(k-y) b^k nicht in der sprache,

beim zweiten würde das so nich klappen,
da die erste potenz durchaus kleiner als die zweite sein darf

-> man zeigt den widerspruch mit u v^2 w = a^(k+y) b^k,
denn das ist auch in der zweiten sprache für jede zerlegung nicht drin,


ich will nicht ausschliessen, das man bei dieser aufgabe vielleicht
nicht die volle komplexität der bedingung 'n<=2m<=3n' braucht [img]http://www.fb18.de/gfx/25.gif[/img],
aber ignorieren kann man sie nicht..

wie gesagt: 'aufgabenspezifisch rall ich das nicht' klingt immer ganz böse,
besser:
wähl dir ein wort, schaue ob du für alle zerlegungen
einen widerspruch bekommst,
wenn ja, gut, wenn nicht schauen, ob es mit einem anderen wort besser geht, usw.,

beispiel
{a^n b^n} versus {a^n b^m 0<=n<=m}
z jeweils a^k b^k

beim zweiten würde das so nich klappen,
da die erste potenz durchaus kleiner als die zweite sein darf

-> man zeigt den widerspruch mit u v^2 w = a^(k+y) b^k,
denn das ist auch in der zweiten sprache für jede zerlegung nicht drin,

wenn ich das so mit der bedingung n<=2m<=3m mache dann kommt da raus a^(k+y)b^k. Und wie schliesse ich jetzt auf n<=2m<=3m???

wenn ich das so mit der bedingung n<=2m<=3m mache dann kommt da raus a^(k+y)b^k. Und wie schliesse ich jetzt auf n<=2m<=3m???

bzw. wenn ich einmal fuer v^0 und einmal fuer v^2 das mache, dann kommt einmal a^(k-y)b^k (==> m<n)) und einmal a^(k+y)b^k (also m>n) raus. Kann ich diesen Widerpruch als Beweis verwenden?

dch seh das auch so hab aber keine ahnung wie man das jetzt weiterfuehren soll. anscheinend hab ich nicht als einziger das prob sonst waeren hier mehr postings

slater wo bist du?

beispiel
{a^n b^n} versus {a^n b^m 0<=n<=m}
z jeweils a^k b^k

beim zweiten würde das so nich klappen,
da die erste potenz durchaus kleiner als die zweite sein darf

-> man zeigt den widerspruch mit u v^2 w = a^(k+y) b^k,
denn das ist auch in der zweiten sprache für jede zerlegung nicht drin,

wenn ich das so mit der bedingung n<=2m<=3m mache dann kommt da raus a^(k+y)b^k. Und wie schliesse ich jetzt auf n<=2m<=3m???

kann ich nicht y gegen inf laufen lassen und dann damit argumentieren dass n<=inf<=3n nicht stimmt?

schwer am vorlesungen besuchen ;)

wenn ich das so mit der bedingung n<=2m<=3m mache dann kommt da raus a^(k+y)b^k. Und wie schliesse ich jetzt auf n<=2m<=3m???

du wählst also z = a^k b^k ?

nun gut, und willst nun zeigen, dass für alle y gilt:
u v^2 w = a^(k+y) b^k nicht in L

kann man gerne versuchen,
dazu guckt man nun ob dieses wort jeweils das kriterium der sprache erfüllt, hier als die gleichungen:

n<= 2m und 2m <= 3n für n=k, m=k+y

einsetzen:
k<=2k+2y, klingt als wär diese begingung erfüllt

2k+2y <= 3k

hmm, bei y=1 ist auch diese gleichung für genügend grosses k erfüllt,
also haben wir eine zerlegung gefunden, für die u v^2 w in L liegt,
damit haben wir leider nicht den erhofften widerspruch,

wie kann man weitermachen?:
herausfinden woran es lag, und anderes prüfwort statt u v^2 w wählen und/ oder anderes z wählen

bzw. wenn ich einmal fuer v^0 und einmal fuer v^2 das mache, dann kommt einmal a^(k-y)b^k (==> m<n)) und einmal a^(k+y)b^k (also m>n) raus. Kann ich diesen Widerpruch als Beweis verwenden?

hier liegt kein widerspruch vor, denn es ist ja nicht verboten,
dass bei 2 unterschiedlichen wörter m<n und m>n gilt,

beide wörter sind bei günstig gewähltem y (etwa y=1) in der sprache L enthalten,
helfen also nicht beim widerlegen der regularität


hmm wie soll ich da helfen, es ist eigentlich ganz einfach,
man könnte ja mal testen, ob u v^(100.000 k) w in L liegt..

kann ich nicht y gegen inf laufen lassen und dann damit argumentieren dass n<=inf<=3n nicht stimmt?

es gilt 1<=y<=k, jedenfalls für y wie bei mir da weiter vorne verwendet,

aber die idee klappt schon, wenn man sie korrekt formuliert

tja wenn ich das korrekt formulieren koennte waer ich ja schon fertig. naja ich werd mal sehen, ob ich das noch hinbekomme…