The algorithm, taken from BI-AAG course @ FIT CTU did not work
correctly when first automaton accepts a word of length 1.

There are two bugs. First, the set of final states was wrong. This was
the easy part to spot.
Second, we sometimes miss some transitions.

Consider these two automata:
 DFA a b
 ><A B -
  <B - -

 DFA a b
 ><C - -

The algorithm would result in this:
 DFA a   b
 ><S B   C
   A B|C -
   B -   -
  <C -   C

Which is of course wrong because the first automaton accepts "a + #E"
and the second one accepts a language of "b*". However, the result
doesn't accept words from neither "a" nor "ab*" which is in language
"(a+#E)b*".

The problem is that for every transition in the first automaton that
leads to a final state we create a new transition to an initial state of
the second automaton. This effectively says that "ok, we are done with
first automaton, we would accept. Let's continue from the initial state
of the second automaton".
Also, when we create a new initial state, we *only* copy transitions from
both initial states there. But if the word is of length 1 and is to be
accepted by the first automaton, we are missing this "transition to second
automaton".
In our example above, we need to add a transition (S, a) -> C and it's
fine.

I don't think we need ext::make_pair everywhere. Let's just use {}. Few
more minor fixes to make the algorithm more readable.

Jan Trávníček authored 3 years ago and Jan Trávníček committed 3 years ago

breaking change!

Jan Trávníček authored 3 years ago and Tomáš Pecka committed 3 years ago

MP algorithm was always resetting the pattern index to 0 whereas it should be
reused. This revealed that Spos should also take into account node wildcards
otherwise the presumed not-necessary-to-be-parsed part of the pattern does not
have to be matching the pattern. Which caused the computation of what does not
need to be matched to underflow.