Äuivalenzrelation beim DEA < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:46 Sa 09.07.2011 | | Autor: | abbc |
Hallo,
ich habe eine Frage zu den Äuivalenzrelationen. Ich habe einen DEA gegeben und möchte dazu jetzt die Äuivalenzrelation berechnen.
Im ersten Schritt Teile ich die Zustände in zwei Mengen auf, die Finalzustände und Nichtfinalzustände. Jetzt muss ich die Nichtfinalzustände weiter aufteilen, wie gehe ich da vor?
Hier ein Beispiel-DEA:
http://h6.abload.de/img/bildschirmfoto2011-07-v70g.png
Im ersten Schritt würde ich folgende Mengen erhalte:
{q0,q1,q2,q3}{q4,q5}
Im nächsten folgende:
{q0,q2}{q1,q3}{q4,q5}
Wie komme ich jetzt aber auf die Zerlegung der Nichtfinalzustände?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:33 Sa 09.07.2011 | | Autor: | felixf |
Moin!
> ich habe eine Frage zu den Äuivalenzrelationen. Ich habe
> einen DEA gegeben und möchte dazu jetzt die
> Äuivalenzrelation berechnen.
Um was fuer eine Aequivalenzrelation handelt es sich hier?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:51 So 10.07.2011 | | Autor: | abbc |
Es geht darum den DEA zu minimieren und durch bilden der Äquivalenzklassen sollten äquivalente Zustände erkannt werden und dadurch dann der minimierte DEA erhalten werden.
Was genau das für eine Aquivalenzrelation ist weiß ich nicht, wusste nicht das es doch unterschiedliche gibt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:45 Mo 11.07.2011 | | Autor: | geograf |
Hallo,
es gibt unter http://www.antigauss.de/inf/theor/minimierung_von_dfas.pdf ein recht anschauliches Beispiel, wie die Minimierung von DEAs funktioniert. Äquivalenzklassen werden so konstruiert, dass schrittweise Zustände, von denen aus die selben Wörter akzeptiert werden, zu einem neuen Zustand zusammengefasst werden (also in eine Äquivalenzklasse wandern). Dies wird wiederholt, bis sich nichts mehr zusammenfassen lässt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 So 24.07.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
