Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.