Grammar and recursive definition help

[bladeb2k]

basically this is 2 questions i have to do which is the final part of a paper that started with me having to design a turing machine that checks that strings of binary digits are formatted correctly with { and } formatted correctly. ie
10 {100 } 1 is ok but }101{1} is not.

Q) The following grammar is proposed for the data above.
data → item rest
item → number | { data }
rest → Λ | , data
digit → 0 | 1
number → digit | digit number
where Λ is the empty string and characters in bold such as . , { and } stand for themselves. data is the start symbol. Show the steps required to demonstrate that the following strings represent legal input data.
a) 10, 1, {1} b) {1,{1}} c) 1
Is the input {} legal? Justify your answer by reference to the grammar. 25 marks


Q) Assuming that the meaning of ?number? in the above grammar is understood complete the following recursive definition of valid input by filling in the blanks.
1. A number is a valid input
2. If X is a valid input so is _______
3. If X and Y are valid inputs so is __________
4. These represent all legal inputs.
Using these definition show that the following are legal inputs
a) 1, {1}
b) {1,{1}}
c) 1
Is {} a legal input according to this definition? Justify your answer.
25 marks