Vielen Dank für deine Antwort. Also muss man ein wenig mit v ausprobieren, bis es nicht in der Sprache ist?
Also in deiner Beweisführung hast du v= b^i gewählt, damit ein Teil herausfliegt? Würde dies auch mit v = a^i gehen? Dann würde u einfach leer sein? Könntest du noch ein Beispiel geben?
die regel |uv| <=n besagt ja das es nicht größer als n sein darf, also muss u leer sein bei a^i .
Ein anderes Beispiel wäre die Sprache L= {(01)^n2^n|n>=0}
Sei p \in N beliebig. Wähle x=(01)^p 2^p dann ist |x| =2p > p.
Seien u,v,w \in sigma mit x =uvw...... alle bedingungen siehe oben.
Wähle v=(01)^i, i \in N
Dann ist x in der Form x=(01)^i 2^p
Wähle i=0, dann ist x = uv^0w = 2^p => x ! \in L
Da man v nicht beliebig pumpen kann ist die Sprache nicht regulär.
Wenn du unbedingt u nicht leer haben möchtest, dann musst du dein v so einschränken, dass |uv| =< p bleibt. zb. durch : Sei u= (01)^l und v = (01)^i. l,i \in N Wähle l,i so, dass l2+i*2 =< p gilt. Ob das formal alles perfekt ist leg ich meine hand nicht ins feuer. Ich hab mir bei dem mal-2 gedacht, da p immer um 1 kleiner ist, als der vordere Teil muss, l und i auch dementsprechend kleiner sein. Diese einschränkung könnte auch bei dem eigt. beweis fehlen aber bin mir gerade nicht sicher. Ansich macht des dem ganzen kein Abbruch dass nur formale feinheiten sind
Und ja du suchst beim pumping Lemma immer nach einem v sodass es nicht mehr in der Sprache drinne ist. Wenn es nicht klappt hast du entweder woanders ein Fehler also du hast dein v falsch gewählt oder die Sprache ist regulär. Das Prinzip ist, dass du in einem DEA irgendwann in eine Schleife gerätst, also zb. bei a^n b^p. Ließt du ja mit einem Zustand alle deine a`s weg und bleibst in dem Zustand wo du gerade bist. Wenn du jetzt an deinem Wort hinter den a's beliebig viele a's dran hängst, dann bleibt dein DEA einfach länger in dem einen Zustand bis er irgendwann ein b ließt und dann in den nächsten Zustand übergeht. Da ist es dann wieder das gleiche er ließt in dem einen Zustand solange die b's in einer Schleife bis keins mehr da ist und wenn das Wort zu ende ist akzeptiert er das Wort. Also ist dem DEA egal ob du "abb" oder "aaaaaaabb" oder "abbbbbbbbbbbb" reingibst er akzeptiert immer. Also egal welches Teilwort du aus der gegebenen Sprache nimmst und dieses Teilwort entfernst oder duplizierst du fliegst niemals aus der Sprache. Du darfst dabei natürlich nicht aus dem Anfang ein a herausnehmen und hinten anfügen sondern nur ein Teilwort dir anschauen zb. das genannte a und an der Stelle wo es steht beliebig oft wiederholen. Du wirst eben feststellen das du bei regulären Sprachen nie aus der Sprache fliegen wirst. Dieses Prinzip machst du dir beim Pumping Lemma zu nutze
Markdown wird unterstützt.
man wählt y immer so das wenn man y pumpt das man später im beweis aus der sprache fliegt.
─ carlos 14.06.2021 um 15:21