Transition Table

The transition table is basically a tabular representation of the transition function. It takes two arguments (a state and a symbol) and returns a state (the “next state”).

A transition table is represented by the following things:

• Columns correspond to input symbols.
• Rows correspond to states.
• Entries correspond to the next state.
• The start state is denoted by an arrow with no source.
• The accept state is denoted by a star.

Example 1:

Solution:

Transition table of given DFA is as follows

Explanation:

• In the above table, the first column indicates all the current states. Under column 0 and 1, the next states are shown.
• The first row of the transition table can be read as, when the current state is q0, on input 0 the next state will be q1 and on input 1 the next state will be q2.
• In the second row, when the current state is q1, on input 0, the next state will be q0, and on 1 input the next state will be q2.
• In the third row, when the current state is q2 on input 0, the next state will be q2, and on 1 input the next state will be q2.
• The arrow marked to q0 indicates that it is a start state and circle marked to q2 indicates that it is a final state.

Example 2:

Solution:

Transition table of given NFA is as follows:

Explanation:

• The first row of the transition table can be read as, when the current state is q0, on input 0 the next state will be q0 and on input 1 the next state will be q1.
• In the second row, when the current state is q1, on input 0 the next state will be either q1 or q2, and on 1 input the next state will be q2.
• In the third row, when the current state is q2 on input 0, the next state will be q1, and on 1 input the next state will be q3.
• In the fourth row, when the current state is q3 on input 0, the next state will be q2, and on 1 input the next state will be q2.