# Algorithm to tell whether a regular language contains at least n strings

I'm taking a course on formal languages and was given this exercise:

Give an algorithm to tell whether a regular language $L$ contains at least $100$ strings.

Can someone give me a hint? Thanks!

-
Look at problem 4 in <a href="www.cas.mcmaster.ca/~soltys/se4i03-f02/test1.ps">www.cas.mcmaster.ca/~solt‌​ys/se4i03-f02/test1.ps</a> –  Chris K. Caldwell May 7 '12 at 0:40
How is the regular language given? –  Gerry Myerson May 7 '12 at 0:41
Normalize the FSM to eliminate unreachable states. (If you were not given a FSM, construct one.) The resulting FSM either contains a loop, or not. If it does, then… . If not, then … . Or alternatively, normalize your regular expression to eliminate trivial terms like $\varnothing\cdot X$. The resulting expression either contains a $\ast$ or does not…. –  MJD May 7 '12 at 1:41
@GerryMyerson: I was going to ask that, but it doesn't really matter, because if it's not in the form we want to use, there'll be an algorithm to convert it into our favourite form. –  Tara B May 7 '12 at 13:30
@MarkDominus: You might as well put your first comment as an answer. As I understand it, hints like that are the kind of thing expected as answers to homework questions, right? –  Tara B May 7 '12 at 13:31

2. Or alternatively, if you are given a regular expression, normalize it to eliminate trivial terms like $\varnothing\cdot X$ and $\epsilon^\star$. The resulting expression either contains a ∗ or does not….