Nachfolgezustände

Der Begriff Nachfolgezustände bezeichnet Zustände, die unmittelbar nach einem gegebenen Zustand durch eine Transition erreichbar sind, wie sie in Übergangssystemen, der Automatenlehre und dynamischen Systemen vorkommen.

Formal betrachtet besteht ein Übergangssystem T aus einer Zustandsmenge S und einer gerichteten Beziehungsrelation R ⊆ S × S (und ggf. Eingaben E). Für einen Zustand s ∈ S gilt die Menge der Nachfolgezustände NF(s) = { t ∈ S | (s, t) ∈ R }. In deterministischen endlichen Automaten (DFA) existiert für jeden Zustand s und jedes Eingabezeichen a genau ein Nachfolgezustand δ(s, a). In nichtdeterministischen Automaten (NFA) kann δ(s, a) eine Menge von Zuständen sein. In stochastischen Modellen wie Markov-Ketten werden Nachfolgezustände zusätzlich mit Übergangswahrscheinlichkeiten betrachtet, etwa P(s'|s).

Beispiel: Ein DFA mit den Zuständen A, B und C hat die Transitionen A -a-> B und A -b-> C. Von A aus hängt der Nachfolgezustand vom Eingabezeichen ab: δ(A, a) = B und δ(A, b) = C.

Anwendungen der Nachfolgezustände finden sich in der Softwareverifikation, beim Model Checking, in der Graphentheorie und in der Planung. Sie spielen eine zentrale Rolle bei Verfahren zur Erreichbarkeitsanalyse, der Minimierung von Zustandsautomaten und der Bestimmung möglicher Pfade durch ein System.

Siehe auch: Zustand, Zustandsautomat, Übergang, Erreichbarkeit.