Reguläre Sprache beweisen

Question

weiß jemand ob die Sprache regulär?

L = {a^n b^m | 0 < n ≤ m ≤ 2n}

und wie beweist man das richtig?

Lg

Comments

Aloha :)

Jede endliche Sprache ist regulär. Du müsstest also zeigen, dass die Anzahl der Wörter der Sprache durch die Wahl von \(n\) begrenzt ist (vollständige Induktion).

Aber die Frage dürfte in der Stacklounge besser aufgehoben sein ;)

Answer 1

Die Sprache ist nicht regulär, weil man mit Automaten nicht zählen kann, wie lang der \(a^n\)-Präfix ist.

Nicht-regularität beweist man oft mit dem Pumping-Lemma.