Conversion of NFA to DFA

 Conversion of NDFA to DFA:

Let X = (Qx, ∑, δx, q0, Fx) be an NDFA which accepts the language L(X). We have to design an equivalent DFA Y = (Qy, ∑, δy, q0, Fy) such that L(Y) = L(X). 

Algorithm

Input − A NDFA

Output − An equivalent DFA

Steps to convert NDFA to DFA:

Step 1 − Create state table from the given NDFA.

Step 2 − Create a blank state table under possible input alphabets for the equivalent DFA.

Step 3 − Mark the start state of the DFA by q0 (Same as the NDFA).

Step 4 − Find out the combination of States {Q0, Q1,... , Qn} for each possible input alphabet.

Step 5 − Each time we generate a new DFA state under the input alphabet columns, we have to apply step 4 again, otherwise go to step 6.

Step 6 − The states which contain any of the final states of the NDFA are the final states of the equivalent DFA.

Example 1:

1. Convert the given NDFA to DFA

Using the above algorithm, we find its equivalent DFA. The state table of the DFA is shown in below

The state diagram of the DFA is as follows:

 Example 3 Conversion from NDFA to DFA

NDFA/NFA                                                                    Minimization of DFA