hallo, wofür genau ist nochmal die natürlicher zahl (pumping length) gut?
ah schreibt doch einfach mal alles was euch dazu einfällt bitte.
ich bin grad ein bisschen wirr…

Das ist eine frei wählbare Zahl, für die gilt:
|w|>=n
Nehmen wir als Beispiel die Sprache a^m*b^2*c^m (m aus N)
Ein (einfaches)Wort aus der Sprache wäre: a^n*b^2*c^n (n aus N)
|w|= n +2 +n =2n +2 >= n(Pumping-Länge)
Du könntest auch 2n als Pumping-Länge nehmen oder n/2 oder sogar 2n+2.Das tut man aber einfachheithalber nicht.Du sollst dir die Länge so wählen, dass es dir möglichst leicht fällt, den Widerspruchsbeweis durchzuführen.

Ein anderes Beispiel: a^2*b^3*c^4 es gibt also keine Variablen, somit wird die Sprache von einem einzigen Wort gebildet.
|w|=2+3+4=9
Ich wähle mir als P-Länge (n=)2
1.|uv|>= 1
2. |v| größer Null
3. für ein beliebiges i aus N muss u*v^i*w aus der Sprache sein.Wenn ich als i 100 wähle, dann ist ein so gebildetes Wort nicht drin.
Wenn eine Sprache von einem einzigen Wort gebildet wird, dann muss man so einen Widerspruchsbeweis erst gar nicht aufstellen, weil es offensichlich ist.
Ich wollte dir aber mit diesem besonderen Beispiel zeigen, dass die Pumping-Länge auch eine Zahl sein kann-wenngleich selten.

Wenn eine Sprache von einem einzigen Wort gebildet wird, dann muss man so einen Widerspruchsbeweis erst gar nicht aufstellen, weil es offensichlich ist.

Stimmt. Endliche Sprachen sind offensichtlich regulaer, also kontextfrei. Also ist offensichtlich an Deiner Argumentation was faul.

Hab das hier grad gefunden. Ich finde, da wird das Ganze recht gut erklärt.
http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS01/F2/Files/uvw-web-Dateien/uvw-web1.html

Das ist eine frei wählbare Zahl, für die gilt:
|w|>=n

Bitte was? Also für den Widerspruchsbeweis ist die Pumping-Länge
ganz und gar nicht frei wählbar. Das Lemma sagt nur, dass eine
solche existiert, d.h. dein Beweis muss für jedes n zeigen, dass ein
Widerspruch eintritt.

Nehmen wir als Beispiel die Sprache a^m*b^2*c^m (m aus N)

Vermutlich meinst du die Sprache [latex]\{a^mb^2c^m\mid m\in\mathbb{N}\}[/latex]…

Ein (einfaches)Wort aus der Sprache wäre: a^n*b^2*c^n (n aus N)
|w|= n +2 +n =2n +2 >= n(Pumping-Länge)
Du könntest auch 2n als Pumping-Länge nehmen oder n/2 oder sogar 2n+2.

Nein, die Pumping-Länge kann man nicht wählen. Du kannst höchstens das Wort, auf
das du das Pumping-Lemma anwendest in einem gewissen Rahmen wählen, es muss nur
|w|>=n erfüllen, wobei n die Pumping-Länge ist.

Ein anderes Beispiel: a^2*b^3*c^4 es gibt also keine Variablen, somit wird die Sprache von einem einzigen Wort gebildet.
|w|=2+3+4=9
Ich wähle mir als P-Länge (n=)2

Genau an der Stelle ist der Beweis falsch. Die Pumping-Länge ist in dem Fall schlicht
nicht 2, sondern z.B. 10. Mit der (falschen) Zahl 2 bekommst du als Ergebnis, dass diese
Sprache nicht regulär ist, aber das ist sie.

1.|uv|>= 1
2. |v| größer Null
3. für ein beliebiges i aus N muss u*v^i*w aus der Sprache sein.Wenn ich als i 100 wähle, dann ist ein so gebildetes Wort nicht drin.
Wenn eine Sprache von einem einzigen Wort gebildet wird, dann muss man so einen Widerspruchsbeweis erst gar nicht aufstellen, weil es offensichlich ist.

Wie UncleOwen schon sagte: Wenn die Sprache endlich ist, ist sie eh regulär.

Ich wollte dir aber mit diesem besonderen Beispiel zeigen, dass die Pumping-Länge auch eine Zahl sein kann-wenngleich selten.

Huch? Die Pumping-Länge ist immer eine Zahl…

irgendwie bin ich grad total dumm glaub ich,wo ist mein denkfehler?
-Das Pumping Lemma ist notwendig für Reguläre Sprachen.
-Reguläre Sprachen werden durch Typ3 Grammatiken erzeugt und können durch Reguläre Ausdrücke dargestellt werden.
Wenn man jetzt z.B. das Alphabet = {a} hat, dann ist {a} ein regulärer Ausdruck, die Produktionsregel wäre also: {S -> a}.
und das einzige Wort das diese Sprache hat ist w = a.
aber diese Sprache erfüllt doch nicht das Pumping Lemma, aber wenn das doch notwendig ist?!

Doch, die Sprache erfuellt das Pumping-Lemma. Mit Pumpinglaenge 2 gibt es einfach kein w, das die geforderte Laenge hat - und damit ist der Rest automatisch erfuellt.

Wie sieht das für die Sprache:
L = { a^i b^j | i < j }
Wäre das ein Beispiel für eine Sprache die nicht regulär ist und trotzdem pumpbar?
Ich habe zumindest keine Zerlegung gefunden, die das Wort aus L katapultiert.

Wie sieht das für die Sprache:
L = { a^i b^j | i < j }
Wäre das ein Beispiel für eine Sprache die nicht regulär ist und trotzdem pumpbar?

Genau, die ist nicht regulär und erfüllt trotzdem das Pumping-Lemma.

Edit: Falschen Kommentar gelöscht.

Ich habe zumindest keine Zerlegung gefunden, die das Wort aus L katapultiert.

Also für einige Zerlegungen führt das Pumpen tatsächlich aus der Sprache heraus,
sobald nämlich v ein a enthält.

Wie sieht das für die Sprache:
L = { a^i b^j | i < j }
Wäre das ein Beispiel für eine Sprache die nicht regulär ist und trotzdem pumpbar?

Genau, die ist nicht regulär und erfüllt trotzdem das Pumping-Lemma.
Wenn K nicht regulär ist, hat man in [latex]K'=K\cdot\{a\}\{b\}^+[/latex]
immer eine Sprache, die auch nicht regulär ist, aber das Pumping-Lemma
erfüllt.

Ich habe zumindest keine Zerlegung gefunden, die das Wort aus L katapultiert.

Also für einige Zerlegungen führt das Pumpen tatsächlich aus der Sprache heraus,
sobald nämlich v ein a enthält.

Huch…?…
Die Sprache [latex]L\ :=\ \{a^i\cdot b^j \mid i,j\in {\mathbb N} \land i<j\}[/latex]
ist, wie richtig bemerkt, nicht regulär.
Aber das Pumping Lemma IST anwendbar um dies zu zeigen!!
(mehr LaTex scheint bald nicht mehr zu gehen, also nur Pseudo-LaTeX ab jetzt, sorry)

Sei n die Zahl, die existieren würde, wenn L regulär wäre.
Dann müsste das Wort z := a^{n}b^{n+1} aus L zerlegbar sei in z = uvw,
wobei  0<|v|<n. (ich nehme eine simple Pumping-Lemma Version, bei der wenig Einschränkungen existieren!)
Würde in solch einer Zerlegung das Wort v die Form v=a^{r}b^{s} (0<r,s<n) besitzen,
so wäre das Wort uvvw nicht mehr in L, denn das wäre doch v=a^{n}b^{s}a^{r}b^{n+1}.
Würde in solch einer Zerlegung das Wort v die Form v=a^{r} (0<r<n) besitzen,
so wäre das Wort uvvw nicht mehr in L, denn das wäre doch v=a^{n+r}b^{n+1}, mit n+1=<n+r.
Würde in solch einer Zerlegung das Wort v die Form v=b^{s} (0<s<n) besitzen, so wäre das Wort uw nicht mehr in L, denn das wäre doch v=a^{n}b^{n+1-s}, mit n+1-s=<n.
Da es keine weitere Möglichkeit einer Zerlegung von z gibt, die zu keinem Widerspruch führen würde, kann L nicht regulär sein.

Würde in solch einer Zerlegung das Wort v die Form v=b^{s} (0<s<n) besitzen, so wäre das Wort uw nicht mehr in L, denn das wäre doch v=a^{n}b^{n+1-s}, mit n+1-s=<n.

Oh, stimmt! Den Fall, v ganz wegzulassen, habe ich übersehen.

Edit: Dann muss das oben in [latex]K'=K\{c\}^+\cup\Sigma^*[/latex]
geändert werden, wenn [latex]c\notin\Sigma[/latex] und [latex]K\subseteq\Sigma^*[/latex].