Pumping Lemma Typ 2?
Pumping Lema für kontextfreie Sprachen Typ 2.
Das Wort z lässt sich in uvwxy zerlegen und |z| >= n
Untere Grafik:
=> Eine Variable muss doppelt vorkommen. Klar!
=> Unteres A wird vom oberen A abgeleitet. Klar!
|vx| darf nicht leer sein => Vorgegeben. A -> AB über ok.
Fragen:
=> Warum teilt sich A immer "genau" in vwx auf? Warum nicht in uvw oder wxy?
Wenn ich pumpe wächst mein v und mein x. d. h.
uv^iwx^iy
Nehmen wir ich habe das Wort z = abababab d. h. n = 8
=> Wie soll man jetzt hier uvwxy wählen um zu zeigen, dass das Wort das PL erfüllt oder nicht. Wie geht man hier am besten vor. Mir ist dies ehrlich gesagt nicht verständlich, wie ich hier vorgehen soll.
1 Antwort
öhm? in der WP liest sich das etwas anders... https://de.wikipedia.org/wiki/Pumping-Lemma
und „uv^iwx^iy“ ist nicht regulär... oder? jedenfalls nich für beliebiges „i“... sonst müsste das Ding ja mitzählen, wieoft v kam... oder?
oh... das steht weiter unten... https://de.wikipedia.org/wiki/Pumping-Lemma#Kontextfreie_Sprachen
das mit dem „A“, das immer „vwx“ wird, bezieht sich eben auf den Ausschnitt des Baums, für den es gilt... so würde ich mal die WP-Bildchen interpretieren...
allerdings ist mir das etwas zu hoch, obwohl ich es mal gelernt habe... es ist total schwierig für mich...
vielleicht steht es in nem Lehrbuch noch besser als in der WP? hat euer Prof euch ein Lehrbuch empfohlen? gibt bestimmt noch ein Exemplar in der Bib zum Ausleihen für umsonst...
Etwas ja. Dort ist es jedenfalls einigermaßen verständlich erklärt, wenn man sich mit der Materie etwas auskennt.
Im Buch sind zum Teil die Erklärungen noch schlimmer als die vom Prof, obwohl die Erklärungen des Profs schon nicht (gerade) gut sind.
Trotzdem Danke! Die Profs haben irgendwie keine Ahnung wie es ist, wenn man sich mit den Dingen das erste mal Beschäftigt. Die machen des seit x Jahren, dann kenn ich des auch alles in und auswendig.
Naja, leider ist es so.