1
$\begingroup$

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!

  • 0
    @Mark: It just bothers me a bit when questions appear to be 'unanswered' but have in fact already been answered in the comments. I think sometimes people write answers they think are too easy as comments because they don't want to get reputation from them. But in that case, making the answer CW is another option.2012-05-07

1 Answers 1

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

  • 0
    It occurs to me now that you don't even need to normalize the regex, if you are a little bit careful.2012-05-07