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