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!
 

 

Äquivalenz überprüfen

0 Punkte
51 Aufrufe

Hallo,

kann mir jemand die b) etwas genauer erklären. Woher weiß ich, dass wenn ich einen anderen Startknoten wähle, dann nur die Bedingung gelten muss, dass man von diesem aus zu so kommt. Wieso muss ich da nicht noch die Äquivalenzen überprüfen? es gibt doch vom neuen Startknoten aus andere Pfeile da könnte doch sein, dass ein Zustand auch äquivalent mit einem anderen ist? Oder was denke ich falsch?

Vielen Dank

Gefragt 22, Okt 2014 in MIN-AG von uxcyx uxcyx Tutor(in) (104,810 Punkte)  

Eine Antwort

0 Punkte
Hallo,

wenn du dir den Algortihmus zur Minimierung ansiehst, dann erkennst du schnell, dass dieser unabhängig vom Startzustand ist.

Die einzige Änderung findet bei der Eliminierung nicht-erreichbarer Zustände statt. Da man von jedem Knoten aus zu s0 kommt, kommt man eben auch zu allen Knoten, von denen man von s0 aus kommt. Zudem hat keiner der Knoten einen Pfeil zu s6. Somit ändert sich die Eliminierung bei s1,..., s5 nicht und man kann den Algorithmus wie gehabt durchführen.

Betrachtet man allerdings s6 als Startzustand, so ist s6 zum ersten Mal auch ein erreichbarer Zustand. Somit muss der Algorithmus angepasst werden, um auch s6 zu beinhalten. Das Egebnis ändert sich hier nur deshalb nicht, weil s6 äquivalent zu einem anderen Zustand ist.

Viele Grüße

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