0 Daumen
355 Aufrufe

weiß jemand ob die Sprache regulär?

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

und wie beweist man das richtig?

Lg

Avatar von

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 ;)

1 Antwort

0 Daumen

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.

Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community