This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] automata -> regular expression
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Yann Regis-Gianas Subject: Re: [Caml-list] automata -> regular expression
```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 (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

```