Re: [Caml-list] automata -> regular expression

[Alain Frisch <Alain.Frisch@ens.fr>]

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