Zustandsraum (Informatik)

In der theoretischen Informatik ist ein Zustandsraum eine Beschreibung von diskreten Zuständen, um sie als einfaches Modell von Maschinen zu verwenden (z. B. Endliche Automaten) (nicht zu verwechseln mit dem Zustandsraum (Neuronales Netz) in der Neuroinformatik). Er stellt die Summe aller Zustände eines betrachteten Systems dar.<ref>Alexander Malkis: Logische und methodische Grundlagen der Programm- und Systementwicklung. Datenstrukturen, funktionale, sequenzielle und objektorientierte Programmierung. Springer Fachmedien, Wiesbaden 2019, ISBN 978-3-658-26301-0, S. 264. </ref>

Formal wird er definiert als ein Tupel <math>[N, A, S, G]</math> wobei:

<math>N</math> eine Menge von Zuständen,
<math>A</math> eine Menge von Übergangskanten zwischen den Zuständen,
<math>S</math> eine nicht-leere Untermenge von <math>N</math>, welche die Startknoten enthält und
<math>G</math> eine nicht-leere Untermenge von <math>N</math>, welche die Zielknoten enthält.

Die Darstellung kann über Zustandsübergangsdiagramme erfolgen. Hilfreich beim Verständnis von Zustandsräumen ist die Graphentheorie, die Mengen aus Knoten und Kanten betrachtet.

Ein Zustandsraum kann mit folgenden Eigenschaften beschrieben werden:

Die Komplexität entspricht der Größe der Menge <math>N</math>. Oft ist der Zustandsraum nicht beschränkt (z. B. bei Turingmaschinen). Abhängig von der Definition des Zustandsraumes ist diese Größe nicht immer leicht zu bestimmen.
Die Struktur des Zustandraums, lässt sich mittels gerichteter Graph modellieren und so analysieren, ob diese topologisch sortierbar ist (Baum) oder zyklisch.

Siehe auch

Endlicher Automat

Einzelnachweise