109
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.
Next TopicDFA