Re: [gnugo-devel] more on dfa

[Arend Bayer]

Dave wrote:

> Arend Bayer writes:
>
> > 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:
> >
(...)
> > > 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.
> >
> >
> > 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.
>
>
> I don't entirely follow - will have to think about it.
>
> What about two identical patterns ?
> Or a pattern which is a subset of a larger pattern ?

Hmm, I think if you take two identical patterns, the synchronized product
is exactly the same as the individual DFAs (except for the attribute, of
course).

Maybe an example makes it clear what I mean (and hence also if I am wrong):

Pattern1: O
Pattern2: ?X
The DFA to Pattern1 has states 1, 2 and error.
1: go to 2 if O, to error otherwise
2: match Pattern1, go to error next (old way) resp. stay at state 2 (if
implemented the way I suggested).

Pattern2:
1: go to 2
2: go to 3 if X, to error otherwise
3: match Pattern1, go to error next (old way) resp. stay at state 2 (if
implemented the way I suggested).

Now the relevant state in the synchronized product is (2, 2). With my
proposed change, this would go to (3, 2) next if an 'X' is read. Currently,
it would go to (3, error) instead, which forgets whether we were at
(2, error) or (2, 2) instead (i.e. forgetting whether Pattern1 got matched).

I am pretty sure this should work in all cases. Probably it is however
clearer to use negative values for those end states with attributes as you
suggested. The point is then that
* the DFA for one pattern has exactly one negative state (successful match),
* when doing synchronized product, a state of the form (a=negative,
b=positive) will become a _positive_ state; it's arrows have to be set
according to the arrows starting from state b, while a is just left
constant and remembers which patterns got matched in the first DFA.

Arend