From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id F21C27F612 for ; Tue, 10 May 2016 23:20:57 +0200 (CEST) IronPort-PHdr: 9a23:9K4zAR27oEEAaLECsmDT+DRfVm0co7zxezQtwd8ZsegSKfad9pjvdHbS+e9qxAeQG96LurQd16GP7v6ocFdDyKjCmUhKSIZLWR4BhJdetC0bK+nBN3fGKuX3ZTcxBsVIWQwt1Xi6NU9IBJS2PAWK8TWM5DIfUi/yKRBybrysXNWC3oLui6vrpsObSj4LrQT+SIs6FA+xowTVu5teqqpZAYF19CH0pGBVcf9d32JiKAHbtR/94sCt4MwrqHwI6Lpyv/JHBK7zeqB9Sb1DEBwnNXo07Yvlr0rtVwyKs0eCSPsV2jdEHAnDpEX3UojwtGj/sq960yCfOeX7UbcuXjfk6ap3Hky7wBwbPiI0pTmEwvd7i7hW9Uqs Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=edwin+ml-ocaml@etorok.net; spf=Pass smtp.mailfrom=edwin+ml-ocaml@etorok.net; spf=None smtp.helo=postmaster@mail.etorok.net Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of edwin+ml-ocaml@etorok.net) identity=pra; client-ip=62.210.252.135; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="edwin+ml-ocaml@etorok.net"; x-sender="edwin+ml-ocaml@etorok.net"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of edwin+ml-ocaml@etorok.net designates 62.210.252.135 as permitted sender) identity=mailfrom; client-ip=62.210.252.135; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="edwin+ml-ocaml@etorok.net"; x-sender="edwin+ml-ocaml@etorok.net"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail.etorok.net) identity=helo; client-ip=62.210.252.135; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="edwin+ml-ocaml@etorok.net"; x-sender="postmaster@mail.etorok.net"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0BtBQCATzJX/4f80j5dFoMiVStSgnu4PiSFbAKBOTwQAQEBAQEBAQFkJ4ItghUBAQQMFwQLAQ0VJQEOCQIYAgIYDgICVxMIAQGIKwqLMpw2Z4RBBow+AQZ8hxqCVoQrFEyCNIJZjlSJWIV+iCCCN4xij0A3K4E2AQEIAQEBAYIqOTIBAQGHSoE9AQEB X-IPAS-Result: A0BtBQCATzJX/4f80j5dFoMiVStSgnu4PiSFbAKBOTwQAQEBAQEBAQFkJ4ItghUBAQQMFwQLAQ0VJQEOCQIYAgIYDgICVxMIAQGIKwqLMpw2Z4RBBow+AQZ8hxqCVoQrFEyCNIJZjlSJWIV+iCCCN4xij0A3K4E2AQEIAQEBAYIqOTIBAQGHSoE9AQEB X-IronPort-AV: E=Sophos;i="5.24,606,1454972400"; d="scan'208";a="217640011" Received: from mail.etorok.net ([62.210.252.135]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 10 May 2016 23:20:57 +0200 Received: by mail.etorok.net (OpenSMTPD) with ESMTP id be0b8087 for ; Tue, 10 May 2016 21:20:56 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha1; c=simple; d=etorok.net; h=subject:to :references:from:message-id:date:mime-version:in-reply-to :content-type:content-transfer-encoding; s=ml; bh=I+xkX3czNjopQB x3mnC3VUkBccY=; b=SOiaPDT0HIJTv7poIkXVvs+XBHvx8BbcmZdhQ5V78foh6A Uaq1wQ+7xq41d8/8KczoPK1tYlUdMjrYFH4PEsSJVtF9DLYTbfeQhn2S70KYv65L WoOoYBsCfENEWt5qsX90H0XYba6pzqKBeKwXBXSrnKsvJ5goEbgrat2vGKqPg= DomainKey-Signature: a=rsa-sha1; c=simple; d=etorok.net; h=subject:to :references:from:message-id:date:mime-version:in-reply-to :content-type:content-transfer-encoding; q=dns; s=ml; b=KrOl+oTu r751btFxT8otusPB9mwjLMIY4pO7axhvzm2U4PWF7co/io2+3LXbHmOHFOyMEJbE WwId2r35BS8gblb6kvBl2EDUQsyXFlvx87JHubQFYfNLEUevMT65Rlo0dcn2jXAK qXzs6ClpNuqKRIjDOq6dWxdSPjTfhGapNsE= Received: by mail.etorok.net (OpenSMTPD) with ESMTPSA id 0bbf1e0d TLS version=TLSv1/SSLv3 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NO for ; Tue, 10 May 2016 21:20:56 +0000 (UTC) To: caml-list@inria.fr References: <573205D0.3010508@linux-france.org> From: =?UTF-8?B?VMO2csO2ayBFZHdpbg==?= Message-ID: <8839045c-d17c-13bc-13e9-08d38e3449e6@etorok.net> Date: Wed, 11 May 2016 00:20:55 +0300 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.0 MIME-Version: 1.0 In-Reply-To: <573205D0.3010508@linux-france.org> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Subject: Re: [Caml-list] Simple library to manipulate automata? 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