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
    Look at problem 4 in www.cas.mcmaster.ca/~soltys/se4i03-f02/test1.ps2012-05-07
  • 1
    How is the regular language given?2012-05-07
  • 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 … . Or alternatively, normalize your regular expression to eliminate trivial terms like $\varnothing\cdot X$. The resulting expression either contains a $\ast$ or does not….2012-05-07
  • 0
    @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.2012-05-07
  • 1
    @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?2012-05-07
  • 0
    @Tara Thanks. It often seems to me that people here give easy, offhand, or partial answers in comments, and I'm not sure yet what the social conventions call for.2012-05-07
  • 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