* Re: [Caml-list] automata -> regular expression
2004-08-02 12:58 [Caml-list] automata -> regular expression debarbie
@ 2004-08-03 8:25 ` Yann Regis-Gianas
2004-08-03 9:25 ` Alain Frisch
0 siblings, 1 reply; 3+ messages in thread
From: Yann Regis-Gianas @ 2004-08-03 8:25 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 3+ messages in thread