1. ## Induction and Grammar

Hi all, I have some problems that I'm not sure about their solution.

Let B be the set of all bit-string (non-null strings over the alphabet {0,1})
a/ Define the set B inductively
b/ Find an unambiguous grammar for the non-negative binary integers such that every number is represented uniquely without extra 0's at the beginning (ex: 1011011001)

My solution is
a/ Basic step: 0 ∈ B, 1 ∈ B
I don't know how to do the recursive step.

b/ S->1 | 1A
A->0| 0A | S
I'm not sure if I'm right. Do we have another way to solve it?

2. ## Re: Induction and Grammar

Originally Posted by math88
a/ Basic step: 0 ∈ B, 1 ∈ B
I don't know how to do the recursive step.
You don't know how to convert a binary string of length n into a binary string of length n + 1?

Originally Posted by math88
b/ S->1 | 1A
A->0| 0A | S
I believe this is a correct grammar that produces all positive numbers. It is unambiguous because each intermediate string contains a single nonterminal.

I would use part (a) here. A nonnegative binary number is either a 0 or a 1 followed by a possibly empty binary string. So the following grammar should work.

S -> 0 | 1A
A -> 1A | 0A | empty

3. ## Re: Induction and Grammar

Originally Posted by emakarov
You don't know how to convert a binary string of length n into a binary string of length n + 1?
So part a) is 0 ∈ B, 1 ∈ B and if x,y ∈ B => xy ∈ B
Am I right?

4. ## Re: Induction and Grammar

Originally Posted by math88
So part a) is 0 ∈ B, 1 ∈ B and if x,y ∈ B => xy ∈ B
This works, but a more obvious answer is

0 ∈ B, 1 ∈ B and if x ∈ B => 0x ∈ B and 1x ∈ B.

Your answer requires a moment of thought to understand why it generates all strings, though it is obvious.