NDFA to DFA Conversion

Posted By on April 29, 2016


Download PDF
Non-deterministic Finite Automaton
DFA Minimization

Problem Statement

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). The following procedure converts the NDFA to its equivalent DFA −

Algorithm

Input: An NDFA
Output: equivalent 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

The NDFA table is as follows −

q δ(q,0) δ(q,1)
a {a,b,c,d,e} {d,e}
b {c} {e}
c {b}
d {e}
e

Let us consider the NDFA shown in the figure below.

NDFA

Using 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
d e
{c,e} B
b c E
c B

The state diagram of the DFA is as follows −

State Diagram of DFA

Non-deterministic Finite Automaton
DFA Minimization

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com