Types enregistrement

---

Ce sont des types qui permettent d'associer plusieurs objets au sein d'une même variable. Pour les déclarer, on utilise la syntaxe suivante :

type nom_enregistrement = {nom1: type1; nom2: type2; nom3: type3};;

Pour créer une variable de type nom_enregistrement, on utilise la syntaxe suivante :

let val_enregistrement = {nom1 = valeur1; nom2 = valeur2; nom3 = valeur3};;

On peut ensuite accéder aux valeurs des champs de la manière suivante :

val_enregistrement.nom1 (*ceci vaut valeur1*)

Il est possible de rendre un champs d'un enregistrement mutable (sa valeur peut être modifiée) en le déclarant avec mutable nom1: typ1 au lieu de simplement nom1: type1.

Le type array en OCaml

---

En plus des listes, le langage OCaml a un type array. Il s'agit de tableau indexables (donc on peut prendre directement l'élément n°i directement), mutables (on peut changer la valeur de l'élément n°i), mais non redimensionnables : on les déclare avec une taille, et ils ne changent jamais de taille !

Comme les listes, le type d'un tableau d'entiers s'écrit int array, de booléens bool array, etc.

On les utilise de la manière suivante :

• création :
  • let tab = Array.make n x créé un tableau tab de longueur n rempli de x
  • let tab = [|1; 2; 3; 10|] créé un tableau contenant 1, 2, 3 et 10.
• accès à un élément
  • tab.(i) lis l'élément i.
• modification
  • tab.(i) <- x écrit x dans la case i de tab. Cette opération renvoie unit, on la succède donc en général d'un simple ;.

Question 1

---

Complétez le type dfa (pour "deterministic finite automaton") correspondant à un automate déterministe.

Question 2

---

Dans une variable, définir l'automate déterministe représenté par ce dessin :

Dessiner un automate

---

Le site fournit une fonction dessine aut, qui affiche un automate. Testez-la sur l'automate de la question précédente !

Question 3

---

Ecrivez une fonction delta_f de type dfa -> int -> lettre -> int qui correspond à la fonction .

Question 4

---

Ecrivez une fonction delta_star de type dfa -> int -> mot -> int qui correspond à la fonction .

Question 5

---

Ecrivez une fonction accepte de type dfa -> mot -> bool qui renvoie true si l'automate accepte le mot, false sinon. Testez votre fonction sur quelques mots exemples.

Question 6

---

Dessinez l'automate correspondant au motif aba, puis détaillez le chemin parcouru en lisant le mot aabaabba. Quand est-ce que l'automate est dans un état acceptant ?

Question 7

---

Ecrivez une fonction prefixe m i de type mot -> int -> mot qui renvoie le préfixe de taille i de m.

Question 8

---

Ecrivez une fonction suffixe_max p m de type mot -> mot -> int qui calcule la taille du plus grand suffixe de p qui est aussi préfixe de m. Vous pouvez vous aider d'une fonction auxiliaire est_prefixe p m.

Question 9

---

Ecrivez une fonction sigma m i x qui calcule la valeur de pour le mot m.

Question 10

---

Enfin, écrivez une fonction automate_motif m de type mot -> dfa qui calcule l'automate des motifs pour un mot m.

Question 11

---

On prend comme exemple le mot aba. Votre automate accepte-il aba ? abbababa ? abaaa ?

Question 12

---

Ecrivez une fonction recherche automate texte de type dfa -> mot -> int list qui renvoie une liste de tous les tels que l'automate accepte . Testez-la sur l'automate de la question précédente et le texte suivant :

Question 13

---

Quelle est la complexité de la création de l'automate ? Et celle de la recherche dans un texte une fois l'automate créé ?

Question 14

---

Ecrivez une fonction union a1 a2 de type dfa -> dfa -> dfa qui renvoie l'automate union de a1 et a2.

Indication : ici, on a que des automates deterministes. L'idée est de faire l'union et la determinisation en une seule étape.

Les modules Queue et Hashtbl

---

OCaml fournit des files et des tables de hachage mutables : les fonctions qui les modifient renvoient unit.

Files (module Queue), de type 'a Queue.t :

• let f = Queue.create () crée une file vide ;
• Queue.add x f ajoute x à la fin de la file f ;
• Queue.pop f retire l'élément en tête de la file et le renvoie (exception Queue.Empty si la file est vide) ;
• Queue.is_empty f teste si la file est vide, Queue.length f renvoie son nombre d'éléments.

Tables de hachage (module Hashtbl), de type ('a, 'b) Hashtbl.t (clés de type 'a, valeurs de type 'b) :

• let t = Hashtbl.create 16 crée une table vide (16 est une taille initiale indicative, la table s'agrandit toute seule) ;
• Hashtbl.replace t k v associe la valeur v à la clé k (en remplaçant l'ancienne valeur s'il y en avait une) ;
• Hashtbl.find t k renvoie la valeur associée à k (exception Not_found si k n'est pas dans la table) ;
• Hashtbl.find_opt t k renvoie Some v si k est associée à v, None sinon ;
• Hashtbl.mem t k teste si la clé k est dans la table ;
• Hashtbl.remove t k supprime la clé k ;
• Hashtbl.length t renvoie le nombre de clés.

N'importe quelle valeur peut servir de clé, par exemple un couple d'entiers : Hashtbl.replace t (2, 3) 7.

Attention : Hashtbl.add t k v existe aussi, mais il masque l'ancienne valeur de k au lieu de la remplacer (elle réapparaît après un Hashtbl.remove).

Question 15

---

Dessinez l'automate union de la question précédente : beaucoup de ses états ne sont pas accessibles depuis l'état initial, ils ne servent à rien. Ecrivez une fonction union_accessible a1 a2, de type dfa -> dfa -> dfa, qui ne construit que les états accessibles de l'automate union.

Indication : faites un parcours (en largeur, par exemple) depuis le couple d'états initiaux, en numérotant les couples dans l'ordre où on les découvre. Une file (Queue) contient les couples à traiter, et une table de hachage (Hashtbl) permet de retrouver le numéro d'un couple déjà vu.