8 Oct 2003 22:26:55 -0400

Related articles |
---|

Why could the DFA constructed in most compiler books recognize all t Volition2k@yahoo.com (2003-09-30) |

Re: Why could the DFA constructed in most compiler books recognize all venkatesha.murthy@windriver.com (Venkatesha Murthy) (2003-10-04) |

Re: Why could the DFA constructed in most compiler books recognize all Volition2k@yahoo.com (2003-10-08) |

Re: Why could the DFA constructed in most compiler books recognize all Volition2k@yahoo.com (2003-10-12) |

From: | Volition2k@yahoo.com (Tim Carmack) |

Newsgroups: | comp.compilers |

Date: | 8 Oct 2003 22:26:55 -0400 |

Organization: | http://groups.google.com |

References: | 03-09-126 03-10-013 |

Keywords: | parse, theory |

Posted-Date: | 08 Oct 2003 22:26:54 EDT |

Unfortunately I cannot find that proof in the second edition of that book.

Maybe it is in the first edition,sigh.

Venkatesha Murthy <venkatesha.murthy@windriver.com> wrote

*> If I remember right, this is a result due to Knuth. I don't have the*

*> reference handy, but Hopcroft and Ullman's book "Introduction to*

*> Automata Theory, Formal Languages and Computation" should have it.*

*>*

*> Venkatesh*

*>*

*>*

*> Tim Carmack wrote:*

*>*

*> > I have read many textbooks on compiling theory and all of them*

*> > teach me how to construct a DFA to recognize all viable prefixes*

*> > of a CFL but without strict proof concerning why all these prefixes*

*> > constitute a regualr language and the DFA constructed could recognize*

*> > this regular language. ...*

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.