[Caml-list] automata -> regular expression

[Caml-list] automata -> regular expression

[debarbie]

Hello,

I need to transform automata into their regular expression. I am
looking for an Ocaml library (module) which contains this algorithm
but I have only found the converse (i.e. from the regular expression
to the automata).

Can you help me?

Thank you!

D. Debarbieux

-------------------
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

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

[Yann Regis-Gianas]

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 :-) :

(* this code may be bugged since it was not tested deeply, anyway, I hope it 
will give you the idea. *)

type expression =
    Plus of expression * expression
  | Mult of expression * expression
  | Star of expression
  | Char of char
  | One 
  | Zero

let ( + ) e1 e2 = 
  match (e1, e2) with
      ((Zero, e) | (e, Zero)) -> e
    | _ -> Plus (e1, e2)

let ( * ) e1 e2 = 
  match (e1, e2) with
      ((Zero, e) | (e, Zero)) -> Zero
    | ((One, e) | (e, One)) -> e
    | _ -> Plus (e1, e2)

let ( * ) e1 e2 = Mult (e1, e2)

let star e = Star e

let rec to_string = function
    Plus (e1, e2) -> "("^ to_string e1 ^")+("^ to_string e2 ^ ")"
  | Mult (e, One) -> to_string e
  | Mult (One, e) -> to_string e
  | Mult (e1, e2) -> to_string e1 ^" "^ to_string e2 
  | Star e1       -> "("^to_string e1 ^")*"
  | Char c        -> String.make 1 c
  | One           -> "1"
  | Zero	  -> "0"
   
type state = int

(* 0 = initial state et 1 = final state. *)
let final = 1
let initial = 0

(* The labels are expression. *)
type automaton =
    ((state * expression * state) list) array *
    ((state * expression * state) list) array

let create_automaton size =
  (Array.init size (fun _ -> []), 
   Array.init size (fun _ -> []))

let add_edge (a : automaton) ((from, label, aim) as e) =
  (fst a).(from) <- e :: (fst a).(from);
  if from <> aim then 
    (snd a).(aim)  <- e :: (snd a).(aim)

let mute a f =
  for i = 0 to Array.length a - 1 do a.(i) <- f a.(i) done

let remove_state (a : automaton) s = 
  mute (fst a) (fun t -> List.filter (fun (_, _, aim) -> aim <> s) t);
  mute (snd a) (fun t -> List.filter (fun (from, _, _) -> from <> s) t);
  (fst a).(s) <- [];
  (snd a).(s) <- []

let delta (a : automaton) s = (fst a).(s)

let rdelta (a : automaton) s = (snd a).(s)

let state_elimination (a : automaton) s =
  let outer_transitions = delta a s 
  and inner_transitions = rdelta a s in
  let noloops, loops = 
    List.fold_left (fun (nl, e) ((_,l,a) as x) -> 
		      if a = s then (nl, e + l) else (x :: nl, e))
      ([], Zero)
      outer_transitions  in
  let merge (s,l,_) (_,l',s') = (s, l * star loops * l', s') in
  let merge' t = List.map (merge t) noloops in
    List.map merge' inner_transitions
 
let automaton_to_expression (a : automaton) =
  (* Here, another elimination order gives another 
     but equivalent expression. *)
  for i = 2 to Array.length (fst a) - 1 do
    List.iter (List.iter (add_edge a)) (state_elimination a i);
    remove_state a i
  done;
  List.fold_left (fun e (_,l,_) -> e + l) Zero ((fst a).(initial))

let examples =
  begin
    let a1 = create_automaton 3 in
    let a2 = create_automaton 4 in
    let a3 = create_automaton 4 in
      add_edge a1 (initial, Char 'a', 2);
      add_edge a1 (2, Char 'b', final);
      add_edge a1 (2, Char 'c', 2);
      Printf.printf "a1 = %s\n" (to_string (automaton_to_expression a1));
      
      add_edge a2 (initial, Char 'a', 2);
      add_edge a2 (initial, Char 'b', 3);
      add_edge a2 (2, Char 'b', final);
      add_edge a2 (2, Char 'c', 2);
      add_edge a2 (3, Char 'c', 3);
      add_edge a2 (3, Char 'b', final);
      add_edge a2 (final, Char 'd', initial);
      Printf.printf "a2 = %s\n" (to_string (automaton_to_expression a2));

      add_edge a3 (initial, Char 'a', 2);
      add_edge a3 (initial, One, 3);
      add_edge a3 (2, Char 'b', final);
      add_edge a3 (2, Char 'c', 2);
      add_edge a3 (3, Char 'c', 3);
      add_edge a3 (3, Char 'b', final);
      add_edge a3 (final, Char 'd', initial);
      Printf.printf "a3 = %s\n" (to_string (automaton_to_expression a3))
  end

  

      


    


-------------------
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

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

[Alain Frisch]

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