# 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

Present State | Next state for Input 0 | Next State of Input 1 |
---|---|---|

→q0 | q1 | q2 |

q1 | q0 | q2 |

*q2 | q2 | q2 |

**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:

Present State | Next state for Input 0 | Next State of Input 1 |
---|---|---|

→q0 | q0 | q1 |

q1 | q1, q2 | q2 |

q2 | q1 | q3 |

*q3 | q2 | q2 |

**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.

**Theory of Automata****Finite Automata****Transition Diagram****Transition Table****DFA (Deterministic finite automata)****Examples of DFA****NFA (Non-Deterministic finite automata)****Examples of NFA****Eliminating ε Transitions****Conversion from NFA to DFA****Conversion from NFA with ε to DFA****Minimization of DFA****Regular Expression****Examples of Regular Expression****Moore Machine****Mealy Machine****Context Free Grammar****Simplification of CFG****Chomsky’s Normal Form (CNF)****Greibach Normal Form (GNF)****Pushdown Automata(PDA)****Non-deterministic Pushdown Automata****Turing Machine****Examples of TM**

Post Views: 194