Properties of Transition System in Automata

Transition System:

A transition graph or a transition system is a finite directed labelled graph in which each vertex (or node) represents a state and the directed edges indicate the transition of a state and the edges are labelled with input-output.

A typical transition system is shown in below fig. In the figure, the initial state is represented by a circle with an arrow pointing towards it, the final state by two concentric circles, and the other states are represented by just a circle.

We now give the (analytical) definition of a transition system.

A transition system is a 5-tuple (Q, ∑, δ, Q0, F), where –

    i. Q, ∑ and F are the finite non-empty set of states, the input alphabet, and the set of final states, respectively, as in the case of finite automata.

    ii. Q0 ⊆ Q. and Q0 is non-empty: and

    iii. δ is a finite subset of Q x ∑* x Q.