Nerode-Äquivalenzklassen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Wandele einen Regulären Ausdruck, z.B. (1((10*2)* + 0*)2 + 0*)*, in einen DFA minimaler Größe um. Bestimme dafür zuvor die Nerode-Äquivalenzklassen. |
Hallo, ich weiß zwar wie die Nerode-Relation definiert ist, habe aber leider allgemein keine Ahnung wie man aus einem regulären Ausdruck die Äquivalenzklassen bestimmt.
Wär super, wenn mir da jemand helfen könnte.
Viele Grüße Julia
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und guten Morgen Julia,
Du könntest so vorgehen:
Konstruier Dir erst mal einen NFA fuer die Sprache (mal ihn ruhig hin, d.h. sein Zustandsdiagramm). Das sollte gut gehen.
Dann bezeichne zu zwei bel. Zuständen [mm] s_1,s_2 [/mm] des konstruierten Automaten [mm] L(s_1,s_2) [/mm] die Menge aller Woerter x aus [mm] \{0,1,2\}^*,
[/mm]
so dass der Automat, wenn er in Zustand [mm] s_1 [/mm] startet und das Wort x liest, am Ende in Zustand [mm] s_2 [/mm] gelangen kann (d.h. es gibt einen Pfad im
Zustandsdiagramm von [mm] s_1 [/mm] nach [mm] s_2, [/mm] dessen Kanten mit x beschriftet sind).
Sei F die Endzustandsmenge des Automaten, dann nennen wir zwei Zustaende [mm] s_1, s_2 [/mm] aequivalent genau dann, wenn fuer jedes Wort x gilt:
Es gibt einen x-Pfad von [mm] s_1 [/mm] nach F genau dann, wenn es einen x-Pfad von [mm] s_2 [/mm] zu F gibt, d.h.
[mm] L(s_1,F):=\bigcup_{t\in F}L(s_1,t)\:\:\: =\:\:\: L(s_2,F)
[/mm]
Sei [mm] s_0 [/mm] der Startzustand des Automaten. Dann gilt:
Die Vereinigungen
[mm] \bigcup_{s'\:\:äquivalent\:\: zu\:\: s} L(s_0,s')
[/mm]
sind die Äquivalenzklassen der Nerode-Relation, und Du solltest den minimalen Automaten erhalten, indem Du bei obigem Automaten alle
äquivalenten Zustände zu je einem kontrahierst.
Frohes Schaffen wünscht
Mathias
|
|
|
|
