Sprache mit Pumpinglemma beweisen

Razorhawk · Gast

Hi ihr da

Hab hier eine Sprache die ich mit dem Pumpinglemma beweisen muss.

L = {a^(w)b^(!w) : 1 <= w } für jedes z aus L

An sich braucht mir keiner wirklich sagen wie das PL funktioniert, aber
vielleicht könnte mal einer darauf gucken und mir einen Tipp geben wie groß |z| sein sollte (natürlich z >= n ... das ist klar) wählen könnte, damit das aufgeht.
Brauch nur den Anstoss, der rest ist eh einfach.

Wenn jemand ne Idee hätte, wäre ich begeistert!

Razorhawk

Razorhawk · Gast

Ich hab gerade eine Möglichkeit gefunden!

Vielleicht könntet ihr ja mal rüber gucken und sagen obs so stimmen könnte... ich bin zumindest zufrieden mit der Lösung:

Also nach PL gibt es ein wort uvwxy das folgende Eigenschaften hat

(Bedingung 1 und 2) Es gilt laut PL 1 <= vx <= vwx <= n

sei also

|z| = (n + n!)

nach Bedingung 3 gilt dann natürlich uv²wx²y ist in L,

mit einer Abschätzung gilt aber:

|z| = (n + n!) = |uvwxy| < |uv²wx²y| <= (n² + n!) < (n * n!) < (n+1) (n!) = (n+1)! < ( (n+1) + (n+1)! )

somit kann nach dieser Abschätzung uv²wx²y nicht in L sein. !Widerspruch --> L ist somit nicht regulär.