A deterministic finite automaton has one transition from one state to another. On the other hand, a nondeterministic finite automaton has one or more than one transition from one state to another or itself.
Every deterministic finite automaton is a nondeterministic finite automaton but the reverse is not true.
Assume an NFA for a language L with
It is converted to a DFA
Note: While converting an NFA with n states to a DFA, 2^{n}^{ }possible set of states can be reachable but not necessarily reached in the DFA.
The following general set of rules are followed to convert a nondeterministic finite automaton to a deterministic finite automaton:
At the beginning
Add
For every state in
The final state
Let's consider the following nondeterministic finite automaton that accepts the language
For this NFA,
state | a | b |
q_{0} | q_{1}, q_{2} | q_{4} |
q_{1} | q_{0} | - |
q_{2} | q_{3} | - |
q_{3} | - | q_{0} |
q_{4} | - | - |
Checks if
Add the first state to
For each state in
state | a | b |
q_{0} | q_{1}, q_{2} | q_{4} |
state | a | b |
q_{0} | q_{1}, q_{2} | q_{4} |
q_{1}, q_{2} | q_{0}, q_{3} | - |
q_{4} | - | - |
state | a | b |
q_{0} | q_{1}, q_{2} | q_{4} |
q_{1}, q_{2} | q_{0}, q_{3} | - |
q_{4} | - | - |
q_{0}, q_{3} | q_{1}, q_{2} | q_{0}, q_{4} |
state | a | b |
q_{0} | q_{1}, q_{2} | q_{4} |
q_{1}, q_{2} | q_{0}, q_{3} | - |
q_{4} | - | - |
q_{0}, q_{3} | q_{1}, q_{2} | q_{4} |
q_{1} | q_{0} | - |
q_{0}, q_{4} | q_{1}, q_{2} | q_{4} |
Combine all the states in the last obtained transition table and show appropriate transitions. In case a transition is not defined for input, make a transition to the trap state.
For this DFA,