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

[rizzix]

Using left-most derivation:
a)

code:

data => item rest => number rest => number , data => number , item rest => number , number rest => number , number , data => number , number , item rest => number , number , { data } rest => number , number , { item rest } rest => number , number , { number  rest } rest => number , number , { number Λ } rest => number , number , { number Λ } Λ

Here I assumed / took number as a Token. That is, it is a terminal in the productions. This my not be the case in the grammar above in which case you need to derive number to digit or digit number which might further be derived to sequence of 0s and/or 1s. If you do this, your most completely derived result would be 10, 1, {1}.

Obviously I'm not going to answer all your questions. If you understand what I'm doing above, the rest are really easy.

[bladeb2k]

thankyou very much - that is such a help i cannot begin to explain!!!! http://compsci.ca/v3/images/smiles/icon_biggrin.gif
Very Happy