Re: [Caml-list] Simple library to manipulate automata?

["Török Edwin" <edwin+ml-ocaml@etorok.net>]

On 05/10/2016 07:01 PM, David MENTRE wrote:
> Hello,
> 
> I would like to manipulate some basic automata in OCaml: creation, execution, minimization, display, etc.
> 
> Before re-inventing the wheel, do you know a library doing that?
> 
> From my own searches, I only found "automatx" (http://pauillac.inria.fr/~quercia/) which seems to suit my needs but (1) has a French API and (2) has no license information.

There is safa/symkat on opam [1]. It has various automata minimization algorithms, NFA -> DFA, print to .dot format.
Although it is meant for equivalence checking, so it may not be 'simple' to use for actually executing the automata, and beware that the syntax for its parser is not the usual regex [2].
(of course you can construct the automata with the API instead of parsing from a string to avoid this).

See below for some code that I wrote a while ago to visualize a DFA using safa/symkat:

[1] http://perso.ens-lyon.fr/damien.pous/symbolickat/
[2] http://perso.ens-lyon.fr/damien.pous/symbolickat/symkat.docdir/Parse.html

(*
 * $ ocamlfind ocamlopt printnfa.ml -package safa,symkat -o printnfa -linkpkg -rectypes
 * $ ./printnfa >test.dot
 * NFA states: 7
 * DFA states: 5
 * $ dot -Tsvg test.dot -o test.svg
 * $ firefox ./test.svg
 *)
let trace_dfa a states =
  let trace = Automata.SDFA.trace Format.pp_print_char Format.pp_print_char
      (Bdd.print_formula 0) in
  Trace.clear ();
  trace a states;
  print_endline (Trace.render false "\"")

let print_nfa x =
  let a,f = Automata.SNFA.reindex (Antimirov.nfa()) in
  let states = f (Antimirov.split x) in
  let number_of_states, _ = Automata.SNFA.size a states in
  Printf.eprintf "NFA states: %d\n%!" number_of_states;
  let a = Determinisation.optimised a in
  let number_of_states, _ = Automata.SDFA.size a [states] in
  trace_dfa a states; 
  Printf.eprintf "DFA states: %d\n%!" number_of_states

let print_dfa x =
  let a = Brzozowski.dfa () in
  let number_of_states, _ = Automata.SDFA.size a [x] in
  Printf.eprintf "DFA states: %d\n" number_of_states

let () =
  let e = Parse.expr "x*x*x*x*x*(x+y)z" in
  let x,_,_ = Hypotheses.eliminate [] e e in
  print_nfa x;

Best regards,
-- 
Edwin Török | Co-founder and Lead Developer

Skylable open-source object storage: reliable, fast, secure
http://www.skylable.com