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

Vorlesung 6: Unnötiger Zustand im NFA? #38

Closed JuKu closed 6 years ago

JuKu commented 6 years ago

Ich bin mir nicht sicher, ob ich selbst nur falsch gedacht habe oder ob es ein Fehler ist. In der Vorlesung 6 auf Folie 21 ist in meinen Augen ein unnötiger Zustand zu finden (4), wieso wird dieser nicht weggekürzt?

sl

Es handelt sich sowieso nicht um einen Endzustand, weshalb dieser gleich zu qf führen sollte.

mmarx commented 6 years ago

Die kompositionelle Methode konstruiert zu einem gegebenen regulaeren Ausdruck einen aequivalenten NFA. Aus Automaten fuer Grundfaelle werden dabei schrittweise groessere Automaten fuer kompliziertere (Teil-)Ausdruecke zusammengesetzt. Dabei werden ε-Uebergaenge entfernt, andere Uebergaenge und insbesondere saemtliche Zustaende bleiben jedoch erhalten. Der entstehende NFA ist daher im Allgemeinen nicht minimal.

JuKu commented 6 years ago

Vielen Dank! Aber wird in der Klausur dann ein minimaler Automat gefordert, oder kann man diesen so stehen lassen?

mmarx commented 6 years ago

Was genau gefordert wird, haengt von der Formulierung der Aufgabenstellung ab. Wird (nur) ein aequivalenter NFA gefordert, muss dieser nicht minimal sein. Wuerde explizit die kompositionelle Methode verlangt, waere hier fuer »a|ba*« ein minimaler NFA sogar falsch (denn es ensteht ja eben ein nicht-minimaler NFA).