TD 5 - Construction d'automates déterministes à partir d'expressions régulières

Dans ce TD, on étudie une méthode de construction directe d'un automate fini déterministe à partir d'une expression régulière. Il s'agit d'un algorithme efficace, utilisé notamment dans ocamllex.

L'idée de départ est la suivante : si un automate fini reconnaît le langage correspondant à l'expression régulière r, alors à toute lettre d'un mot reconnu on peut faire correspondre une occurrence d'une lettre apparaissant dans r. Pour distinguer les différentes occurrences d'une même lettre dans r, on va les indexer par des entiers. Considérons par exemple l'expression régulière (a|b)* a (a|b), qui définit les mots sur l'alphabet {a,b} dont l'avant-dernière lettre est un a. Si on indice les caractères, on obtient

(a₁|b₁)* a₂ (a₃|b₂)

Si on considère le mot aabaab, alors il correspond à l'expression régulière de la manière suivante

a₁a₁b₁a₁a₂b₂

L'idée est alors de construire un automate dont les états sont des ensembles de lettres indexées, correspondant aux occurrences qui peuvent être lues à un instant. Ainsi l'état initial contient les premières lettres possibles des mots reconnus. Dans notre exemple, il s'agit de a₁,b₁,a₂. Pour construire les transitions, il suffit de calculer, pour chaque occurrence d'une lettre, l'ensemble des occurrences qui peuvent la suivre. Dans notre exemple, si on vient de lire a₁, alors les caractères possibles suivants sont a₁,b₁,a₂ ; si on vient de lire a₂, alors ce sont a₃,b₂.

Question 1. Nullité d'une expression régulière

On considère le type Caml suivant pour les expressions régulières dont les lettres sont indexées par des entiers (type ichar).

type ichar = char * int

type regexp = 
  | Epsilon
  | Character of ichar
  | Union of regexp * regexp
  | Concat of regexp * regexp
  | Star of regexp

Écrire une fonction

val null : regexp -> bool

qui détermine si epsilon (le mot vide) appartient au langage reconnu par une expression régulière.

Question 2. Les premiers et les derniers

Pour représenter les ensembles de lettres indexées, on se donne le type Caml suivant :

module Cset = Set.Make(struct type t = ichar let compare = compare end)

Écrire une fonction

val first : regexp -> Cset.t

qui calcule l'ensemble des premières lettres des mots reconnus par une expression régulière. (Il faut se servir de null.)

De même, écrire une fonction

val last : regexp -> Cset.t

qui calcule l'ensemble des dernières lettres des mots reconnus.

Question 3. Les suivants

En se servant des fonctions first et last, écrire une fonction

val follow : ichar -> regexp -> Cset.t

qui calcule l'ensemble des lettres qui peuvent suivre une lettre donnée dans l'ensemble des mots reconnus.

On notera que la lettre d appartient à l'ensemble follow c r si et seulement si

soit il existe une sous-expression de r de la forme r₁r₂ avec d élément de first r₂ et c élément de last r₁ ;
soit il existe une sous-expression de r de la forme r₁* avec d élément de first r₁ et c élément de last r₁.

Question 4. Construction de l'automate

Pour construire l'automate déterministe correspondant à une expression régulière r, on procède ainsi :

on ajoute un nouveau caractère # à la fin de r ;
l'état de départ est l'ensemble first r ;
on a une transition de l'état q vers l'état q' à la lecture du caractère c (il s'agit là d'une lettre non indexée) si q' est l'union de tous les follow ci r pour tous les éléments ci de q ;
les états d'acceptation sont ceux qui contiennent le caractère #.

Écrire une fonction

val next_state : regexp -> Cset.t -> char -> Cset.t

qui calcule l'état résultant d'une transition.

Pour représenter l'automate fini, on se donne le type Caml suivant :

module Cmap = Map.Make(Char)
module Smap = Map.Make(Cset)

type state = Cset.t

type autom = {
  start : state;
  trans : state Cmap.t Smap.t
}

On peut choisir de représenter ainsi le caractère # :

let eof = ('#', -1)

Écrire une fonction

val make_dfa : regexp -> autom

qui construit l'automate correspondant à une expression régulière. L'idée est de construire les états par nécessité, en partant de l'état initial. On pourra par exemple adopter l'approche suivante :

let make_dfa r =
  let r = Concat (r, Character eof) in
  (* transitions en cours de construction *)
  let trans = ref Smap.empty in
  let rec transitions q =
    (* la fonction transitions construit toutes les transitions de l'état q,
       si c'est la première fois que q est visité *)
    ...
  in
  let q0 = first r in
  transitions q0;
  { start = q0; trans = !trans }

Note : il est bien entendu possible de construire au final un automate dont les états ne sont pas des ensembles mais, par exemple, des entiers, pour plus d'efficacité dans l'exécution de l'automate. Cela pourrait d'ailleurs être fait pendant la construction, ou a posteriori. Mais ce n'est pas ce qui nous intéresse ici.

Question 5. Tests

Écrire une fonction

val recognize : autom -> string -> bool

qui détermine si un mot est reconnu par un automate.

Pour tester, on reprend l'exemple ci-dessus :

(*  (a|b)*a(a|b)  *)
let r = Concat (Star (Union (Character ('a', 1), Character ('b', 1))),
		Concat (Character ('a', 2),
			Union (Character ('a', 3), Character ('b', 2))))
let a = make_dfa r

Voici quelques tests positifs (la réponse doit être true) :

let _ = recognize a "aa"
let _ = recognize a "ab"
let _ = recognize a "abababaab"
let _ = recognize a "babababab"
let _ = recognize a (String.make 1000 'b' ^ "ab")

et quelques tests négatifs (la réponse doit être false) :

let _ = recognize a ""
let _ = recognize a "a"
let _ = recognize a "b"
let _ = recognize a "ba"
let _ = recognize a "aba"
let _ = recognize a "abababaaba"

Voici un autre test avec une expression régulière caractérisant un nombre pair de b :

let r = Star (Union (Star (Character ('a', 1)),
		     Concat (Character ('b', 1),
			     Concat (Star (Character ('a',2)),
				     Character ('b', 2)))))
let a = make_dfa r

Quelques tests positifs :

let _ = recognize a ""
let _ = recognize a "bb"
let _ = recognize a "aaa"
let _ = recognize a "aaabbaaababaaa"
let _ = recognize a "bbbbbbbbbbbbbb"
let _ = recognize a "bbbbabbbbabbbabbb"

et quelques tests négatifs :

let _ = recognize a "b"
let _ = recognize a "ba"
let _ = recognize a "ab"
let _ = recognize a "aaabbaaaaabaaa"
let _ = recognize a "bbbbbbbbbbbbb"
let _ = recognize a "bbbbabbbbabbbabbbb"

solution

retour à la page du cours