Transition In Automata

Moving From one state to another or in the same state with the help of an arrow, by using an input alphabet, is called transition in Automata. Transition happens with the help of the transition function.

Notation of Transition 

The notation of a transition typically involves representing the states, input symbols, and corresponding transitions. Following is the notation of the transition from a state to a similar or another state.

Notation of Transition in Automata

Transition Table

A transition table represents the transition function in tabular form. The transition function (∂) is a function that takes Q * ∑ as its input and maps it into Q. In this context, ‘Q’ represents a set of states, and ‘∑’ represents the input alphabet. To represent this transition function, we can use a table called the transition table. This table takes in two values – a state and a symbol – and returns the next state.

A transition table provides the following information

  • The first column represents all possible states.
  • Rest all columns reserve for each corresponding input symbol. It is also called the next state after the transition for specific corresponding input symbols.
  • The final state is represented by a star or double circle.
  • The start state is always denoted by a small arrow.

Example 01: Transition in Automata

Consider the following is the DFA that accepts all strings starting with b.

Transition and Its Table Example 01

In the above finite automata transition graph, the machine is initially in the initial state (q0), then on receiving input “b”, the machine changes its state to q2.

  • At state q0, on receiving input “a”, the machine changes its state to q1, which is the dead state.
  • At state q2, on receiving input “a” and “b”, the machine stays in the same state (q2), which is the final state.

The following is the transition table of the above DFA 

Present State Next state for Input “a” Next State of Input “b”
→q0 q1 q2
q1 Nill Nill
*q2 q2 q2

The transition table has three rows displaying the present state and the next state depending on the input provided. 

  • In the first row, the current state is q0. On input “a”, the next state will be q1, and on input “b”, the next state will be q2.
  • In the second row, the current state is q1. No transition was made over inputs a or b.
  • In the third row, the current state is q2. On input “a”, the next state will be q2, and on input “b”, the next state will also be q2.

Example 02: Transition in Automata

Consider the following DFA

Transition and Its Table Example 02

The following is the transition table of the above DFA 

Present State Next state for Input “a” Next State of Input “b”
→q0 q1 q2
q1 q0 q2
*q2 q2 q2

The above transition table has three rows displaying the present state and the next state depending on the input provided. 

  • In the first row, the current state is q0. On input “a”, the next state will be q1, and on input “b”, the next state will be q2.
  • In the second row, the current state is q1. On input “a”, the next state will be q0, and on input “b”, the next state will be q2.
  • In the third row, the current state is q2. On input “a”, the next state will be q2, and on input “b”, the next state will be q2.