# 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 $1$s and $0$s has at least two $0$s and three $1$s can be created by combining the DFA ($M1$) that checks to see if a string has at least two $0$s and the DFA ($M2$) that checks to see if the string has at least three $1$s.

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:

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$.

Filed Under: Crash Courses, Computer Science

Sources Used

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