29 Apr 2007 09:18:58 -0400

Related articles |
---|

rules to generate a context free grammar alinsoar@voila.fr (A Soare) (2007-04-23) |

Re: rules to generate a context free grammar mburrel@uwo.ca.easynews.com (Mike Burrell) (2007-04-23) |

Re: rules to generate a context free grammar cdsmith@twu.net (Chris Smith) (2007-04-29) |

From: | Chris Smith <cdsmith@twu.net> |

Newsgroups: | comp.compilers |

Date: | 29 Apr 2007 09:18:58 -0400 |

Organization: | Altopia Corp. - Usenet Access - www.altopia.com |

References: | 07-04-077 07-04-096 |

Keywords: | parse, theory |

Posted-Date: | 29 Apr 2007 09:18:58 EDT |

Mike Burrell <mburrel@uwo.ca.easynews.com> wrote:

*> On 2007-04-23 07:48:12 -0400, A Soare <alinsoar@voila.fr> said:*

*> > I know that every set that can be generated by a computer can also be*

*> > generated by a context free grammar.*

*>*

*> That's not true. The set { a^n b^n c^n | n > 0 } for example, can be*

*> generated by a computer, but not by a context-free grammar.*

Well, technically speaking, it is true. If a computer has k bits of

total memory (including all registers, main memory, etc.), then it is a

DFA with 2^k states. Therefore, any set that can be generated by a

computer can also be generated by a right-linear grammar (aka, regular,

or type 3 in the Chomsky hierarchy), and thus certainly by a context-

free one. :)

*> For any program, you should be able to generate a grammar for it.*

*> Generating a pretty grammar is another story haha.*

And, of course, this goes even more for the grammars I'm talking about.

--

Chris Smith

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.