Pumping-Lemma für {a^n b^m}

Question

Wie kann ich mit dem Pumping-Lemma beweisen, dass folgende Sprache nicht regulär ist?

$$ L=\left\{ { { a }^{ n }{ b }^{ m } }|{ n\neq m } \right\} $$

Answer 1

Wie kann ich mit dem Pumping-Lemma beweisen, dass folgende Sprache nicht regulär ist?

Diese Aufgabe ist alles andere als trivial. Viele versuchen einen Umweg am Pumping-Lemma vorbei. Mein Vorschlag mit einer direkten Anwendung des Pumping-Lemmas ist Folgender:

Sei \(p\) die Pumping-Lemma-Zahl. Wähle \(w = a^p b^{p + p!}\in L\) und

\(\forall k\geq 0: xyz=a^{p-u}a^{uk}b^{p+p!}\in L\) mit \(0<u\leq p\)

Mit der ganzen Zahl \(k=1+\frac{p!}{u}\)* folgt:

\(a^{p+p!}b^{p+p!}\notin L\) \(\square\)

*\(k\) ist eine ganze Zahl, da \(\frac{p!}{u}\) eine ganze Zahl ist, denn \(0<u\leq p\).

Comments

Oh ok da habe ich wahrscheinlich einen Denkfehler gehabt. Der ursprüngliche Ausdruck war

$$\overline { \left\{ { { a }^{ n }{ b }^{ n } }|{ n>0 } \right\}  } $$

Ich bin davon ausgegangen, dass man die Negation durch den o.g. Ausdruck auflösen kann.

---

Ich bin davon ausgegangen, dass man die Negation durch den o.g. Ausdruck auflösen kann.

Also willst Du eigentlich zeigen, dass die Sprache

\(L=\{a^nb^n\mid n\leq 0\}\)

nicht regulär ist? Falls ja, stelle diese Aufgabe bitte als neue Frage ein. Danke.