Computer Science Canada

Grammar and recursive definition help
Author:  bladeb2k [ Sun Aug 19, 2007 10:01 am ]
Post subject:  Grammar and recursive definition help
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
Author:  rizzix [ Sun Aug 19, 2007 10:41 am ]
Post subject:  Re: Grammar and recursive definition help
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.
Author:  bladeb2k [ Sun Aug 19, 2007 11:15 am ]
Post subject:  Re: Grammar and recursive definition help
thankyou very much - that is such a help i cannot begin to explain!!!! http://compsci.ca/v3/images/smiles/icon_biggrin.gif
Very Happy

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy