Nerode-Lemma und Automaten

Question

Hallo,

wir sollen mithilfe des Nerode Lemmas zeigen, dass man mit der folgenden Sprache keine endlichen Automaten erkannt werden kann:

L = {w ∈ Σ* | ∃k ≤ m ≤ n : w = a^(k) b^(n) a^(m)}

die Sprache L ist undenlcih lang, da man mit w beliebig lange und viele Worte bauen kann und dadurch würde der Automat ja unendlich viele Zustände haben. Demnach ist die Sprache L also nicht regulär.

Ich weß aber nicht wie ich das der Aufagbenstellung entsprechend lösen soll. Würde mich über eine helfende hand freuen.

LG

Answer 1

da man mit w beliebig lange und viele Worte bauen kann und dadurch würde der Automat ja unendlich viele Zustände haben.

Dass man beliebig lange und viele Worte bauen kann, ist nicht hinreichend dafür, dass die Sprache nicht von einem Automaten erkannt werden kann. Zum Beispiel kann die Sprache

        {w ∈ Σ* | ∃k,m,n : w = a^kb^maⁿ}

von einem Automaten erkannt werden.