Theoretical CFG question

norlin@essex.ecn.uoknor.edu (Norman Lin)
Fri, 13 Nov 1992 02:17:50 GMT

          From comp.compilers

Related articles
Theoretical CFG question norlin@essex.ecn.uoknor.edu (1992-11-13)
Re: Theoretical CFG question jos@and.nl (1992-11-15)
Re: Theoretical CFG question pab@cs.arizona.edu (1992-11-16)
Re: Theoretical CFG question jos@and.nl (1992-11-17)
| List of all articles for this month |

Newsgroups: comp.compilers
From: norlin@essex.ecn.uoknor.edu (Norman Lin)
Organization: Engineering Computer Network, University of Oklahoma, Norman
Date: Fri, 13 Nov 1992 02:17:50 GMT
Keywords: parse, question

An assignment was recently given and graded in my Formal Languages class.
One question intrigued me, but no one in the class managed to solve it.
The professor also said it wouldn't be instructive or useful to spend a
lot of time going over the solution (which was not provided), so I'm
posting to the net to see what response I'll get.


The problem was:
                                                                                              *
For i>=1, let b(i) denote the string in 1(0+1) that is the
binary representation of i.


Construct a CFG generating
                    +
      {0,1,#} - {b(1)#b(2)# ... #b(n) | n>=1}


After scratching my head for a week, all I could come up with were a few
elementary observations but useless observations. Does anyone have any
ideas about this problem?


Just a confused graduate student,
Norman Lin
norlin@midway.ecn.uoknor.edu
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.