sig
module type NFA =
sig
type state
type letter
module StateSet : Set.S
module Alphabet : Set.S
module StateToTransitionMap : Map.S
module TransitionMap : Map.S
type nfa = {
mutable nfa_states : StateSet.t;
mutable nfa_alphabet : Alphabet.t;
mutable nfa_start_state : StateSet.elt option;
mutable nfa_final_states : StateSet.t;
mutable nfa_transitions :
StateSet.t TransitionMap.t StateToTransitionMap.t;
}
val nfa_empty : Nfa.NFA.nfa
val fresh_nfa_empty : unit -> Nfa.NFA.nfa
val get_nfa_alphabet : Nfa.NFA.nfa -> Alphabet.t
val add_letter : Nfa.NFA.nfa -> Alphabet.elt -> unit
val add_all_letters : Nfa.NFA.nfa -> Alphabet.t -> unit
val get_nfa_states : Nfa.NFA.nfa -> StateSet.t
val get_nfa_start_state : Nfa.NFA.nfa -> StateSet.elt option
val get_nfa_final_states : Nfa.NFA.nfa -> StateSet.t
val add_state : Nfa.NFA.nfa -> StateSet.elt -> unit
val set_start_state : Nfa.NFA.nfa -> StateSet.elt -> unit
val set_final_states : Nfa.NFA.nfa -> StateSet.t -> unit
val add_final_state : Nfa.NFA.nfa -> StateSet.elt -> unit
val get_nfa_transitions :
Nfa.NFA.nfa -> StateSet.t TransitionMap.t StateToTransitionMap.t
val get_TransitionMap :
Nfa.NFA.nfa -> StateToTransitionMap.key -> StateSet.t TransitionMap.t
val get_destStateSet : 'a TransitionMap.t -> TransitionMap.key -> 'a
val get_destStateSet_s :
Nfa.NFA.nfa ->
StateToTransitionMap.key -> TransitionMap.key -> StateSet.t
val add_transitions_aux :
Nfa.NFA.nfa ->
StateToTransitionMap.key -> Alphabet.elt * StateSet.elt -> unit
val add_transitions :
Nfa.NFA.nfa ->
StateSet.elt -> (Alphabet.elt * StateSet.elt) list -> unit
val print_automata :
Nfa.NFA.nfa ->
(Alphabet.elt -> unit) -> (StateSet.elt -> unit) -> unit
val empty : Nfa.NFA.nfa -> bool
end
module MakeNFA :
functor (State : Set.OrderedType) (Letter : Set.OrderedType) ->
sig
type state = State.t
type letter = Letter.t
module StateSet :
sig
type elt = State.t
type t
val empty : t
val is_empty : t -> bool
val mem : elt -> t -> bool
val add : elt -> t -> t
val singleton : elt -> t
val remove : elt -> t -> t
val union : t -> t -> t
val inter : t -> t -> t
val diff : t -> t -> t
val compare : t -> t -> int
val equal : t -> t -> bool
val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
val for_all : (elt -> bool) -> t -> bool
val exists : (elt -> bool) -> t -> bool
val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t
val cardinal : t -> int
val elements : t -> elt list
val min_elt : t -> elt
val max_elt : t -> elt
val choose : t -> elt
val split : elt -> t -> t * bool * t
val find : elt -> t -> elt
val of_list : elt list -> t
end
module Alphabet :
sig
type elt = Letter.t
type t
val empty : t
val is_empty : t -> bool
val mem : elt -> t -> bool
val add : elt -> t -> t
val singleton : elt -> t
val remove : elt -> t -> t
val union : t -> t -> t
val inter : t -> t -> t
val diff : t -> t -> t
val compare : t -> t -> int
val equal : t -> t -> bool
val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
val for_all : (elt -> bool) -> t -> bool
val exists : (elt -> bool) -> t -> bool
val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t
val cardinal : t -> int
val elements : t -> elt list
val min_elt : t -> elt
val max_elt : t -> elt
val choose : t -> elt
val split : elt -> t -> t * bool * t
val find : elt -> t -> elt
val of_list : elt list -> t
end
module StateToTransitionMap :
sig
type key = State.t
type +'a t
val empty : 'a t
val is_empty : 'a t -> bool
val mem : key -> 'a t -> bool
val add : key -> 'a -> 'a t -> 'a t
val singleton : key -> 'a -> 'a t
val remove : key -> 'a t -> 'a t
val merge :
(key -> 'a option -> 'b option -> 'c option) ->
'a t -> 'b t -> 'c t
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
val iter : (key -> 'a -> unit) -> 'a t -> unit
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
val for_all : (key -> 'a -> bool) -> 'a t -> bool
val exists : (key -> 'a -> bool) -> 'a t -> bool
val filter : (key -> 'a -> bool) -> 'a t -> 'a t
val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
val cardinal : 'a t -> int
val bindings : 'a t -> (key * 'a) list
val min_binding : 'a t -> key * 'a
val max_binding : 'a t -> key * 'a
val choose : 'a t -> key * 'a
val split : key -> 'a t -> 'a t * 'a option * 'a t
val find : key -> 'a t -> 'a
val map : ('a -> 'b) -> 'a t -> 'b t
val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
end
module TransitionMap :
sig
type key = Letter.t
type +'a t
val empty : 'a t
val is_empty : 'a t -> bool
val mem : key -> 'a t -> bool
val add : key -> 'a -> 'a t -> 'a t
val singleton : key -> 'a -> 'a t
val remove : key -> 'a t -> 'a t
val merge :
(key -> 'a option -> 'b option -> 'c option) ->
'a t -> 'b t -> 'c t
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
val iter : (key -> 'a -> unit) -> 'a t -> unit
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
val for_all : (key -> 'a -> bool) -> 'a t -> bool
val exists : (key -> 'a -> bool) -> 'a t -> bool
val filter : (key -> 'a -> bool) -> 'a t -> 'a t
val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
val cardinal : 'a t -> int
val bindings : 'a t -> (key * 'a) list
val min_binding : 'a t -> key * 'a
val max_binding : 'a t -> key * 'a
val choose : 'a t -> key * 'a
val split : key -> 'a t -> 'a t * 'a option * 'a t
val find : key -> 'a t -> 'a
val map : ('a -> 'b) -> 'a t -> 'b t
val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
end
type nfa = {
mutable nfa_states : StateSet.t;
mutable nfa_alphabet : Alphabet.t;
mutable nfa_start_state : StateSet.elt option;
mutable nfa_final_states : StateSet.t;
mutable nfa_transitions :
StateSet.t TransitionMap.t StateToTransitionMap.t;
}
val nfa_empty : nfa
val fresh_nfa_empty : unit -> nfa
val get_nfa_alphabet : nfa -> Alphabet.t
val add_letter : nfa -> Alphabet.elt -> unit
val add_all_letters : nfa -> Alphabet.t -> unit
val get_nfa_states : nfa -> StateSet.t
val get_nfa_start_state : nfa -> StateSet.elt option
val get_nfa_final_states : nfa -> StateSet.t
val add_state : nfa -> StateSet.elt -> unit
val set_start_state : nfa -> StateSet.elt -> unit
val set_final_states : nfa -> StateSet.t -> unit
val add_final_state : nfa -> StateSet.elt -> unit
val get_nfa_transitions :
nfa -> StateSet.t TransitionMap.t StateToTransitionMap.t
val get_TransitionMap :
nfa -> StateToTransitionMap.key -> StateSet.t TransitionMap.t
val get_destStateSet : 'a TransitionMap.t -> TransitionMap.key -> 'a
val get_destStateSet_s :
nfa -> StateToTransitionMap.key -> TransitionMap.key -> StateSet.t
val add_transitions_aux :
nfa ->
StateToTransitionMap.key -> Alphabet.elt * StateSet.elt -> unit
val add_transitions :
nfa -> StateSet.elt -> (Alphabet.elt * StateSet.elt) list -> unit
val print_automata :
nfa -> (Alphabet.elt -> unit) -> (StateSet.elt -> unit) -> unit
val empty : nfa -> bool
end
end