Cours 6

Htmligure
Version & licenses
Creative Commons License

Exemple d'utilisation des foncteurs.

Guyslain
Thursday, 21 July 2016

Retour au sommaire.

Exemple : l'algorithme de Floyd-Wharshall, une orgie de foncteurs.

À titre d'exemple d'utilisation des foncteurs, on peut considérer l'algorithme de Floyd-Warshall. L'un de ses avatars permet de calculer les distances entre toute paire de sommets d'un graphe. Mais l'algorithme est plus général: il permet aussi de calculer le langage reconnu par un automate, de résoudre des systèmes d'équations linéaires, etc.

La version générale travaille sur une matrice dont les coefficients sont dans une algèbre de Kleene, c'est-à-dire un semi-anneau auquel on ajoute un opérateur *. On commence donc pour poser des interfaces pour ces deux notions :

  1. module type Semiring = sig
  2. type t
  3. val zero : t
  4. val one : t
  5. val add : t -> t -> t
  6. val mult : t -> t -> t
  7. val pp : Format.formatter -> t -> unit
  8. end

  10. module type KleeneAlgebra = sig
  11. module S : Semiring
  12. val star : S.t -> S.t
  13. end

Dans Semiring, on ajoute une fonction pp de pretty-printing. Cela permettra plus tard de créer automatiquement les pretty-printers pour les matrices. Dans KleeneAlgebra, nous aurions pu plutôt inclure Semiring (avec include Semiring). Nous aurons cependant plus tard besoin de faire directement référence à la restriction au semi-anneau d'une algèbre de Kleene, donc nous utilisons un sous-module.

Nous pouvons maintenant définir l'interface d'une matrice carrée. Dans cet exemple nous allons fixé la dimension en utilisant un module de paramétrage. Ainsi des matrices de dimensions différentes appartiendront à des modules différents. Un avantage est qu'on garanti ainsi que les additions et les multiplications matricielles sont toujours définis : pas de risque d'additionner des matrices de dimensions différentes, l'inférence de type ne l'acceptera pas.

  1. module type MatrixDim = sig
  2. val dim : int
  3. end

  5. module type Matrix = sig
  6. type t
  7. type coefficient
  8. module D : MatrixDim
  9. val create : (int -> int -> S.t) -> t
  10. val get_coef : t -> int -> int -> S.t
  11. val pp : Format.formatter -> t -> unit
  12. end

On se contente d'avoir la dimension, une fonction de construction et une fonction d'accès aux coefficients. Pour créer une représentation, il nous faut un type pour les coefficients ayant aussi une fonction de pretty-printing. On va donc définir une interface pour un type pretty-printable. Par ailleurs, on peut facilement représenter une matrice comme une fonction des paires d'entiers vers les coefficients. Pour plus d'efficacité, on va néanmoins stocker les coefficients dans une structure de données : un dictionnaire des paires d'entiers vers les coefficients. Il faut donc définir cela :

  1. module type PrintableType = sig
  2. type t
  3. val pp : Format.formatter -> t -> unit
  4. end

  6. module IntPair = struct
  7. type t = int * int
  8. let compare (x1,y1) (x2,y2) = if x1 = x2 then y1 - y2 else x1 - x2
  9. end

  11. (* Dictionaries with keys of type [int * int] *)
  12. module IPMap = Map.Make(IntPair)


  15. (* Double functor: matrix dimension + coefficients *)
  16. module MakeMatrix :
  17. functor (D : MatrixDim) ->
  18. functor (Coef : PrintableType) -> Matrix with type coefficients = Coef.t
  19. =
  20. functor (D : MatrixDim) ->
  21. functor (Coef : PrintableType) ->
  22. struct

  24. type t = Coef.t IPMap.t
  25. type coefficients = Coef.t
  26. module D = D

  28. let get_coef mat i j = IPMap.find (i,j) mat

  30. let indices = List.range ~stop:`inclusive 1 D.dim
  31. let positions = List.cartesian_product indices indices

  33. let create fct =
  34. List.fold_left
  35. ~f:(fun map (i,j) -> IPMap.add (i,j) (fct i j) map)
  36. ~init:IPMap.empty
  37. positions

  39. let pp_line mat ppf line =
  40. let open Format in
  41. fprintf ppf "@[<h 0>%a@]"
  42. (pp_print_list ~pp_sep:(fun ppf () -> pp_print_break ppf 3 0) Coef.pp)
  43. (List.map ~f:(get_coef mat line) indices)

  45. let pp ppf mat =
  46. let open Format in
  47. fprintf ppf "@[<v 0>%a@]"
  48. (pp_print_list ~pp_sep:pp_print_cut (pp_line mat))
  49. indices

  51. end

Ce qui est intéressant avec les matrices est qu'elles forment elles-mêmes un semi-anneau, si les coefficients forment un semi-anneau. On peut le prouver en donnant un foncteur, prenant une représentation des matrices, un semi-anneau sur les coefficients, et produisant un semi-anneau des matrices. Autrement dit, on va écrire l'addition et la multiplication matricielle.


  2. module type MatrixSemiring =
  3. sig
  4. include Matrix
  5. module S : Semiring with type t = coefficients
  6. val zero : t
  7. val one : t
  8. val add : t -> t -> t
  9. val mult : t -> t -> t
  10. end

  12. module MakeMatrixSemiring :
  13. functor (M : Matrix) ->
  14. functor (S : Semiring with type t = M.coefficients) ->
  15. MatrixSemiring
  16. with module D = M.D
  17. and type t = M.t
  18. and type coefficients = M.coefficients
  19. =
  20. functor (M : Matrix) ->
  21. functor (S : Semiring with type t = M.coefficients) ->
  22. struct
  23. include M
  24. module S = S
  25. let (+) = S.add
  26. let ( * ) = S.mult

  28. let zero = create (fun i j -> S.zero)
  29. let one = create (fun i j -> if i = j then S.one else S.zero)

  31. let add mat1 mat2 =
  32. create (fun i j -> get_coef mat1 i j + get_coef mat2 i j)

  34. let mult mat1 mat2 =
  35. create @@ fun i j ->
  36. List.range ~stop:`inclusive 1 D.dim
  37. |> List.map ~f:(fun k -> get_coef mat1 i k * get_coef mat2 k j)
  38. |> List.reduce ~f:(+)
  39. |> Core.Std.Option.value ~default:S.zero
  40. end

Ceci dit, nous n'avons pas besoin des opérateurs sur les matrices pour l'algorithme de Floyd-Warshall. Nous avons simplement besoin d'une matrice et d'une algèbre de Kleene sur les coefficients de cette matrice. Nous pouvons donc écrire un autre foncteur pour obtenir l'algorithme (on l'appelle close car il calcule une fermeture transitive).

  1. module MakeFloydWarshall :
  2. functor (K : KleeneAlgebra) ->
  3. functor (M : Matrix with type coefficients = K.S.t) ->
  4. sig
  5. val close : M.t -> M.t
  6. end
  7. = functor (K : KleeneAlgebra) ->
  8. functor (M : Matrix with type coefficients = K.S.t) ->
  9. struct
  10. let (+) = K.S.add
  11. let ( * ) = K.S.mult

  13. let define succ_k mat_k i j =
  14. M.get_coef mat_k i j
  15. + M.get_coef mat_k i succ_k
  16. * K.star (M.get_coef mat_k succ_k succ_k)
  17. * M.get_coef mat_k succ_k j

  19. let close matrix =
  20. List.fold_left
  21. ~f:(fun mat_k succ_k ->
  22. M.create (define succ_k mat_k)
  23. )
  24. ~init:matrix
  25. (List.range ~stop:`inclusive 1 M.D.dim)

  27. end

Voilà pour la partie algorithmique : en présence de semi-anneaux ou d'algèbres de Kleene, on peut dériver des matrices avec MakeMatrix, puis un semi-anneau matriciel avec MakeMatrixSemiring ou un algorithme de Floyd-Warshall avec MakeFloydWarshall.

Essayons avec plusieurs algèbres de Kleene. Commençons par un calcul de distance dans un graphe orienté :

  1. module MinPlus =
  2. struct
  3. type t = Infty | Int of int
  4. let zero = Infty
  5. let one = Int 0
  6. let add i j = match i, j with
  7. | Int i, Int j -> Int (min i j)
  8. | Infty, _ -> j
  9. | _, Infty -> i
  10. let mult i j = match i, j with
  11. | Int i, Int j -> Int (i+j)
  12. | _ -> Infty
  13. let pp ppf = function
  14. | Int i -> Format.fprintf ppf "%3d" i
  15. | Infty -> Format.pp_print_string ppf "+oo"
  16. end

  18. module KleeneMinPlus =
  19. struct
  20. module S = MinPlus
  21. let star i = S.Int 0
  22. end

  24. module D8 = struct
  25. let dim = 8
  26. end

On utilise le semi-anneau $(\min,+)$ : on veut calculer le minimum de la somme des longueurs de chaque chemin. L'étoile est utilisée pour boucler sur un sommet, dans cette application, boucler sur un sommet ne coûte rien : cela veut dire faire du sur-place. On applique maintenant les foncteurs :

  1. module MatrixMinPlus8 = MakeMatrix(D8)(MinPlus)
  2. module SemiringMinPlus8 = MakeMatrixSemiring(MatrixMinPlus8)(MinPlus)
  3. module FWMinPlus8 = MakeFloydWarshall(KleeneMinPlus)(MatrixMinPlus8)

Testons en écrivant une fonction de génération aléatoire d'une matrice. Il suffit d'une fonction aléatoire pour les coefficients, et d'appeler MatrixMinPlus8.create avec.

  1. let random_MinPlus_coef p =
  2. if Random.float 1. < p then MinPlus.Int 1 else MinPlus.Infty
  3. let random_mat p =
  4. MatrixMinPlus8.create (fun i j -> random_MinPlus_coef p)

  6. let mat = random_mat 0.3
  7. let mat_close = FWMinPlus8.close mat

On installe le formatteur pour les matrices, puis on teste :

  1. # #install_printer MatrixMinPlus8.pp;;
  2. # let mat = random_mat 0.3;;
  3. val mat : MatrixMinPlus8.t =
  4. +oo 1 1 +oo +oo +oo +oo +oo
  5. +oo +oo 1 +oo +oo +oo +oo +oo
  6. 1 1 +oo +oo 1 +oo +oo +oo
  7. 1 +oo +oo +oo 1 +oo +oo 1
  8. 1 +oo +oo 1 +oo +oo +oo +oo
  9. +oo 1 +oo 1 +oo +oo +oo +oo
  10. +oo 1 +oo +oo +oo +oo +oo +oo
  11. +oo +oo +oo +oo +oo +oo +oo +oo
  12. # let mat_close = FWMinPlus8.close mat;;
  13. val mat_close : MatrixMinPlus8.t =
  14. 2 1 1 3 2 +oo +oo 4
  15. 2 2 1 3 2 +oo +oo 4
  16. 1 1 2 2 1 +oo +oo 3
  17. 1 2 2 2 1 +oo +oo 1
  18. 1 2 2 1 2 +oo +oo 2
  19. 2 1 2 1 2 +oo +oo 2
  20. 3 1 2 4 3 +oo +oo 5
  21. +oo +oo +oo +oo +oo +oo +oo +oo

Un dessin permet ensuite de vérifier que le résultat est bien la matrice des distances du graphe. Il serait néanmoins plus intéressant de connaître aussi les plus courts chemins. Pour cela, il suffit de changer de semi-anneau. Profitons-en pour généraliser l'algorithme pour le cas où les arêtes possèdent des longueurs arbitraires positives. Pour ne pas choisir entre des longueurs entières ou flottantes, on peut à nouveau introduire un foncteur :

  1. module MakeMinPlusPath = functor (SR : Semiring) ->
  2. struct
  3. module S =
  4. struct
  5. let (<=) x y = SR.add x y = x (* we need add to be a minimum *)

  7. type t =
  8. | NoPath
  9. | Path of SR.t * (int * int) list

  11. let zero = NoPath
  12. let one = Path (SR.one, [])

  14. let add p1 p2 =
  15. match p1, p2 with
  16. | Path (len1,_), Path (len2, _) when len1 <= len2 -> p1
  17. | Path _, Path _ -> p2
  18. | NoPath,_ -> p2
  19. | _,NoPath -> p1

  21. let mult p1 p2 =
  22. match p1, p2 with
  23. | Path (len1,p1), Path (len2,p2) -> Path (SR.mult len1 len2, p1 @ p2)
  24. | _ -> NoPath


  27. let pp_edge ppf (i,j) = Format.fprintf ppf "(%d,%d)" i j
  28. let pp_edges ppf list =
  29. let open Format in
  30. pp_print_list ~pp_sep:(fun ppf () -> fprintf ppf ";") pp_edge ppf list
  31. let pp ppf = function
  32. | NoPath -> Format.pp_print_string ppf "ø"
  33. | Path (len,list) ->
  34. Format.fprintf ppf "%a:[%a]" SR.pp len pp_edges list

  36. end

  38. let star p = S.one
  39. end

Pour l'instancier sur des longueurs flottantes, on crée un semi-anneau $(\min,+)$ des flottants, et on applique le foncteur MakeMinPlusPath.

  1. module FloatSR =
  2. struct
  3. type t = float
  4. let zero = infinity
  5. let one = 0.
  6. let add = min
  7. let mult = (+.)
  8. let pp = Format.pp_print_float
  9. end

  11. module MinPlusPath = MakeMinPlusPath(FloatSR)

Nous sommes prêt à produire les matrices et l'algorithme de Floyd-Warshall :

  1. module D5 = struct let dim = 5 end
  2. module MatrixMinPlusPath5 = MakeMatrix(D5)(MinPlusPath.S)
  3. module SemiringMinPlusPath5 =
  4. MakeMatrixSemiring(MatrixMinPlusPath5)(MinPlusPath.S)
  5. module FWMinPlusPath5 = MakeFloydWarshall(MinPlusPath)(MatrixMinPlusPath5)

De nouveau, on ajoute un générateur aléatoire et on teste sur un exemple.

  1. let random_MinPlusPath_coef p i j =
  2. if i = j then
  3. MinPlusPath.S.(Path (0.,[]))
  4. else if Random.float 1. < p then
  5. MinPlusPath.S.(Path (Random.float 10., [(i,j)]))
  6. else
  7. MinPlusPath.S.NoPath

  9. let random_float_mat p =
  10. MatrixMinPlusPath5.create (random_MinPlusPath_coef p)


  13. (* in toplevel: *)
  14. # #install_printer MatrixMinPlusPath5.pp;;
  15. # let mat = random_float_mat 0.4;;
  16. val mat : MatrixMinPlusPath5.t =
  17. 0.:[] ø ø 0.819736241165:[(1,4)] ø
  18. 0.407159120634:[(2,1)] 0.:[] ø ø 5.61633446903:[(2,5)]
  19. 6.9831845109:[(3,1)] ø 0.:[] ø ø
  20. ø 2.61599931405:[(4,2)] ø 0.:[] ø
  21. ø ø 2.13522490529:[(5,3)] ø 0.:[]
  22. # let mat_close = FWMinPlusPath5.close mat;;
  23. val mat_close : MatrixMinPlusPath5.t =
  24. 0.:[]
  25. 3.43573555521:[(1,4);(4,2)]
  26. 11.1872949295:[(1,4);(4,2);(2,5);(5,3)]
  27. 0.819736241165:[(1,4)]
  28. 9.05207002424:[(1,4);(4,2);(2,5)]

  30. 0.407159120634:[(2,1)]
  31. 0.:[]
  32. 7.75155937432:[(2,5);(5,3)]
  33. 1.2268953618:[(2,1);(1,4)]
  34. 5.61633446903:[(2,5)]

  36. 6.9831845109:[(3,1)]
  37. 10.4189200661:[(3,1);(1,4);(4,2)]
  38. 0.:[]
  39. 7.80292075206:[(3,1);(1,4)]
  40. 16.0352545351:[(3,1);(1,4);(4,2);(2,5)]

  42. 3.02315843468:[(4,2);(2,1)]
  43. 2.61599931405:[(4,2)]
  44. 10.3675586884:[(4,2);(2,5);(5,3)]
  45. 0.:[]
  46. 8.23233378308:[(4,2);(2,5)]

  48. 9.11840941618:[(5,3);(3,1)]
  49. 12.5541449714:[(5,3);(3,1);(1,4);(4,2)]
  50. 2.13522490529:[(5,3)]
  51. 9.93814565735:[(5,3);(3,1);(1,4)]
  52. 0.:[]

On termine avec un exemple sensiblement différent : construire l'expression régulière reconnue par un automate fini. Pour cela, il suffit d'utiliser Floyd-Warshall sur l'algèbre de Kleene usuelle sur les langages réguliers. Cette application a un problème : les expressions régulières générées peuvent être extrêmement longues. Pour éviter cela, nous allons regarder des automates tout petits et utiliser des règles de simplification sur les expressions régulières. Cela rend la définition des expressions régulières assez complexes. Par ailleurs, on ne veut pas imposer le type des lettres de l'alphabet, donc nous allons encore ajouter un foncteur !

  1. module type Alphabet =
  2. sig
  3. type letter
  4. val pp : Format.formatter -> letter -> unit
  5. end

On ajoute quelques fonctions utilitaires puis le foncteur pour créer le type des expressions régulières sur un alphabet :


  2. type 'elt at_least_two_elts_list =
  3. ('elt * 'elt list * 'elt)

  5. type 'elt list_ends =
  6. | No_ends
  7. | Single_end of 'elt
  8. | Double_ends of 'elt * 'elt list * 'elt

  10. let rec insert_ends head tail =
  11. match observe_list_ends tail with
  12. | No_ends -> Single_end head
  13. | Single_end last -> Double_ends (head,[],last)
  14. | Double_ends (snd,middle,last) -> Double_ends (head,snd::middle,last)
  15. and observe_list_ends = function
  16. | [] -> No_ends
  17. | head::tail -> insert_ends head tail



  21. module MakeRegexp :
  22. functor (A : Alphabet) ->
  23. sig
  24. type regexp =
  25. | Empty
  26. | Epsilon
  27. | Letter of A.letter
  28. | Or of regexp at_least_two_elts_list
  29. | Concat of regexp at_least_two_elts_list
  30. | Star of regexp
  31. include KleeneAlgebra with type S.t = regexp
  32. end
  33. = functor (A : Alphabet) ->
  34. struct

  36. type regexp =
  37. | Empty
  38. | Epsilon
  39. | Letter of A.letter
  40. | Or of regexp at_least_two_elts_list
  41. | Concat of regexp at_least_two_elts_list
  42. | Star of regexp

  44. let zero = Empty
  45. let one = Epsilon


  48. let to_or list =
  49. match observe_list_ends list with
  50. | No_ends -> Empty
  51. | Single_end elt -> elt
  52. | Double_ends (head,middle,last) -> Or (head, middle, last)
  53. let of_triple (head,middle,last) =
  54. head :: middle @ [last]

  56. let to_concat list =
  57. match observe_list_ends list with
  58. | No_ends -> Epsilon
  59. | Single_end elt -> elt
  60. | Double_ends (head,middle,last) -> Concat (head,middle,last)

  62. let merge = List.merge ~cmp:compare

  64. let rec contains regexp1 regexp2 =
  65. regexp1 = regexp2 ||
  66. match regexp1, regexp2 with
  67. | _, Star e when contains regexp1 e -> true
  68. | Star e1, Star e2 -> contains e1 regexp2
  69. | _, Or (head,middle,tail) ->
  70. List.exists ~f:(contains regexp1) (head::tail::middle)
  71. | don't_know -> false

  73. let rec insert e = function
  74. | head::tail when contains head e -> e::tail
  75. | head::tail as list when contains e head -> list
  76. | head::tail when head < e -> head :: insert e tail
  77. | list -> e::list

  79. let rec add_concat ((head1,mid1,tail1) as re1) ((head2,mid2,tail2) as re2) =
  80. if head1 = head2 then
  81. mult head1 (add (to_concat (mid1@[tail1])) (to_concat (mid2@[tail2])))
  82. else if tail1 = tail2 then
  83. mult (add (to_concat (head1::mid1)) (to_concat (head2::mid2))) tail1
  84. else Or (Concat re1,[],Concat re2)

  86. and add e1 e2 = match e1, e2 with
  87. | Empty, e
  88. | e, Empty -> e
  89. | Epsilon, Star e
  90. | Star e, Epsilon -> Star e
  91. | Epsilon, Concat (Star e1,[],e2) when e1 = e2 -> Star e1
  92. | Epsilon, Concat (e1,[],Star e2) when e1 = e2 -> Star e1
  93. | Concat (e1,[],Star e2), Epsilon when e1 = e2 -> Star e1
  94. | Concat (Star e2,[],e1), Epsilon when e1 = e2 -> Star e1
  95. | e, Concat (head,middle,last) when e = head ->
  96. mult e (add Epsilon (to_concat (middle@[last])))
  97. | e, Concat (head,middle,last) when e = last ->
  98. mult (add Epsilon (to_concat (head::middle))) e
  99. | Concat (head,middle,last), e when e = head ->
  100. mult e (add Epsilon (to_concat (middle@[last])))
  101. | Concat (head,middle,last), e when e = last ->
  102. mult (add Epsilon (to_concat (head::middle))) e
  103. | e1, e2 when e1 = e2 -> e1
  104. | Or regexps1, Or regexps2 ->
  105. to_or (merge (of_triple regexps1) (of_triple regexps2))
  106. | e, Or regexps
  107. | Or regexps, e -> to_or (insert e (of_triple regexps))
  108. | Concat regexps1, Concat regexps2 -> add_concat regexps1 regexps2
  109. | _, _ -> Or (e1,[],e2)

  111. and mult e1 e2 = match e1, e2 with
  112. | Epsilon, e
  113. | e, Epsilon -> e
  114. | Empty, _
  115. | _, Empty -> Empty
  116. | Concat (head1,mid1,last1), Concat (head2,mid2,last2) ->
  117. Concat (head1,mid1 @ [last1; head2] @ mid2,last2)
  118. | Concat (head,mid,last), e -> Concat (head,mid@[last],e)
  119. | Star e1, Star e2 when contains e1 e2 -> Star e2
  120. | Star e1, Star e2 when contains e2 e1 -> Star e1
  121. | _ -> Concat (e1,[],e2)

  123. and star = function
  124. | Empty -> Epsilon
  125. | Epsilon -> Epsilon
  126. | e -> Star e


  129. let rec pp_re ppf = function
  130. | Or regexps ->
  131. Format.pp_print_list
  132. ~pp_sep:(fun ppf () -> Format.fprintf ppf "@,|")
  133. pp_re
  134. ppf
  135. (of_triple regexps)
  136. | e -> pp_term ppf e
  137. and pp_term ppf = function
  138. | Concat regexps ->
  139. Format.pp_print_list
  140. pp_term
  141. ppf
  142. (of_triple regexps)
  143. | e -> pp_factor ppf e
  144. and pp_factor ppf = function
  145. | Empty -> Format.pp_print_string ppf "ø"
  146. | Epsilon -> Format.pp_print_string ppf "e"
  147. | Letter a -> A.pp ppf a
  148. | Star e -> Format.fprintf ppf "@[%a*@]" pp_factor e
  149. | e -> Format.fprintf ppf "@[(%a)@]" pp_re e

  151. module S = struct
  152. type t = regexp
  153. let zero = zero
  154. let one = one
  155. let add = add
  156. let mult = mult
  157. let pp = pp_re
  158. end
  159. end

Maintenant, on utilise les différents foncteurs pour obtenir notre instance de l'algorithme de Floyd-Warshall, appliqué aux expressions régulières sur un alphabet à deux lettres :

  1. module D2 = struct
  2. let dim = 2
  3. end

  5. module AB = struct
  6. type letter = A | B
  7. let pp ppf = function
  8. | A -> Format.pp_print_string ppf "a"
  9. | B -> Format.pp_print_string ppf "b"
  10. end

  12. module ReAB = MakeRegexp(AB)

  14. module Automata = MakeMatrix(D2)(ReAB.S)
  15. module FWAutomata = MakeFloydWarshall(ReAB)(Automata)

On crée un automate, et on teste :

  1. # #install_printer Automata.pp;;
  2. # let aut1 =
  3. Automata.create
  4. (fun i j -> match i,j with
  5. | 1,1 -> ReAB.Letter AB.A
  6. | 1,2 -> ReAB.Letter AB.B
  7. | 2,1 -> ReAB.Empty
  8. | 2,2 -> ReAB.(S.add (Letter AB.A) (Letter AB.B))
  9. | _ -> ReAB.Empty
  10. );;
  11. val aut1 : Automata.t =
  12. a b
  13. ø a|b
  14. # let aut2 = FWAutomata.close aut1;;
  15. val aut2 : Automata.t =
  16. aa* a*b(a|b)*
  17. ø (a|b)(a|b)*

Avec des automates aléatoires :

  1. let random_arc i j =
  2. match Random.int 5 with
  3. | 0 -> ReAB.Letter AB.A
  4. | 1 -> ReAB.Letter AB.B
  5. | 2 -> ReAB.S.add (ReAB.Letter AB.A) (ReAB.Letter AB.B)
  6. | 3 -> ReAB.Epsilon
  7. | _ -> ReAB.Empty
  8. let random_automaton () =
  9. Automata.create random_arc


  12. (* In toplevel: *)
  13. # let aut3 = random_automaton ();;
  14. val aut3 : Automata.t =
  15. e ø
  16. b a
  17. # let aut4 = FWAutomata.close aut3;;
  18. val aut4 : Automata.t =
  19. e ø
  20. a*b aa*
  21. # let aut5 = random_automaton ();;
  22. val aut5 : Automata.t =
  23. e a|b
  24. a|b b
  25. # let aut6 = FWAutomata.close aut5;;
  26. val aut6 : Automata.t =
  27. e|(a|b)(b|(a|b)(a|b))*(a|b) (a|b)(b|(a|b)(a|b))*
  28. (b|(a|b)(a|b))*(a|b) (b|(a|b)(a|b))(b|(a|b)(a|b))*

Impeccable: chaque coefficient $c_{i,j}$ est une expression régulière pour le language des mots permettant d'aller de l'état $i$ vers l'état $j$, comme attendu.

Retour au sommaire.