A tutorial on finite automata


Equivalence of DFA and NDFA

Theorem

If L is a language accepted by a nondeterministic finite automaton, then a deterministic finite automaton exists accepting L.

The proof of this theorem is a constructive one. Given a NDFA we construct an equivalent DFA where the set of final states is the set of subsets that contains at least one final state of the starting NDFA and the transition function is defined by applying the delta of the NDFA to each state in a given subset and taking the union of resulting states.

Examples

  1. Example 1: Deterministic Two Consecutive 1's or 0's
  2. Example 2: Deterministic Starting and Ending with an a

Back to Index