Re: [gnugo-devel] more on dfa

[Arend Bayer]

I wrote a while ago:
> > There is a clean way to solve this problem: Instead of having attributes
> > for all states, we could only have attributes for those states that have
> > a transition into the error state. I.e., only at the very end of the DFA
> > spiral we generate a list of all patterns that got matched.

Dave wrote:

> Well, I had a go, and have a version in which all patterns are
> pushed down the tree to the terminal states. I kept the
> attributes too, so I could check the two approaches against
> each other.
>
> Unfortunately, the dfa merges the tree where it can, so there
> can be multiple paths to the terminal state, each picking up
> different patterns.
(...)
> So I (or someone) will have to figure out how to modify the sync product
> to not merge the branches, at least for paths containing different
> attributes.

Yes, that's why the DFA size will have to be increased somewhat.

I think the cleanest way to solve this is as follows: Each DFA for a
single pattern contains exactly one state with an attribute, and from
there all arrows point to the error state.

Just change all arrows from this state to point to itself. I.e. the
pattern gets two "end" states, the usual error state with the pattern
not matched, or this state where the patttern got matched.

Then the synchronized product will automatically not merge branches
which contain different attributes matched so far.

Of course, we will then end up with loads of states that point to
itself. Either keep track of those (which we have to do anyway, as these
are the ones having attributes), and change them to point to the error
state.
The the actual dfa would be

while (next =  pdfa->states[state].next[dfa_p[dfa_pos + spiral[l][row]]]) {
  state = next;
  row++;
}
and then lookup the attributes belonging to "state" via a hash table.

Or reserve a part at the beginning (or end) of the DFA for these "end states".
Then the dfa would be:
while (state > number_of_end_states) {
  state =  pdfa->states[state].next[dfa_p[dfa_pos + spiral[l][row]]]) {
  row++;
}

> While I'm here, I noticed that dfa.c contains both routines used in
> in the main gnugo binary and routines used only in mkpat.
>
> Probably cleaner to split out the dfa construction routines into
> mkdfa.c
There are a few common routines, however.

> Also, dfa.c constructs the dfa using the types used by gnugo, but there
> is no particular reason why the datatypes used to build the dfa need
> to match the final representation of the dfa.

Especially as the DFA during built can (as far as I understand) be
larger than the final DFA.

Arend