Estimate the number of states in a DFA (intersection)

Question

I'm having trouble understanding how to estimate the number of states in the intersection of two DFA's (M1 and M2, which have n and k states). I don't want to construct an actual DFA, but to understand how many states an intersection will give. For example, the union of M1 and M2 will give |n| x |k| states (if I have understood this correctly). Is there anyone who could help me understand this problem? I have some difficulty understanding DFA's...

Answer 1

Given two DFAs D₁ and D₂ with n₁ and n₂ states, respectively, it's possible to construct a new DFA D₃ with n₁n₂ states in it whose language is the intersection of the languages of D₁ and D₂ by using the product construction: have the states of D correspond to pairs of states, one from D₁ and one from D₂, and where the accepting states correspond to pairs of accepting states from D₁ and D₂.

That said, this isn't necessarily going to be the minimum-state DFA for the intersection. It's just going to be some DFA for the intersection.