Zustandspfad

Zustandspfad bezeichnet in der Informatik eine Folge von Zuständen, die ein System während einer Ausführung durchläuft. Er tritt in Zustandsmaschinen, endlichen Automaten und formalen Spezifikationen auf und dient dazu, das Verhalten des Systems schrittweise abzubilden.

Formal: Ein endlicher Automat M = (Q, Σ, δ, q0, F). Ein Zustandspfad q0, q1, ..., qn ist eine Sequenz von Zuständen aus Q, für die für jedes i ≤ n-1 eine Transition qi → qi+1 existiert, die durch eine Eingabe a_i ∈ Σ (oder epsilon bei ε-NFA) ausgelöst wird. In einem DFA ist qi+1 eindeutig durch qi und das gelesene Symbol bestimmt.

Eigenschaften: Pfade können end- oder unendlich sein. Sie beschreiben eine mögliche Ausführung oder Verifikation. Erreichbare Pfade sind diejenigen, die von q0 aus tatsächlich erreicht werden können; Endpfade enden in Endzuständen F.

Anwendungen: Zustandspfadanalysen dienen der Verifikation von Systemverhalten, der Testfallgenerierung, dem Model Checking und der Fehlersuche. Sie helfen, Eigenschaften wie Sicherheits- oder Verfügbarkeitsanforderungen zu prüfen und Deadlocks oder unerwartete Zustandswechsel zu identifizieren.

Beispiel: Ein DFA mit Zuständen {A, B, C}, Startzustand A, Endzustand C, Transitionen A —a→ B und B —b→ C. Der Zustandspfad A, B, C beschreibt die Eingaben a, gefolgt von b, und führt ins akzeptierende Endstadium.

Begriffliche Anmerkungen: Der Begriff wird oft mit Trace oder Ausführungspfad übersetzt; in der Praxis kann er entweder die Sequenz von Zuständen oder von Übergängen (mit Symbolen) umfassen.