Nerode-Äquivalenzklassen

30.01.2013, 09:09	Auf diesen Beitrag antworten »
Leyla	Nerode-Äquivalenzklassen Meine Frage: Gegeben ist eine Sprache über dem Alphabet $[latex]A=\left\{ a,b\right\} ^{}[/latex]$ für $[latex]k\in \mathbb N _+[/latex]$ . Das k-letzte Zeichen eines Wortes $[latex]w\in L_k[/latex]$ ist ein a. 1. Bestimmen sie alle Nerode-Äquivalenzklassen von und geben sie für jede einen Regulären Ausdruck an. 2. Wie viele Nerode-Äquivalenzklassen hat ? Meine Ideen:* Stimmt es, dass wenn ich einen Minimalen-Automaten habe, der die Sprache akzeptiert, dass ich genau so viele Nerode-Äquivalenzklassen haben wie Zustände? Dann denke ich wären es für 4 Nerode-Äquivalenzklassen. $[latex]q_0: \left[b\right] = b[/latex]$ $[latex]q_1: \left[a\right] = b a \left(b\left(ba\right)* a \right)[/latex]$ $[latex]q_2: \left[aa\right] = b aa a[/latex]$ $[latex]q_3: \left[ab\right] = baa*b[/latex]$ Ist das so richtig?

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »