Combining DFAs

Another interesting property of DFAs is that they can be combined. This allows more complex problems to be solved by creating smaller and easier DFAs and then combining them together to solve the entire problem. For example a DFA that checks to see if a string of 1s and 0s has at least two 0s and three 1s can be created by combining the DFA (M1) that checks to see if a string has at least two 0s and the DFA (M2) that checks to see if the string has at least three 1s.

The set of states of this new DFA (M3) are the cross product of the internal states of M1 and M2. A state is the initial state of M3 if both of its components were initial states of M1 and M2, and a state is the final state of M3 if both of its components were final states of M1 and M2.

The transition function of M3 is defined as follows \delta_3 (q1,q2), x) = (\delta_1 (q1, x), \delta_2(q2, x)). As a result this gives us the DFA transition table and diagram:

finite3

Notice A \times A is the initial state of M3 because A is the initial states of both M1 and M2. C \times D is the final state of M3 because C is the final state of M1 and D is the final state of M2.

Previous | Next

  1. What is a Finite State Machine?
  2. Deterministic Finite Automata
  3. Examples of DFA part 1
  4. Examples of DFA part 2
  5. Examples of DFA part 3
  6. Combining DFAs
  7. Limits and Languages of DFAs
  8. Applications

Filed Under: Crash Courses, Computer Science

Sources Used

  • Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman

Sharing the Wonder