• Tomáš Pecka's avatar
    algo: Fix AutomataConcatenation when first automaton has a word of len 1 · 0fb7a684
    Tomáš Pecka authored
    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.
    0fb7a684
Name
Last commit
Last update
..
src Loading commit data...
test-src Loading commit data...
CMakeLists.txt Loading commit data...
Doxyfile Loading commit data...