Re: [gnugo-devel] more on dfa

[Dave Denholm]

Arend Bayer <address@hidden> writes:

> 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.
> > >
> >
> > 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 ?
> 


> 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).
> 


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

and we have "lost" the flag on 2 that loops back to itself.



> 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.
> 



Well, anyway, what I have so far is that while building the dfa, each state
has two attributes. One which lists the patterns matched at that node, and
one which lists all the patterns matched up to and including that node.
(The former is probably useless in the long term, but in the short term I
 would ideally like to be able to run the engine in the old mode, asserting
 that the pattern list accumulated is the same as the one stored in the dfa)




I'm also trying to add a pattern to a dfa in situ, rather than making a new dfa 
out
of two input dfas. I'm hoping this will offset the performance problems
of not using the pool of smaller dfas (since I am still assuming I add
patterns one at a time, in order of increasing length).

The algorithm is then that product of (L,0) is just L itself. It does leave
unreachable states in the dfa, but they can easily be pruned once at the end.
(Does mean that the code for measuring the incremental size increases in the
dfa is useless...)

Unfortunately, I've got a problem with my state cache for (0,R), which means I 
end
up appending the new pattern to each existing terminal state which can match
it :-(



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