Wrong fsm/complement

[pietrobraione]

The construction of the complement of an automaton (automat.fsm/complement) is wrong, as it appears by inspecting the svg of the complement of a, or of the complement of a*. Currently the function builds the complement by "switching" final and nonfinal states. This works only for complete DFAs but not for incomplete DFAs or NFAs (see https://en.wikipedia.com/wiki/Deterministic_finite_automaton for definitions). In the general case the construction should be as follows:

1- first, if the automaton is nondeterministic, make it deterministic; call d the obtained deterministic automaton; 2- then, if d is incomplete, make it complete by adding a "refuse all" nonfinal state S, and transitions s -[DEF]->S from all the states s to S; call c the resulting automaton; 3- finally, the final and nonfinal states of c are switched. Note that this way S becomes an "accept all" state.

In the current implementation both step 1 and step 2 are missing.

[ztellman]

Makes sense, I'll make the requisite changes this weekend.

[pietrobraione]

I had a look at the code, and I have implemented a fixed version of complement that seems to work:

(defn complement-fixed
  "Returns the complement of the given automaton."
  [x]
  (let [fsm (->dfa (automat.compiler.core/parse-automata x))
        st (state)]
  (dfa
    (start fsm)
    (set/union #{st} (set/difference (states fsm) (accept fsm)))
    (merge (zipmap* (states fsm) 
                    #(let [tr (fsm/input->state fsm %)] (if (contains? tr fsm/default) tr (merge tr {fsm/default st})))) 
           {st {default st}})
    (zipmap* (states fsm) #(input->actions fsm %)))))

[ztellman]

If you'd like to open a pull request, I'm happy to accept your change.

On Thu, May 19, 2016 at 1:22 AM Pietro Braione notifications@github.com wrote:

I had a look at the code, and I have implemented a fixed version of complement that seems to work:

(defn complement-fixed "Returns the complement of the given automaton." [x](let [fsm %28->dfa %28automat.compiler.core/parse-automata x%29%29 st %28state%29] %28dfa %28start fsm%29 %28set/union #{st} %28set/difference %28states fsm%29 %28accept fsm%29%29%29 %28merge %28zipmap* %28states fsm%29

%28let [tr %28fsm/input->state fsm %%29] %28if %28contains? tr fsm/default%29 tr %28merge tr {fsm/default st}%29%29%29%29

       {st {default st}}%29
%28zipmap* %28states fsm%29 #%28input->actions fsm %%29%29%29))

— You are receiving this because you commented.

Reply to this email directly or view it on GitHub https://github.com/ztellman/automat/issues/41#issuecomment-220258580

[pietrobraione]

I will - but I need a little more time to test everything. Cheers Pietro

[pietrobraione]

I have a question: What is the right way to add a state to an automaton?

[ztellman]

I'm sorry, I've fallen behind on all of this. What do you mean by "add a state"? You can add it to the state->input->state data structure, and it should just work.

[pietrobraione]

Nevermind, I also fell behind as you can notice. My question was: What is the right way to create a new State object and add it to the states of an automaton? Let us say that I have some-automaton and I want to build another automaton that is some-automaton plus one additional acceptance state. Currently I do something like that:

(let [new-state (fsm/->State nil (Object.) {} nil)]
    (fsm/dfa
        (fsm/start some-automaton)
        (set/union #{new-state} (fsm/accept some-automaton))
        ... ;rest omitted
    )
)

Is my definition of new-state the right way of creating a new state?