Müller Übungsblätter A18 (v)
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Pumpinglemma
die sprache L := {w ∈ {a}*| |w| ist weder durch 3 noch durch 5 teilbar }
die komplementär sprache L2 := {w ∈ {a}*| |w| ist durch 3 und durch 5 teilbar }
beide sprachen sind regulär denn man kann problemlos automaten konstruieren die diese akzeptieren. aber nach dem Pumpinglemma ist L2 nicht!! regulär!!!.
ich nehme ein wort z = a^(n+15) mit 15|n somit ist z elem L2.
z = uvw uv = a^n und w = a^15
betrachte ich dann uv^2w = a^naa^15 ist |uv^2w| = a^(n+1+15) und somit ist uv^2w kein element von L2 und d.h. L2 dürfte nicht regulär sein???
was mache ich also falsch
ich glaube:
wenn uv≤n dann folgt uv^2≤2n, also uv^2w=2n+15
mit deiner Annahme dass n teibat duch 15, folgt 2n auch teilbar durch 15
somit ist Regulaer
labro: beachte. dass das PL besagt “Es existiert (mindestens) eine zerlegung” Das heißt, du musst bei der Verwednung des PL zum Beweis der NICHTregularität einer Sprache nachweisen, dass für keine einzige Zerlegung das PL erfüllt ist. Du hast halt jetzt grade eine Zerlegung gewählt, für das die Eigenschaft III nicht erfüllt ist. Aber hast Du auch noch andere Zerlegungen geprüft? Dann wirst Du schnell eine finden, sodass das PL erfüllt ist.
Gruß,
Marco
vieleicht, aber ich wollte Dich darauf hinweisem, dass uv^2≤2n ist und nicht n+1, wie Du es gemacht hast, und dass es ne moegliche Fehler ist…ich hab nicht alles beruecksichtigt und alles ausprobiert
obwohl doch, immer wenn du n ( und n ist duch 15 teilbar) mit i multiplizierst, bekommst du eine Zahl die immer duch 15 teilbar ist, egal fuer welche Zerlegung.
denn uv^i≤in und somit : uv^iw= in + 15 und diese Laenge ist immer durch 15 teilbar und somit die Sprache Regulaer, was in der Tat ist.
Gruss,
dime
Wenn ich deine Sprache L invertiere krieg ich:
L2 = {…| |w| ist durch 3 ODER durch 5 teilbar}
denn:
L= {a^n | not(3|n) AND not(5|n) , n∈N}
L2= {a}* \ L = {a^n | not[not(3|n) AND not(5|n)] , n∈N} = (de Morgan)
= {a^n | (3|n) OR (5|n) , n∈N}
Wobei sich (a|b) als a teilt b liest.
Sind trotzdem alle regulär.
Außerdem: den Existenz- mit dem Allquantor zu verwechseln ist ein beliebter Fehler, den man aber tunlichst vermeiden sollte. Hier nochmal ein Hinweis, wie die beiden mittels klassischer Logik auseinander hervorgehen (dualität):
(not ∃x not φ(x) ) ≡ (∀xφ(x))
vorallem wie soll ich alle zerlegungen ausprobieren. reicht es nicht für ein z aus L zu zeigen dass es beim pumpen nicht mehr zu L gehört.
oft zeigt man dass für z = uvw elem L 1,2,3 erfüllt ist und für uv^2w ist bedingung 3 nicht erfüllt??
du musst es allgemein an einer Zerlegung zeigen. Aber das Wort darfste dir waehlen.
Die Stellen an denen man im Pumping Lemma sich was waehlen darf, sind all diejenigen wo ein Allquantor steht. das bedeutet fuer dich: wenn es fuer alle gilt, dann muss es auch fuer dieses bestimmte, von mir ausgewaehlte gelten. Das ist der Ansatzpunkt. Die Sachen wo dann da steht: es gibt eine Zerlegung… etc. da musst du extrem aufpassen. Die Zerlegung bestimmt sich selbst, nicht du. Wenn du ein bissl Kontrolle ueber deine Zerlegung haben willst musst du dein Wort geignet waehlen
Am coolsten is doch man zeigt das bei der Sprache über die Äquivalenzen, oder.