Re: DFA - State Reduction

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


******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

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