Skip to content
Snippets Groups Projects
  1. Dec 31, 2021
  2. Dec 26, 2021
  3. Dec 20, 2021
  4. Dec 13, 2021
  5. Dec 05, 2021
    • 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.
      Unverified
      0fb7a684
    • Tomáš Pecka's avatar
      algo: make AutomataConcatenation code more readable · 8faf1384
      Tomáš Pecka authored
      I don't think we need ext::make_pair everywhere. Let's just use {}. Few
      more minor fixes to make the algorithm more readable.
      Unverified
      8faf1384
    • Tomáš Pecka's avatar
  6. Dec 03, 2021
  7. Nov 27, 2021
Loading