NDFA to DFA Conversion - Automata Theory

How to convert NDFA to DFA?

Problem Statement

Let non) be an NDFA which represents the language L(X). Here we have to design an equivalent non 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.

ndfa

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 −

dfa_state_diagram

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Automata Theory Topics