Äquivalenz überprüfen

Question

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

Answer 1

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)