Transition system

In <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, a transition system is a concept used in the study of <a href="/facts/Computation/qLsELosq">computation</a>. It is used to describe the potential behavior of <a href="/facts/Discrete_system/DMbNSaaa">discrete systems</a>. It consists of <a href="/facts/State_(computer_science)/4Yu8xXHS">states</a> and transitions between states, which may be labeled with labels chosen from a set; the same label may appear on more than one transition. If the label set is a <a href="/facts/Singleton_(mathematics)/LtNVfujT">singleton</a>, the system is essentially unlabeled, and a simpler definition that omits the labels is possible.
Transition systems coincide mathematically with <a href="/facts/Abstract_rewriting_system/FNIYHu2k">abstract rewriting systems</a> (as explained further in this article) and <a href="/facts/Directed_graph/YBdfQ0um">directed graphs</a>. They differ from <a href="/facts/Finite-state_automata/GMusWd0a">finite-state automata</a> in several ways:

<ul><li>The set of states is not necessarily finite, or even countable.</li>
<li>The set of transitions is not necessarily finite, or even countable.</li>
<li>No "start" state or "final" states are given.</li></ul>
Transition systems can be represented as directed graphs.

Transition system open-in-new

Transition system