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

Question

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!

Answer 1

1. 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 … . (You fill in the dots.)

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….