Re: [gnugo-devel] more on dfa

[Dave Denholm]

Arend Bayer <address@hidden> writes:

> Dave Denholm wrote:
> 
> > Hmm - still confused. Surely using the next link as a flag in this way is 
> > lost
> > when a pattern is added.
> >
> > Eg pattern 1 is O
> >    pattern 2 is OXX
> >    pattern 3 is OX.
> >
> > After adding pattern 1 we have
> >
> >   1 -O-> 2   and 2 points back to itself to indicate match.
> >
> > Add pattern 2
> >
> >   1 -O-> 2 -X-> 3 -X-> 4
> (Let me take this as the DFA of pattern 2)
> >
> > and we have "lost" the flag on 2 that loops back to itself.
> 
> This "pointing to itself" is only meant to solve the problem of merging
> branches with different attributes. You still have to take care of handling
> the attributes themselves.
> 
> So here state 2 in pattern 2 points to itself, and state 4 in pattern 2.
> The synchronized product is then
> 
> 1,1 -O-> 2,2 -X-> 2,3 -X-> 2,4 -> 2,4
> (this is what sync_prod() should do automatically)
> 


Oops -  yes, of course - I keep missing the detail that we are making a new
dfa, not modifying an existing dfa. So we don't "lose" the flag, we
incorporate the information it contained into the new dfa we are building...

dd
-- 
address@hidden          http://www.insignia.com