pumping lemma
-
hallo
brauche mal eben eine kopfwäsche.
wenn ich eine sprache habe, sprich: L= a ^ m, und m ist eine Quadratzahl
dann ist mir klar, dass diese sprache keine reguläre sprache ist.nun funktioniert das pumping lemma ja wie folgt:
sei L regulär, dann gibt es eine Zahl n, so dass sich alle wörter x aus dieser sprache L mit laenge von x >= n zerlegen lassen in
x = uvw, so dass folgende eigenschaften erfüllt sind:
1. laenge von v >=1
2. laenge von vw <= n
3. für alle i= 0,1,2 ... gilt u v^i w gehören zur Sprache Lok, sei zum beispiel x = a ^ n ^ 2. (n hoch 2 == quadratzahl)
ich sehe, dass
1 <= laenge v <= laenge uv <= n (bedingung 1 und 2)aber wenn ich i = 2 setze, dann gilt nach bedingung 3:
u v^2 w muss element von L sein.ich sehe ein, dass da ein hacken besteht, nach aufmalen mit zuständen...
das "aufpumpen" geht nicht.nur ist das kein beweis.
ich finde einen beweis in einem buch nach langem recherchieren, aber:
den versteh ich nicht, wahrscheinlich wegen einer banalen mathematischen grundlage, die mir wiedermal fehlt ...n^2 = laenge x = laenge uvw < laenge u v^2 w <= n^2 + n < n^2 + 2n +1 = (n+1) ^2
ich verstehe die abschätzung nicht (die stelle, die hervorgehoben ist, der rest ist mir einleuchtend). wie kommt man darauf? (sorry, wenn es banal sein sollte)
thxps: sorry für fehlende latex tags.. grad zu müde..
-
elise schrieb:
2. laenge von vw <= n
[...]
n^2 = laenge x = laenge uvw < laenge u v^2 w <= n^2 + n < n^2 + 2n +1 = (n+1) ^2
Also:
1. n^2 = laenge uvw.
2. laenge von vw <= n. Somit ist auch die Länge von v <= n.
3. laenge uvw + laenge v = laenge uv^2w <= n^2 + n.
Das n kommt hierbei von der Abschätzung der Länge von v.
-
ich glaube, ich war gestern abend wohl blindigst...
es ist logisch, dass n^1 kleiner ist als n^2+n
was mir nur sorge macht: ich wäre nie auf diesen beweisansatz gekommen, ich habe dauernd nur rumgemalt.. und intuitiv gesehen, dass es keine reguläre sprache ist.
menno, die hinterlistigen mathegenies holen mich wieder ein...
danke erstmal
elise, die mathelooserin..
