# How can I prove a DFA accepts a certain mininum number of states?

We know that if there are two languages, L1 and L2, if L1 and L2 are regular, the intersection of those two is also regular. Suppose we have two machines, M1 and M2, and using them, a new machine M3 is built. If M1 had k>0 states and M2 had l>0 states, the new machine has to have kl states at minimum.

How would I go about trying to prove this? I've been stuck on this for quite some time. I know that we would have to construct the languages L1 and L2 so that M1 and M2 accept them, respectively, which in turn allows the smallest machine accepts L1 intersects L2 has k x l states.

Any help would be greatly appreciated.

-
I assume $M_i$ is supposed to recognize $L_i$ and that $L_3 = L_1 \cap L_2$. If so, then the statement is not true. Consider the case that $L_1 = L_2$ and $M_1 = M_2$. Then we can take $M_3 = M_1$. – Qiaochu Yuan Feb 22 '13 at 2:57
There is a general technique for finding a lower bound on the number of states a FSM recognizing a given language $L$, but it requires a little algebraic number theory. – Qiaochu Yuan Feb 22 '13 at 2:59

I'm wondering whether maybe you got the question the wrong way round, and what you're actually supposed to show is that you need at most $kl$ states. Because that is true, whereas what you have asked about is not, as Qiaochu already mentioned in the comments (if $L_1$ and $L_2$ are the same language, then $L_1\cap L_2 = L_i$ for $i=1,2$ and so you can use either $M_1$ or $M_2$ to recognise the intersection, so you only need $\min\{k,l\}$ states in that case).
Let me know if you'd like an explanation of why you need at most $kl$ states, but you might find you can do the question once you realise what it actually says.