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

Venkatesha Murthy <venkatesha.murthy@windriver.com>
4 Oct 2003 14:46:10 -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: Venkatesha Murthy <venkatesha.murthy@windriver.com>
Newsgroups: comp.compilers
Date: 4 Oct 2003 14:46:10 -0400
Organization: Wind River Systems Inc.
References: 03-09-126
Keywords: parse, theory
Posted-Date: 04 Oct 2003 14:46:10 EDT

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.