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.
There are at least two basic types of state transition systems: labelled (or LTS for labelled transition system) or unlabelled.
Table of contents |
2 Relation between labelled and unlabelled transition systems. 3 See also |
Formally, an unlabelled state transition system is a tuple (S, &rarr) where S is a set (of states) and &rarr &sube S × S is a binary relation over S (of transitions.) If p,q &isin S, (p,q) &isin &rarr is usually written as p &rarr q. This represents the fact that there is a transition from state p to state q.
A labelled transition system is a tuple (S, &Lambda, &rarr) where S is a set (of states), &Lambda is a set (of labels) and &rarr &sube S × &Lambda × S is a ternary relation (of labelled transitions.) If p, q &isin S and &alpha &isin &Lambda, (p,&alpha,q) &isin &rarr is written
Formal definition