Theoretical CFG 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
--

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