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.