Search code examples
bnf

A set of positive integers that do not begin with 0, except for 0

While trying to solve the following exercises in programming language subjects, I know my answer can't create string 201, but I can't imagine how to solve this exception.

Problem: L(G) is a set of positive decimal numbers that do not start with 0, except zero. Design grammar G.

My answer:

G is:
    S -> Digit
    NonZeroDigit -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
    Digit -> 0 | NonZeroDigit | NonZeroDigit 0 | NonZeroDigit Digit

Check correctness:

Digit => 0
Digit => NonZeroDigit => 1
Digit => NonZeroDigit Digit => 2 Digit => 20

If I add Digit -> Digit Digit, it would create Digit => Digit Digit => Digit Digit Digit => 201, but this also can create Digit => Digit Digit => Digit Digit Digit => 000. What?

How do I change the grammar I define so I can meet the condition?

Solution

  • Why not just Split n=0 and n>0?

    S -> 0 | posDig digit
posDig -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
digit -> digit digit | 0 | posDig | <epsilon>

    Instead of (posDig digit) in S, you could also say e.g. number (tho 1 to 9 would now be a number as well) From there on, you just need to make sure the first digit is not