How to convert two intersected DFAs into a minimal DFA

Question

I have the following problem: There are two deterministic finite automatons which should be intersected and converted into a single minimal deterministic finite automaton. Is there an algorithm to do that?

I know that I can create an NFA by creating the cartesian product of the two automatons and convert the outcome into a DFA, but this is a time-killing procedure. Is there an easier way to create the intersection of two automatons?

By the way: here is the solution:

I tried my approach as I described below, but I can't imagine how to get the solution: Computing the complement of the two DFA's gives my two new DFA's with exactly two accepting states. Now I have to combine them and minimize them, but wherefrom can I get the third accepting state?

Answer 1

To the best of my knowledge, there's no "direct" algorithm that accomplishes this. You can do this by

• minimizing the two input DFAs,
• computing their Cartesian product (which produces another DFA, by the way, not an NFA), then
• minimizing the result.

It's not strictly necessary to minimize the two input DFAs, but it can help with efficiency. If you have an n-state and an m-state DFA, their Cartesian product will have O(mn) states. The DFA minimization algorithm runs in time O(k²), where k is the number of states in the DFA, so if the original DFAs have sizes n and m, computing the Cartesian product and then minimizing will take time O(m²n²), whereas minimizing, then computing the Cartesian product, then minimizing again takes time O(m² + n² + m'²n'²), where m' and n' are the sizes of the minimized DFAs.

Hope this helps!