Probleme – Berry-Sethi, de l'induction au programme

1. Les équations. Elles suivent la définition inductive des langages réguliers : un cas par constructeur.

$$\begin{array}{lll}\mathrm{nul}(\varnothing )=\text{faux}& \mathrm{nul}(\epsilon )=\text{vrai}& \mathrm{nul}(x)=\text{faux}\\ \mathrm{nul}(e_1|e_2)=\mathrm{nul}(e_1)\vee \mathrm{nul}(e_2)& \mathrm{nul}(e_1{e}_2)=\mathrm{nul}(e_1)\wedge \mathrm{nul}(e_2)& \mathrm{nul}(e^{\ast })=\text{vrai}\end{array}$$

$$\begin{array}{ll}P(\varnothing )=P(\epsilon )=\varnothing ,& P(x)=\{x\}\\ P(e_1|e_2)=P(e_1)\cup P(e_2),& P(e^{\ast })=P(e)\\ P(e_1{e}_2)=P(e_1)\cup P(e_2)\text{ si }\mathrm{nul}(e_1),P(e_1)\text{ sinon}& \end{array}$$

$D$ est symétrique : $D(e_1{e}_2)=D(e_1)\cup D(e_2)$ si $\mathrm{nul}(e_2)$, et $D(e_2)$ sinon. Enfin

$$F(e_1{e}_2)=F(e_1)\cup F(e_2)\cup D(e_1)\cdot P(e_2),F(e^{\ast })=F(e)\cup D(e)\cdot P(e),$$

où $X\cdot Y$ note l'ensemble des couples. Les deux dernières lignes portent tout : un facteur de deux lettres naît soit à l'intérieur d'un sous-terme, soit à la jonction — dernière lettre du gauche suivie de première lettre du droit. L'étoile recolle sa propre fin sur son propre début, ce qui est exactement ce qu'elle autorise.

2. Le programme.

type expr =
  | Vide
  | Eps
  | Lettre of char * int          (* la lettre, et son NUMERO d'occurrence *)
  | Union of expr * expr
  | Concat of expr * expr
  | Etoile of expr

(* Numerote les occurrences de lettres : rend une expression LINEAIRE.
   Precondition : aucune. Postcondition : deux occurrences distinctes
   portent deux numeros distincts. Complexite : Theta(taille de e). *)
let linearise e =
  let n = ref 0 in
  let rec aux = function
    | Vide -> Vide
    | Eps -> Eps
    | Lettre (c, _) -> incr n; Lettre (c, !n)
    | Union (e1, e2) -> let a = aux e1 in Union (a, aux e2)
    | Concat (e1, e2) -> let a = aux e1 in Concat (a, aux e2)
    | Etoile e1 -> Etoile (aux e1)
  in aux e

let rec nul = function
  | Vide | Lettre _ -> false
  | Eps | Etoile _ -> true
  | Union (e1, e2) -> nul e1 || nul e2
  | Concat (e1, e2) -> nul e1 && nul e2

let rec prem = function
  | Vide | Eps -> []
  | Lettre (c, i) -> [(c, i)]
  | Union (e1, e2) -> union (prem e1) (prem e2)
  | Concat (e1, e2) -> if nul e1 then union (prem e1) (prem e2) else prem e1
  | Etoile e1 -> prem e1

let rec dern = function
  | Vide | Eps -> []
  | Lettre (c, i) -> [(c, i)]
  | Union (e1, e2) -> union (dern e1) (dern e2)
  | Concat (e1, e2) -> if nul e2 then union (dern e1) (dern e2) else dern e2
  | Etoile e1 -> dern e1

let rec fact = function
  | Vide | Eps | Lettre _ -> []
  | Union (e1, e2) -> union (fact e1) (fact e2)
  | Concat (e1, e2) ->
      union (union (fact e1) (fact e2)) (produit (dern e1) (prem e2))
  | Etoile e1 -> union (fact e1) (produit (dern e1) (prem e1))

Les ensembles sont des listes triées sans doublon, avec deux opérations de service :

let rec insere x = function
  | [] -> [x]
  | t :: q when x = t -> t :: q
  | t :: q when x < t -> x :: t :: q
  | t :: q -> t :: insere x q

let union l1 l2 = List.fold_left (fun acc x -> insere x acc) l2 l1
let produit l1 l2 =
  List.concat_map (fun x -> List.map (fun y -> (x, y)) l2) l1

Chaque fonction est la transcription littérale de son équation — c'est ce que permet une définition par induction, et c'est le lien avec le chapitre chap:induction.

L'automate s'en déduit sans travail :

type automate = {
  nb : int;                                  (* nombre d'etats, 0 compris *)
  trans : (int * char * int) list;           (* (depart, lettre, arrivee)  *)
  acceptants : int list;
}

let glushkov e =
  let el = linearise e in
  let rec compte = function
    | Vide | Eps -> 0
    | Lettre _ -> 1
    | Union (a, b) | Concat (a, b) -> compte a + compte b
    | Etoile a -> compte a
  in
  { nb = compte el + 1;
    trans = List.map (fun (c, i) -> (0, c, i)) (prem el)
            @ List.map (fun ((_, i), (d, j)) -> (i, d, j)) (fact el);
    acceptants = (if nul el then [0] else []) @ List.map snd (dern el) }

3. L'exécution. Sur $(a|b{)}^{\ast }abb$, le programme rend

  nul = false
  P = {a1, a3, b2}
  D = {b5}
  F = {a1a1, a1a3, a1b2, a3b4, b2a1, b2a3, b2b2, b4b5}
  automate : 6 etats, 11 transitions, acceptants {5}
  2047 mots essayes (longueur <= 10), 0 desaccord(s)

La dernière ligne est la vérification : l'automate a été exécuté par simulation non déterministe sur tous les mots de longueur au plus $10$, et sa réponse comparée au prédicat « se termine par abb ». Aucun désaccord.

4. Les deux propriétés.

Le nombre d'états. Les états sont, par construction, l'état initial et les lettres numérotées — une par occurrence dans l'expression. Il y en a donc exactement $|\text{lettres}|+1$, quel que soit l'emboîtement des étoiles. C'est la propriété remarquable de Glushkov : la taille de l'automate ne dépend que du nombre de lettres écrites, jamais de la structure.

Aucune transition spontanée. Une transition n'est créée que dans deux cas : depuis l'initial vers une lettre de $P$, et de $x$ vers $y$ pour $xy\in F$. Dans les deux cas la transition porte la lettre de son état d'arrivée, et cette lettre est un élément de $\Sigma$. Il n'y a donc rien qui puisse être spontané. C'est le gain de la construction sur celle de Thompson, qui en produit beaucoup.

Un corollaire immédiat : toutes les transitions entrant dans un état portent la même lettre — celle de cet état. L'automate est donc « déterministe en arrière », même s'il ne l'est pas en avant.

La complexité. Les fonctions $P$ et $D$ rendent des ensembles de taille au plus $n$ (le nombre de lettres) et se calculent en $O(n^2)$ avec des listes triées. $F$ rend au plus $n^2$ couples, et le produit $D(e_1)\cdot P(e_2)$ les fabrique en $O(n^2)$. L'ensemble est donc en $O(n^2)$ en temps et en place, où $n$ est le nombre de lettres de l'expression, mesuré ici : $5$ lettres, $8$ facteurs, $11$ transitions.