Module Automate

module Automate: sig .. end

Automates

Types

type ('a, 'b) auto_min = {

	`etats :'a list;`
	`initial :'a;`
	`alphabet :'b list;`
	`final :'a -> bool;`
	`trans :'a -> 'b -> 'a;`

}

Type d'un automate déterministe avec des états de type 'a sur des lettres de type 'b.

type 'a mot = 'a list

Type d'un mot sur un alphabet de type 'a.

val exec : ('b, 'a) auto_min -> 'a mot -> 'b

Exécution d'un automate déterministe sur un mot.

type ('a, 'b) automate = 'a list * 'a list * 'a list * 'b list * ('a * 'b * 'a) list

Type d'un automate avec des états de type 'a sur des lettres de type 'b. Un tel automate est vu comme un tuple (e,i,f,a,t) où :

e est l'ensemble des états,
i est l'ensemble des états initiaux,
f est l'ensemble des états finaux,
a est l'alphabet,
tr est l'ensemble des transitions

Opérations sur les automates

val map : ('a -> 'b) -> ('a, 'c) automate -> ('b, 'c) automate

Application d'une fonction de renommage à tous les états d'un automate.

val simpl : ('a, 'b) automate -> (int, 'b) automate

Renommage des états d'un automate avec des entiers.

val build : (module Tools.Base with type t = 'a) ->
       'a ->
       ('a -> bool) -> 'b list -> ('a -> 'b -> 'a) -> ('a, 'b) automate

Construction d'un automate à partir d'une fonction de transition.

val build_avec_puit : (module Tools.Base with type t = 'a) ->
       'a ->
       ('a -> bool) ->
       'b list -> ('a -> 'b -> 'a) -> 'a -> ('a, 'b) automate

Construction d'un automate à partir d'une fonction de transition, en omettant l'état puit.

val build2 : (module Tools.Base with type t = 'a) ->
       'a ->
       ('a -> bool) ->
       'b list -> ('a -> 'b -> 'a list) -> ('a, 'b) automate

Construction d'un automate à partir d'une fonction de transition.

val build_acc : (module Tools.Base with type t = 'a) ->
       'a ->
       ('a -> bool) ->
       'b list -> ('c -> 'a -> 'b -> 'c * 'a) -> 'c -> ('a, 'b) automate

Construction d'un automate à partir d'une fonction de transition utilisant un accumulateur.

val build2_acc : (module Tools.Base with type t = 'a) ->
       'a list ->
       ('a -> bool) ->
       'b list ->
       ('c -> 'a -> 'b -> 'c * 'a list) -> 'c -> ('a, 'b) automate

Construction d'un automate à partir d'une fonction de transition.

val rev : ('a, 'b) automate -> ('a, 'b) automate

Automate mirroir.

val determ : (module Tools.Base with type t = 'a) ->
       (module Tools.Base with type t = 'b) ->
       ('a, 'b) automate -> ('a list, 'b) automate

Déterminisation.

val determ2 : (module Tools.Base with type t = 'a) ->
       (module Tools.Base with type t = 'b) ->
       ('a, 'b) automate -> ('a list, 'b) automate

Déterminisation, sans état puit.

val min : (module Tools.Base with type t = 'a) ->
       (module Tools.Base with type t = 'b) ->
       ('a, 'b) automate -> ('a list list, 'b) automate

Minimisation.

val min2 : (module Tools.Base with type t = 'a) ->
       (module Tools.Base with type t = 'b) ->
       ('a, 'b) automate -> ('a list list, 'b) automate

Minimisation, sans état puit.

val convert : (module Tools.Base with type t = 'a) ->
       (module Tools.Base with type t = 'b) ->
       ('a, 'b) automate -> ('a list list option, 'b) auto_min

Conversion vers un automate minimal fonctionnel

val equiv : (module Tools.Base with type t = 'a) ->
       (module Tools.Base with type t = 'b) ->
       (module Tools.Base with type t = 'c) ->
       ('a, 'c) automate ->
       ('b, 'c) automate -> 'c mot option

Test simple d'équivalence d'automates

val hkequiv : (module Tools.Base with type t = 'a) ->
       (module Tools.Base with type t = 'b) ->
       (module Tools.Base with type t = 'c) ->
       ('a, 'c) automate ->
       ('b, 'c) automate -> 'c mot option

Algorithme d'Hopcroft et Karp

val access : (module Tools.Base with type t = 'a) ->
       (module Tools.Base with type t = 'b) ->
       ('a, 'b) automate -> ('a, 'b) automate

Nettoyage de l'automate, en ne gardant que les états accessibles.

val coaccess : (module Tools.Base with type t = 'a) ->
       (module Tools.Base with type t = 'b) ->
       ('a, 'b) automate -> ('a, 'b) automate

Nettoyage de l'automate, en ne gardant que les états co-accessibles.

val puits : (module Tools.Base with type t = 'a) -> ('a, 'b) automate -> 'a list

Détection des états puits : q tel que pour toute lettre a, soit il n'y a pas de transition étiquetée par a depuis q, soit il y a une transition q -a-> q.

val etats_coaccessibles : (module Tools.Base with type t = 'a) ->
       (module Tools.Base with type t = 'b) -> ('a, 'b) automate -> 'a list

Liste des états accessibles d'un automate.

val etats_non_puit : (module Tools.Base with type t = 'a) -> ('a, 'b) automate -> 'a list

Liste des états n'étant pas des puits d'un automate.

Traduction en format dot

val sprint_auto : ('a -> string) -> ('b -> string) -> ('a, 'b) automate -> string

Impression comme chaîne de caractères.

val print_auto : Pervasives.out_channel ->
       ('a -> string) -> ('b -> string) -> ('a, 'b) automate -> unit

Impression dans un canal.

val print_to_file : string ->
       ('a -> string) -> ('b -> string) -> ('a, 'b) automate -> unit

Impression dans un fichier.