Informatiker Board | formale Sprachen | Nerode-Äquivalenzklassen

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Nerode-Äquivalenzklassen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Nerode-Äquivalenzklassen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Leyla
unregistriert

Nerode-Äquivalenzklassen

Zitatantwort auf diesen Beitrag erstellen

Meine Frage:
Gegeben ist eine Sprache [latex]L_k[/latex]

ü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 [latex]L_2[/latex]

und geben sie für jede einen Regulären Ausdruck an.
2. Wie viele Nerode-Äquivalenzklassen hat [latex]L_k[/latex]

?

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 [latex]L_2[/latex]

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] = b*aa*b[/latex]$

Ist das so richtig?

30.01.2013 09:09

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Nerode-Äquivalenzklassen