Conversion from NFA to DFA
In this section, we will discuss the method of converting NFA to its equivalent DFA. In NFA, when a specific input is given to the current state, the machine goes to multiple states. It can have zero, one or more than one move on a given input symbol. On the other hand, in DFA, when a specific input is given to the current state, the machine goes to only one state. DFA has only one move on a given input symbol.
Let, M = (Q, ∑, δ, q0, F) is an NFA which accepts the language L(M). There should be equivalent DFA denoted by M’ = (Q’, ∑’, q0′, δ’, F’) such that L(M) = L(M’).
Steps for converting NFA to DFA:
Step 1: Initially Q’ = ϕ
Step 2: Add q0 of NFA to Q’. Then find the transitions from this start state.
Step 3: In Q’, find the possible set of states for each input symbol. If this set of states is not in Q’, then add it to Q’.
Step 4: In DFA, the final state will be all the states which contain F(final states of NFA)
Example 1:
Convert the given NFA to DFA.
Solution: For the given transition diagram we will first construct the transition table.
State | 0 | 1 |
---|---|---|
→q0 | q0 | q1 |
q1 | {q1, q2} | q1 |
*q2 | q2 | {q1, q2} |
Now we will obtain δ’ transition for state q0.
- δ'([q0], 0) = [q0]
- δ'([q0], 1) = [q1]
The δ’ transition for state q1 is obtained as:
- δ'([q1], 0) = [q1, q2] (new state generated)
- δ'([q1], 1) = [q1]
The δ’ transition for state q2 is obtained as:
- δ'([q2], 0) = [q2]
- δ'([q2], 1) = [q1, q2]
Now we will obtain δ’ transition on [q1, q2].
- δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0)
- = {q1, q2} ∪ {q2}
- = [q1, q2]
- δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1)
- = {q1} ∪ {q1, q2}
- = {q1, q2}
- = [q1, q2]
The state [q1, q2] is the final state as well because it contains a final state q2. The transition table for the constructed DFA will be:
State | 0 | 1 |
---|---|---|
→[q0] | [q0] | [q1] |
[q1] | [q1, q2] | [q1] |
*[q2] | [q2] | [q1, q2] |
*[q1, q2] | [q1, q2] | [q1, q2] |
The Transition diagram will be:
The state q2 can be eliminated because q2 is an unreachable state.
Example 2:
Convert the given NFA to DFA.
State | 0 | 1 |
---|---|---|
→q0 | {q0, q1} | {q1} |
*q1 | ϕ | {q0, q1} |
Now we will obtain δ’ transition for state q0.
- δ'([q0], 0) = {q0, q1}
- = [q0, q1] (new state generated)
- δ'([q0], 1) = {q1} = [q1]
The δ’ transition for state q1 is obtained as:
- δ'([q1], 0) = ϕ
- δ'([q1], 1) = [q0, q1]
Now we will obtain δ’ transition on [q0, q1].
- δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0)
- = {q0, q1} ∪ ϕ
- = {q0, q1}
- = [q0, q1]
Similarly,
- δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1)
- = {q1} ∪ {q0, q1}
- = {q0, q1}
- = [q0, q1]
As in the given NFA, q1 is a final state, then in DFA wherever, q1 exists that state becomes a final state. Hence in the DFA, final states are [q1] and [q0, q1]. Therefore set of final states F = {[q1], [q0, q1]}.
The transition table for the constructed DFA will be:
State | 0 | 1 |
---|---|---|
→[q0] | [q0, q1] | [q1] |
*[q1] | ϕ | [q0, q1] |
*[q0, q1] | [q0, q1] | [q0, q1] |
The Transition diagram will be:
Even we can change the name of the states of DFA.
Suppose
- A = [q0]
- B = [q1]
- C = [q0, q1]
With these new names the DFA will be as follows:
- 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