# NDFA to DFA Conversion - Automata Theory

## Problem Statement

Let ) be an NDFA which represents the language L(X). Here we have to design an equivalent which can be L(Y) = L(X). Below mentioned steps are used to convert the NDFA to its equivalent DFA −

## Algorithm

Input − An NDFA

Output − An equivalent DFA

Step 1 – let’s create state table from the given NDFA.

Step 2 –Now create a blank state table with possible input alphabets for the equivalent DFA.

Step 3 – Now highlight 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 – When we create a new DFA state with the input alphabet columns, then 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

Let’s see the NDFA shown in the figure below. q δ(q,0) δ(q,1)
a {a,b,c,d,e} {d,e}
b {c} {e}
c {b}
d {e}
e

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

q δ(q,0) δ(q,1)
[a] [a,b,c,d,e] [d,e]
[a,b,c,d,e] [a,b,c,d,e] [b,d,e]
[d,e] [e]
[b,d,e] [c,e] [e]
[e]
[c, e] [b]
[b] [c] [e]
[c] [b]

The state diagram of the DFA is as follows − ## Automata Theory Related Practice Tests

Automata Theory Topics