Procedure to convert NFA to DFA

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

The following procedure converts the NFA to its equivalent DFA:

Input: An NDFA

Output: An equivalent DFA

step 1: start

Step 2: Create state table from the given NDFA.

Step 3: Create a blank state table under possible input alphabets for the equivalent DFA.

Step 4: Mark the start state of the DFA by q0 (Same as the NDFA).

Step 5: Find out the combination of States {Q0, Q1,… , Qn} for each possible input alphabet.

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

Step 7: The states which contain any of the final states of the NDFA are the final states of the equivalent DFA.

step 8: stop

Leave a Reply