From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id LAA12577; Tue, 3 Aug 2004 11:25:22 +0200 (MET DST) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id LAA14276; Tue, 3 Aug 2004 11:25:21 +0200 (MET DST) Received: from nef.ens.fr (nef.ens.fr [129.199.96.32]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i739PKEV000688; Tue, 3 Aug 2004 11:25:20 +0200 Received: from clipper.ens.fr (clipper-gw.ens.fr [129.199.1.22]) by nef.ens.fr (8.12.11/1.01.28121999) with ESMTP id i739PKrg040135 ; Tue, 3 Aug 2004 11:25:20 +0200 (CEST) Received: from localhost (frisch@localhost) by clipper.ens.fr (8.12.3/jb-1.1) id i739PIKI008071 ; Tue, 3 Aug 2004 11:25:18 +0200 (MET DST) X-Authentication-Warning: clipper.ens.fr: frisch owned process doing -bs Date: Tue, 3 Aug 2004 11:25:18 +0200 (MET DST) From: Alain Frisch X-X-Sender: frisch@clipper.ens.fr Reply-To: Alain Frisch To: Yann Regis-Gianas cc: caml-list@inria.fr Subject: Re: [Caml-list] automata -> regular expression In-Reply-To: <200408031025.30412.Yann.Regis-Gianas@inria.fr> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=ISO-8859-1 Content-Transfer-Encoding: 8BIT X-Virus-Scanned: by amavisd-milter (http://amavis.org/) X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-1.3.3 (nef.ens.fr [129.199.96.32]); Tue, 03 Aug 2004 11:25:20 +0200 (CEST) X-Miltered: at nez-perce with ID 410F5A00.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; alain:01 frisch:01 alain:01 frisch:01 caml-list:01 yann:01 regis-gianas:01 2004:99 lifl:01 transitions:01 sub-language:01 expressive:01 heuristics:01 regexps:01 cduce:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Tue, 3 Aug 2004, Yann Regis-Gianas wrote: > Le lundi 2 Août 2004 14:58, debarbie@lazarus.lifl.fr a écrit : > > Hello, > > [...] > > Can you help me? > > Well, there are two popular methods to convert an automaton into a rational > expression : the Yamada/McNaughton method and the state elimination method. > The former can be found in every good book about FSMs. The latter is a bit > more simple : it works on a generalized finite state machine (a fsm whose > labels are rational expressions), removes the automaton states one by one and > for each state removal, builds the transitions that denote the sub-language > of the removed state. A piece of code might be more expressive :-) : Here is another implementation, with some (naive) heuristics to produce compact regexps: http://www.cduce.org/c-bin/viewcvs.cgi/misc/pretty.ml?rev=1.3 The interface is: (* Decompilation of regular expressions *) type 'a regexp = | Empty | Epsilon | Seq of 'a regexp * 'a regexp | Alt of 'a regexp * 'a regexp | Star of 'a regexp | Plus of 'a regexp | Trans of 'a module Decompile(H : Hashtbl.S)(S : Set.OrderedType) : sig val decompile: (H.key -> (S.t * H.key) list * bool) -> H.key -> S.t regexp end H.key: type of nodes S.t: type of transitions The first argument is the transition relation (maps a node to the list of its outgoing transitions + final flag), the second is the initial state. -- Alain ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners