Re: [gnugo-devel] more on dfa

[Arend Bayer]

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)

and the attributes of 2,4 will be the union of the attributes of states
2 and 4, respectively.


Arend