# Need help explain BNF

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

-
What is the question that you are trying to solve? –  Code-Guru Jun 29 '14 at 8:24

## 1 Answer

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.

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