(* Exercice de colles d'informatique *)

(* Titre : Implémentation du lemme de l'étoile en OCaml *)

(* On se propose d'implémenter le lemme de l'étoile en OCaml. En effet,
   étant fixés un automate A et un mot w dans le langage de l'automate dont
   la longueur est supérieure au nombre d'états de l'automate, le lemme de
   l'étoile nous donne l'existence de trois mots, x y et z vérifiant des
   propriétés. Dans cet exercice on calcule trois tels mots x, y et z. *)

(** Un automate non déterministe *)
type automate_nd = {
  init  : int list;             (* les états initiaux *)
  trans : int list array array; (* la table des transitions *)
  fin   : int list              (* les états finaux *)
}

(* les états sont les entiers de l'intervalle [|0, n-1|] où n est la taille
   du tableau trans. init est la liste des états initiaux, fin est la liste
   des états finaux. trans est une matrice représentant les transitions de
   l'automate : dans sa ligne d'indice i elle contient un tableau dont la
   taille est la taille de l'alphabet, dans sa l-ème case elle contient les
   états j tels que (i, l, j) est une transition de l'automate. *)

(* Ci-dessous un automate exemple : il a un unique état initial 0, deux
   états finaux 2 et 3. Depuis l'état 0, on peut atteindre l'état 0 en
   lisant a, mais aussi l'état 1. L'état 2 n'a pas de transition sortante
   étiquettées par la lettre a mais a une transition étiquettée par c vers
   l'état 3. *)

(* Automate exemple *)
let (auto_2: automate_nd) = {
  init = [0];
  trans =
(* lettres |   a   |   b   |   c   |*)
       [| [| [0; 1]; [0; 4]; [3]   |];    (* état 0 *)
          [| [2]   ; [2]   ; [3]   |];    (* état 1 *)
          [| []    ; []    ; [3]   |];    (* état 2 *)
          [| [3]   ; [3]   ; [3]   |];    (* état 3 *)
          [| [4]   ; []    ; []    |]     (* état 4 *)
       |];
  fin = [2; 3]
}

(** Calcule la lettre associée à l'entier [i]. *)
let lettre_of_int (i: int): char =
  char_of_int (97 + i)

(** Calcule l'entier associée à une lettre [c]. *)
let int_of_letter (c: char): int =
  (int_of_char c) - 97

(* Q1. Écrire une fonction trouve_xyz prenant en paramètres un automate a
   et un mot w que l'on supposera être dans le langage de l'automate a et
   de longueur supérieure au nombre d'états de l'automate et retournant un
   triplet de mots x, y, z vérifiant les contraintes du lemme de
   l'étoile.

   Quelle est la complexité de l'algorithme mis en place ? *)

(* Q2. Écrire une fonction trouve_mot prenant en paramètre un automate a et
   retournant, s'il existe, un mot w dans le langage de l'automate et de
   longueur supérieur au nombre d'états de l'automate.

   Quelle est la complexité de l'algorithme mis en place ?  *)