search

knowsys / FormaleSysteme

Unterlagen zur Vorlesung "Formale Systeme", Fakultät Informatik, TU Dresden
https://iccl.inf.tu-dresden.de/web/Formale_Systeme
44 stars 14 forks source link

Frage zu Äquivalenzklassen #39

Closed tidenhub closed 6 years ago

tidenhub commented 6 years ago

Hallo, ausgehend von Vorlesung 9 sollte es möglich sein, eine DFA ML zu konstruieren, sodass die Anzahl der Zustände in ML dem Index von ≃ entspricht.

Für das Beispiel in Vorlesung 8 sollte es mir dann möglich sein, eine ML mit 4 Zuständen zu zeichnen. image

Mein Ansatz wäre folgender, aber da habe ich 5 Zustände. dsc_0622

Wie würde ein passender ML für dieses Beispiel aussehen?

mmarx commented 6 years ago

Die Aequivalenzklassen [ab] und [ba] sind gleich, da ja ba ∈ [ab] gilt. Entsprechend ist auch [ba] dann kein neuer Zustand, die a-Kante vom [b]-Zustand aus geht also eigentlich zum Zustand [ab].

tidenhub commented 6 years ago

Okay, aber was ist mit den restlichen Übergängen, damit der DFA wieder total wird? dsc_0624

mmarx commented 6 years ago

Die blauen Übergänge gegen alle zu [b], da sowohl ab, bb, aba wie auch abb in [b] liegen.

tidenhub commented 6 years ago

Okay, aber dann erzeugt der Automat ML nicht mehr die Sprache L!? z.B. bba könnte man dann mit ML erstellen.

mmarx commented 6 years ago

Das stimmt. Tatsächlich ist [b] eine weitere Äquivalenzklasse, wir werden das Beispiel korrigieren.

mmarx commented 6 years ago

Das Beispiel ist jetzt korrigiert, der Automat bekommt dann einen weiteren Zustand [bb], zu dem genau alle blauen Uebergaenge im Bild oben fuehren.