Pumping Lemma

Aufrufe: 159     Aktiv: 24.06.2021 um 09:16

0

Hallo zusammen,

Leider verstehe ich nicht ganz. Wie das mit dem Pumping Lemma genau funktioniert. Was mir klar ist, es ist eine Beweisführung, welches aufzeigt, dass eine Sprache nicht regulär ist und dies mit dem DFA nicht gebaut werden kann.

Um die Beweisführung zu starten, muss folgendes beachtet werden:

1) y >= 1 darf nicht leer sein 2) |xy| <= p (Anzahl der Länge p) 3) for each i >= 0 xy^iz element of A

a^mb^m

Irgendwie muss ich a^mb^m zerlegen, dafür muss ich nun ein String definieren:

aabb aaabbb

x = a^p z = b^p

Wie bestimme ich nun y?

Kann mir jemand Schritt für Schritt erklären, wie das geht?

EDIT vom 24.06.2021 um 09:16:

enter image description here die gelb markierten Stellen verstehe ich nicht!

Diese Frage melden
gefragt

Student, Punkte: 64

 

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
Kommentar schreiben
1 Antwort
0

Hallo, hier mal der Beweis bei Fragen einfach melden

enter image description here

wenn man v=a^ib^i wählen würde müssste man auch sicherstellen dass es nicht größer wird als n

Diese Antwort melden
geantwortet

Punkte: 55

 

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?

  ─   sayuri 19.06.2021 um 12:08

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 l
2+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

  ─   carlos 22.06.2021 um 17:58

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

  ─   carlos 22.06.2021 um 18:09

Kommentar schreiben