Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Minimierung allgemein

0 Punkte
33 Aufrufe

Hallo,

wenn man einen endlichen Automaten "minimiert" hat und er dann gleich viele Zustände hat wie vor der Minimierung, ist es dann möglich, dass er sich (Kanten, ...) geändert hat
oder ist dann zwangsläufig der zu minimierende Automat schon der minimierte Automat? Kann man im letzten Fall sagen, dass der ursprüngliche Automat minimierbar ist, wenn er sowieso schon dem endgültigen minimierten Automaten entspricht?

Gefragt 23, Okt 2014 in MIN-AC von uxcyx uxcyx Tutor(in) (104,810 Punkte)  

Eine Antwort

0 Punkte

Hallo,

Sie sprechen vermutlich von deterministischen endlichen Automaten. Für diese ist die Anzahl der Kanten gleich der Anzahl der Zustände mal der Anzahl der Eingabezeichen - es macht also keinen Sinn, die Kantenanzahl minimieren zu wollen. Wenn durch den Minimierungsalgorithmus kein Zustand wegfällt, dann war der zu minimierende Automat schon minimal.

Viele Grüße

Lukas König, Friederike Pfeiffer-Bohnen

Beantwortet 23, Okt 2014 von uxcyx uxcyx Tutor(in) (104,810 Punkte)  
...