Re: DFA - State Reduction

Chris F Clark <>
Fri, 27 Feb 2009 02:05:37 -0500

          From comp.compilers

Related articles
DFA - State Reduction (Alexander Morou) (2009-02-25)
Re: DFA - State Reduction (Chris F Clark) (2009-02-27)
Re: DFA - State Reduction (Chris F Clark) (2009-02-27)
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: Fri, 27 Feb 2009 02:05:37 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 09-02-127
Keywords: lex, DFA
Posted-Date: 27 Feb 2009 07:32:30 EST

Rereading this posting, I see that I misread you the first time and
you do understand the need to keep distinct terminal states separate,
but what you appear to be doing is trying to understand the
equivalence between DFAs and NFAs (and some related topics).

In a verifier (as you call it), one is only concerned with whether the
string is an element of the language, and not which element it is.
This will allow use to merge more states, as you have done. However,
as you have noted, in doing so, one loses track of which element has
been matched and recovering that information can effectively require a
full match by a non-reduced machine. Thus, a verifier throws away
"too much" information.

Now, the correspondence of NFAs and DFAs is based upon verifier
equivalence, and that's okay as long as one recongizes that fact and
is careful about preserving the distinctions (i.e. the different
outputs) as one reduces the machine. That care also would need to be
applied to relevant internal distinctions if one were using regexes
(with captures). Villi Laurakiri has a nice but very theroectical
paper which describes just such a framework.

Note, the "loose" (verifier based) corresppondence between NFAs and
DFAs is made worse when one uses them to describe unanchored regular
expressions (with implicit .*s in them) as are used in certain pattern
matching applications. Not only does one lose which pattern is being
matched, but one can also lose where the pattern actually started.

Hope this helps,

Chris Clark Internet:
Compiler Resources, Inc. or:
23 Bailey Rd Web Site:
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.