Re: Why could the DFA constructed in most compiler books recognize all the prefixes of a CFL?

Volition2k@yahoo.com (Tim Carmack)
8 Oct 2003 22:26:55 -0400

          From comp.compilers
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)
| List of all articles for this month |
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.