### Equivalence of DFA

• Every DFA is a NFA, but not vice versa.

• But there is an equivalent DFA for every NFA

• For every NFA, there exists a DFA that simulates the characteristics of NFA

Both NFA and DFA has five tuples ; < Q, Σ, q0, qf, 𝜹 >

where,

Q denotes the set of states

Σ, denotes input alphabet

q0 indicates initial state

qf indicates final state

the transition function of NFA is defined as 𝜹 : Q x Σ → 2Q

the transition function of DFA is defined as 𝜹 : Q x Σ → Q

By replacing Q with 2Q  the equivalent NFA of DFA can be obtained.

Example 1:

Draw the Equivalent DFA for the transition table given

 a b q0 q0, q1 q2 q1 q0 q1 q2* ø q0, q1

Solution:

 a b [q0] [q0, q1] [q2] q2 ø [q0, q1] [q0, q1] [q0, q1] [q1, q2] [q1, q2]* [q0] [q0, q1]

Example 2:

 State 0 1 q0 q0, q1 q0 q1 q2 q1 q2 q3 q3 q3* ø q2

Solution:

 State 0 1 [q0] [q0, q1] [q0] [q0, q1] [q0, q1, q2] [q0, q1] [q0, q1, q2] [q0, q1, q2,q3] [q0,q1,q3] [q0,q1,q3]* [q0, q1, q2] [q0, q1,q2] [q0, q1, q2,q3]* [q0, q1, q2,q3] [q0, q1, q2,q3]