Informatiker Board | formale Sprachen | Nerode-Äquivalenzklassen

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Der letzte Beitrag

Leyla

Nerode-Äquivalenzklassen

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?