Take the 2-minute tour ×
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.

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!

share|improve this question
    
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
1  
How is the regular language given? –  Gerry Myerson May 7 '12 at 0:41
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…. –  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
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? –  Tara B May 7 '12 at 13:31

1 Answer 1

up vote 2 down vote accepted
  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….

share|improve this answer
    
It occurs to me now that you don't even need to normalize the regex, if you are a little bit careful. –  MJD May 7 '12 at 17:30

Your Answer

 
discard

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.