When a certain input is given to the current state in NFA, the machine changes states. On a particular input symbol, it can have zero, one, or several moves. When a specific input is given to the current state in DFA, however, the machine only moves to one state. On each input symbol, DFA can only make one move.
What is NFA and DFA?
NFA(Nondeterministic Finite Automata) means where the transition from a state can be multiple next states for each input symbol. NFA also has five tuples as DFA, but different transition functions, as shown below:
Q, ∑, δ, q0, F
Where,
Q represents the finite set of states.
∑ represents a finite set of symbols known as alphabets.
δ represents the transition function where δ: Q x ∑ →2Q.
Q0 is an initial state.
F is a final state.
DFA(Deterministic Finite Automata) is a finite-state machine that accepts or rejects a given string of symbols by running through a state sequence that is uniquely determined by the string in the theory of computation. It is represented as 5 tuples (Q, ∑, δ, q0, F) where:
Q represents the finite states.
∑ represents the is a finite set of symbols, also called the alphabet.
δ represents the transition function where δ: Q × ∑ → Q.
q0 represents the initial state from where any input is processed.
F represents the set of the final state of Q.
Steps for Converting NFA to DFA
Step 1 :
Suppose 'Q' to be a new set of states of the Deterministic Finite Automata. In the initial stage, 'Q' is null.
Suppose 'T' to be a new transition table of the Deterministic Finite Automata.
Step 2 :
Add the start state of the NFA to 'Q.'
To the transition table 'T,' add transitions from the initial state this is very crucial in the Conversion of NFA to DFA.
If a start state makes transitions to several states for a certain input alphabet, in that case, those multiple states should be treated as a single state in the case of Deterministic Finite Automata.
If the transition of start state over any input alphabet is null in the Non-Deterministic Finite Automata, in that case, perform the transition of start state over that input alphabet to a dead state in the Deterministic Finite Automata.
Step 3:
Now check If there is any new state in the transition table 'T' then, Add the new state in 'Q' and correspondingly add the transition of that state in the transition table 'T.'
Step 4:
Keep repeating Step-03 until no new state is present in the transition table 'T.'
Finally, the transition table 'T' so obtained is the complete transition table of the required DFA.
Examples of Conversion of NFA to DFA
Example 1
Given below is the NFA convert it into its equivalent DFA use the steps explained above for Conversion of NFA to DFA.
Step 1: Construct the corresponding NFA transition table. Ultimately this table is going to help in converting the DFA from its corresponding NFA.
a
b
A(Initial state)
A
{A, B}
B
-
C
C(Final state)
-
-
Explaining the table:
a
b
A(Initial state)
A (In NFA diagram you can see A goes to A with a self-loop)
{A, B}(In NFA diagram you can see A goes to both A and B)
B
-
C(In NFA diagram you can see B goes to C)
C(Final state)
-
-
Step 2: Use this table and start moving on all the states and try to make a DFA table. If a state goes to multiple states, then consider those multiple states set as a single isolated state. So here, in a first attempt, [A, B] is considered as a new state.
Step 3: Now, give that state a new entry in the DFA transition table. So in this example, give [A, B] a new entry and start filling the transitions for [A, B] in order to fill the transition for this new state first, check the transition of A and then for B, and finally make the subset of the same.
Step 4: Keep repeating steps two and step three until the entire table is formed.
Step 5: Now check for the final state in NFA that is C, so wherever C is present in the DFA transition table, make that as a final state so in the DFA table [A, B, C] is considered as the final state. Also, we have to stop at the third row because [A] and [A, B, C] are already present.
Note: {} this type of bracket is used to store the multiple states, and [] this type of bracket shows a single state.
a
b
A(Initial state)
A
[A, B](consider this as a single state)
[A, B](new entry to this state)
[A] A goes to A via a self-loop whereas B has no transition to a
[A, B, C]([A, B] goes to [A, B, C] on b and now consider [A, B, C] as a new state)
[A, B, C](new state)
[A]
[A, B, C]
Below is the state diagram for this transition table
Example 2
Below is another NFA that we will convert into its equivalent DFA using the steps for converting NFA to DFA we learned above.
Step 1: Construct the corresponding NFA transition table. Ultimately this table is going to help in converting the DFA from its corresponding NFA.
a
b
q0(Initial state)
{q1,q2}
q2
q1(Final state)
{q1,q2}
q2
q2
-
-
Explaining the table:
0
1
q0(Initial state)
{q1,q2} (In NFA diagram you can see q0 goes to both q1 and q2)
q2(In NFA diagram you can see q0 goes q2)
q1(Final state)
{q1,q2} (In NFA diagram you can see q1 goes to both q1 and q2)
q2(In NFA diagram you can see q1 goes q2)
q2
-
-
Step 2: Use this table and start moving on all the states and try to make a DFA table. If a state goes to multiple states, then consider those multiple states set as a single isolated state. So here, in a first attempt, [q1, q2] is considered as a new state.
Step 3: Now, give that state a new entry in the DFA transition table. So in this example, give [q1, q2] a new entry and start filling the transitions for [q1, q2] in order to fill the transition for this new state first, check the transition of q1 and then for q2, and finally make the subset of the same.
Step 4: Keep repeating steps two and step three until the entire table is formed.
Step 5: Now check for the final state in NFA that is q1, so wherever q1 is present in the DFA transition table, make that as a final state so in the DFA table [q1,q2] is considered as the final state. Also, we have to stop at the third row.
Note: {} this type of bracket is used to store the multiple states, and [] this type of bracket shows a single state.
a
b
q0(Initial state)
[q1,q2](consider this as a single state)
q2
[q1, q2](new entry to this state)
[q1,q2] (q1 goes to q1 and q2 whereas q2 has no transition)
q2(q1 goes to q2 on 1 and q2 has no transition)
q2
-
-
Below is the state diagram for this transition table
Frequently Asked Questions
Why NFA is converted to DFA?
An NFA can have zero, one, or many moves on input, whereas a DFA will only have one move. Conversion of an NFA to an equivalent DFA helps to achieve determinism. This conversion leads to state minimization, reducing unnecessary memory usage.
How to change NFA to DFA?
NFA(Non-Deterministic Finite Automata) is the kind of automata that has only the required states that are needed to make the required output condition true. We change it into DFA(Deterministic Finite Automata) by adding all the conditional changes for all the states that are described.
Is DFA equal to NFA?
An NFA is not entirely equal to a DFA. In DFA, all the conditional states of the NFA are written but the vice versa is not true. This means that in an NFA, all the conditional state variables for all the states are not written. But they are equal in understanding the language.
What is NFA vs DFA?
NFA(Non-deterministic Finite Automata) has only the required states that are needed to make the required output condition true. While DFA(Deterministic Finite Automata) by adding all the conditional changes for all the states that are described.
Conclusion
In this blog, we discussed a lot about the Conversion from NFA to DFA with illustrated examples. We did a thorough understanding of the conversion of NFA to DFA and are now ready to deal with any type of question.
117+ registered 