0 Daumen
34 Aufrufe

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

vor von

1 Antwort

0 Daumen
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 = akbman}

von einem Automaten erkannt werden.

vor von 1,7 k  –  ❤ Bedanken per Paypal

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...