Gegeben ist ein Zustandsautomat (State-Machine) mit einer Anzahl von
Zuständen (States) und Zustandsübergängen (Transitions).
Einer der Zustände ist der Startzustand.
Alle Zustände sind auf irgendeinem Weg vom Startzustand aus erreichbar.
Problem:
Es fallen nun ein oder mehrere Zustandsübergänge weg. Die Folge ist, daß
möglicherweise nicht mehr alle Zustände erreichbar sind.
Die Frage ist nun, wie kann man ermitteln, welche Zustände noch
erreichbar sind? Gibt es einen einfachen Algorithmus dafür?
Die Übergangsmatrix ist bekannt. (In dieser Matrix steht, welcher Zustand eine
Verbindung zu einem anderen Zustand hat).
Beispiel:
1 2 3 4 5
------------------
1 | 0 1 0 0 1
2 | 1 0 0 1 0
3 | 0 1 0 0 0
4 | 0 0 1 0 0
5 | 1 1 1 1 0
Erklärung: Man kann z.B. von Zustand 1 nach ustand 2 oder 5.
Jetzt fällt plötzlich der Übergang von Zustand 1 nach Zustand 2 weg.
Welche Zustände sind dann noch erreichbar? Gesucht ist ein einfaches Verfahren.
Vielen Dank.