Equivalence of DFA, NFA, and ε-NFA

Equivalence of DFA and NFA

Proof

(=>): A DFA is always an NFA, by definition.

(<=): Use the power set of the states in the original NFA as the states for the new DFA.

Then, specify the transition rules so that for an input i, a state s' in the original NFA is included in the new DFA state,

if and only if the previous DFA state includes a state s that is mapped to s' upon the input i by the transition rule of the original NFA.

This increases the number of the states exponentially, but is enough for an existence proof by construction. 

Equivalence of DFA and ε-NFA

Proof

(=>): A DFA is always an ε-NFA, by definition.

(<=): Similar to the case of NFA, but this time we should also include the states reachable by ε-transition, that is, any sequence of transitions that consumes the input i once, and consumes ε for the rest.

Hence, DFA, NFA, and ε-NFA are all equivalent in their expressive power.