TP 3 : Algorithme de Berry-Sethi

Fonctions utilitaires

On utilisera le type suivant d'expression régulière :

type 'a regexp =
    | Vide | Epsilon | L of 'a
    | Union of 'a regexp * 'a regexp
    | Concat of 'a regexp * 'a regexp
    | Etoile of 'a regexp

1. Écrire une fonction fusion : 'a list -> 'a list -> 'a list telle que, si u et v sont strictement croissantes, fusion u v est une liste strictement croissante contenant tous les éléments de u et de v.

fusion [1;3;5] [2;3;4;6];;
- : int list = [1; 2; 3; 4; 5; 6]

2. Écrire une fonction est_vide : 'a regexp -> bool déterminant si le langage d'une expression régulière est vide.

est_vide (Concat(L 1, Vide));;
- : bool = true
est_vide (Etoile Vide);;
- : bool = false

3. Écrire une fonction a_epsilon : 'a regexp -> bool déterminant si le langage décrit par une expression régulière contient $\epsilon$.

a_epsilon (Concat(L 1, Epsilon));;
- : bool = false
a_epsilon (Etoile (L 1));;
- : bool = true

4. Donner la complexité des fonctions précédentes.

Calcul des ensembles $P(L)$, $S(L)$, $F(L)$

Revoir si besoin dans le cours les définitions des ensembles $P(L)$, $S(L)$, $F(L)$.

5. Écrire sur papier des équations de récurrence pour les ensembles $P(L)$, $S(L)$, $F(L)$.

6. Écrire une fonction p : 'a regexp -> 'a list renvoyant l'ensemble $P(L)$ d'une expression régulière, sous forme de liste strictement croissante. Tester sur les exemples suivants :

p (Union (Concat(L 1, L 3), L 2));;
- : int list = [1; 2]
p (Concat (L 1, Vide));;
- : int list = []
p (Concat (Concat(L 1, L 3), L 2));;
- : int list = [1]
p (Concat (Epsilon, L 2));;
- : int list = [2]

7. Écrire une fonction s : 'a regexp -> 'a list renvoyant l'ensemble $S(L)$ d'une expression régulière, sous forme de liste strictement croissante.

s (Union (L 2, Concat(L 1, L 3)));;
- : int list = [2; 3]
s (Concat (Vide, L 1));;
- : int list = []
s (Concat (Concat(L 1, L 3), L 2));;
- : int list = [2]
s (Concat (L 2, Epsilon));;
- : int list = [2]

8. Écrire une fonction produit : 'a list -> 'b list -> ('a * 'b) list renvoyant le produit cartésien de deux listes. L'ordre des éléments de la liste de retour n'importe pas.

produit [1;2] [3;4];;
- : (int * int) list = [(1, 3); (1, 4); (2, 3); (2, 4)]

9. Écrire une fonction f : 'a regexp -> ('a * 'a) list renvoyant l'ensemble $F(L)$ d'une expression régulière, sous forme de liste de couples dans un ordre quelconque.

f (Concat (Concat(L 1, L 3), L 2));;
- : (int * int) list = [(1, 3); (3, 2)]

Linéarisation d'une expression régulière

10. Écrire une fonction n_lettres : 'a regexp -> int renvoyant le nombre de lettres d'une expression régulière. Par exemple, n_lettres (Union (Concat (L 'a', L 'b'), Etoile (L 'a'))) doit renvoyer 3.

11. Écrire une fonction lineariser : 'a regexp -> ('a * int) regexp renvoyant la linéarisation d'une expression régulière, où la $i$ème occurrence d'une lettre $a$ est remplacée par $(a, i)$.

lineariser (Union (Concat (L 'a', L 'b'), Etoile (L 'a')));;
- : (char * int) regexp = Union (Concat (L ('a', 1), L ('b', 2)), Etoile (L ('a', 3)))

Automate de Glushkov

L'automate de Glushkov n'est pas forcément déterministe. On utilisera le type suivant, où les occurrences de lettres sont numérotées à partir de $1$ et $0$ est l'état initial :

type 'a automate = {
    delta : 'a list array array;
    finaux : bool array;
}

Ainsi, si a est un automate, a.delta.(i).(j) est la liste des lettres portées par les transitions de l'état i vers l'état j. a.finaux.(i) est vrai si l'état i est final.

12. Écrire une fonction glushkov : 'a regexp -> 'a automate renvoyant l'automate de Glushkov d'une expression régulière.

13. Définir une expression régulière dont le langage est l'ensemble des mots sur $\{a, b\}$ ayant un nombre pair de $a$ et vérifier l'automate de Glushkov obtenu en le dessinant à la main.