0 Daumen
99 Aufrufe

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\} $$

Gefragt von

1 Antwort

+1 Punkt
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\).

Beantwortet von 7,0 k

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...