Fri, 13 Nov 1992 02:17:50 GMT

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) |

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.