Equivalence of DFA and NFA

We naturally try to find the relationship between DFA and NDFA. Intuitively we now feel that:

i. A DFA can simulate the behavior of NDFA by increasing the number of states.
In other words. a DFA (Q, ∑, δ, q₀, F) can be viewed as an NDFA (Q, ∑, δ’, q₀, F) by defining δ’(q, a) = {δ(q, a)}.

ii. Any NDFA is a more general machine without being more powerful We now give a theorem on the equivalence of DFA and NDFA.