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 have several BNF defined as follow:

1. <S> -> 0<S> | 1 | 0  
2. <S> -> 1<S> | 1 | 0
3. <S> -> 0<S> | 1<S> | 1 | 0
4. <S> -> <S>0 | 1  | 0
5. <S> -> <S>1 | 0

This is the solution from my friend, however, I doubt the correctness of some of them

1. { 0^n: n >= 1 } V { 0^n1: n >= 0 } -> This is fine.
2. { 1^n0^k: n > 0, k = 0, 1 } -> I don't quite get this one, is the same with grammar 1?
3. { 0 } V { 1^n0^k: n > 0 and k = 0, 1 } -> I think this one is incorrect.
4. { 0^n: n > 0 } V { 10^n: n >= 0 } -> I think this is also incorrect
5. { 01^n: n >= 0 } -> This is fine.

Could anyone help me explain this?

Thanks,
Chan

share|improve this question
    
What is the question that you are trying to solve? –  Code-Guru Jun 29 at 8:24

1 Answer 1

up vote 1 down vote accepted

Questions $1$,$2$ and $4$ are very similar. If you get one of them you should get all of them. Question $5$ is even simpler.

For question $3$, it is easy to see that every non-empty string is generated by the BNF. For example, to generate 0110, use $$S \rightarrow 0S \rightarrow 01S \rightarrow 011S \rightarrow 0110.$$

As to your question on "how to write all non-empty strings in $\{\}$ notation", this depends on the conventions used in your course. The corresponding regular expression is $(0+1)^+$, but I guess you haven't learned these just yet.

share|improve this answer
    
Thank you very much. So the solution that I posted above is incorrect, isn't it? Could you point out which one is incorrect? I understood your solution, but I really want make sure that my thought of my friend's solution is also right. –  Chan Feb 17 '11 at 6:21
    
2 and 3 are wrong. 2 is almost correct (it cannot generate $0$). 3 is very wrong. –  Yuval Filmus Feb 17 '11 at 6:24
1  
Thanks a lot for your confirmation. I just can't believe that a ph.D researcher could not solve the above questions correctly. Totally shock! –  Chan Feb 17 '11 at 6:34

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.