State transition system
From Free net encyclopedia
In theoretical computer science, a state transition system is an abstract machine used in the study of computation. The machine consists of a set of states and transitions between states.
State transition systems differ from finite state automata in several ways:
- In a state transition system the set of states is not necessarily finite, or even countable.
- In a state transition system the set of transitions is not necessarily finite, or even countable.
- In a state transition system, transitions do not form a function, but a relation between the states, and therefore, there may be zero or more than one transition out of a given state, with the same input.
State transition systems with a finite number of states and transitions can be represented as directed graphs.
There are at least two basic types of state transition systems: labelled (or LTS for labelled transition system) or unlabelled.
Formal definition
Formally, an unlabelled state transition system is a tuple (S, →) where S is a set (of states) and → ⊆ S × S is a binary relation over S (of transitions.) If p,q ∈ S, (p,q) ∈ → is usually written as p → q. This represents the fact that there is a transition from state p to state q.
A labelled transition system is a tuple (S, Λ, →) where S is a set (of states), Λ is a set (of labels) and → ⊆ S × Λ × S is a ternary relation (of labelled transitions.) If p, q ∈ S and α ∈ Λ, (p,α,q) ∈ → is written
& \alpha & \\
p & \rightarrow & q \end{matrix} </math>
Relation between labelled and unlabelled transition systems.
There are many relations between these concepts. Some are simple, such as observing that a labelled transition system where the set of labels consists of only one element is equivalent to an unlabelled transition system. However not all these relations are equally trivial.