Problem Statement

Let X = (Q_x, ∑, δ_x, q₀, F_x) be an NFA which accepts the language L(X). We have to design an equivalent DFA Y = (Q_y, ∑, δ_y, q₀, F_y) such that L(Y) = L(X). The following procedure converts the NDFA to its equivalent DFA −

Algorithm

Input − An NFA

Output − An equivalent DFA

Step 1 − Create state table from the given NFA.

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 A state (Same as the NFA).

Step 4 − Find out the combination of States {Q₀, Q₁,... , Q_n} for each possible input alphabet. (Our inputs are 0 and 1)

Step 5 − Each time we generate a new DFA state (e.g. AC) 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 NFA are the final states of the equivalent DFA.

Conversion From NFA to DFA