Abdeckung eines Zustandsautomaten - Erreichbarkeitsanalyse

[diz]

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.

[U-- °LoneWolf°]

Das hört sich an als könnte man es mit Backtracking lösen.

Due gehst alles ausgahngzustände und alle unterzustände durch bsi du nicht weiter kommts und merkst die nwo du nicht mehr weiter gekommen bist.

[Der Kleine]

Wenn ich es richtig verstanden habe:

Erreichbar ist ein zusatnd nur, wenn er einen Vorgänger hat.

Also müssen alle errecihbaren Zustände zumindest einen Vorgänger besitzen oder selbst Startvorgang sein.

Wenn er auch einen Vorgänger hat, so muß sicher gestellt sein, das er nicht in einem Kreis (beliebiger Länge) gefangen ist: also 2 - 3 - 4 - 2, bzw. muss geschaut werden, ob in diesem Kreis der Startzustand beinhaltet ist, bzw. ob es weitere Zugänge zu diesem Kreis gibt.

Sofern alle verbleibenden Zustände einen Kreis bilden, muß der Startzustand innerhalb dieses Kreises liegen.

Mehr Möglichkeiten gibt es IMO nicht, so daß die Überprüfung damit beendet wäre.