solution

▶ Question 0 solution-caml “begincaml “endcaml

▶ Question 0

Compilation d’expressions rationnelles

Nous nous intssons aujourd’hui au probl de drminer si une expression rationnelle reconnane cha de caracts. La traduction na de la dnition des chas reconnues par une expression rationnelle m algorithme par essais et erreurs qui est trnefficace dans certains cas. La mani efficace de drminer si une expression rationnelle reconnane cha de caracts est de transformer d’abord l’expression rationnelle en un automate qui reconnaes ms mots, puis d’exter l’automate sur ladite cha de caracts.

“beginmulticols*2“raggedcolumns

1 Expressions rationnelles

On consid un alphabet Σ (les ments de Σ, les caracts, sont notc).Uneexpression rationnellepermetdereprnterdemanifinieunlangagesurΣ, c’est-ire une partie de l’ensemble des mots sur Σ, usuellement not^{∗}. Les expressions rationnelles r sur Σ sont dnies par la grammaire suivante :

\begin{aligned}r & ::= & ε \\ & | & c \\ & | & (r | r) \\ & | & (rr) \\ & | & r^{∗} \end{aligned}

On dnit le langage dtr une expression rationnelle de mani rrsive. ε dte le langage contenant le mot vide ε tandis que c dte le langage {c}. Si r_{1} et r_{2} dtent respectivement les langages L_{1} et L_{2} alors (r_{1} | r_{2}) dte l’union des langages : L_{1} ∪ L_{2} et (r_{1}r_{2}) dte la concatenation L_{1} · L_{2}. Enfin r_{1}^{∗} dte le langage L_{1}^{∗}. Dans la suite de cet ncous supposerons que les ments de Σ sont reprntn Caml par des caracts de type char. “stepcountervs@question▶ Question 1 Donner une

dnition par un type regexp inductif (comme pour les arbres), pour representer les expressions rationnelles ( regular expressions en anglais).

type regexp = — Epsilon — Char of char — Or of regexp

* regexp — Seq of regexp * regexp — Star of regexp Pour pouvoir tester les fonctions construites on va se donner un petit exemple. “stepcountervs@question▶ Question 2 rivez en Caml, dans le type dnit question prdente, l’expression rationnelle correspondant ( b c | d)^{∗}e.

let example = Seq (Seq (Char ’a’ , Star ( Or ( Seq (Char ’b’, Char ’c’) , Char ’d’) ) ) , Char ’e’)

2 Construction de Thompson

L’algorithme de transformation d’une expression rationnelle en automate que nous allons employer est connu sous le nom de construction de Thompson . Les automates qu’il produit ont la particularitavoir un seul t final. De plus aucune transition ne sort de l’t final. En revanche les epsilon transitions sont authoris Ainsi, un automate de Thompson pourrat e reprnt Caml par un enregistrement du type suivant :

type thompson =
{
initial : int ;
final : int ;
trans : (int ∗ char ∗ int) list ;
eps trans : (int ∗ int) list ;
}

La construction de Thompson proc par rrrence sur la structure de l’expression rationnelle. Les questions ?? question :thompson-star introduisent quelques fonctions auxiliaires permettant d’effectuer les options de base sur les automates, que vous pourrez ensuite utiliser pour riser la construction de Thompson question ??. Au fur et a mesure de la construction on va avoir besoin de nouveau ts, comme ils sont reprnter de fa unique par un entier, il est neccessaire de connae ceux qui sont d utilisour cela on peut soit darer une reference qui contiendra le nombre d’ts, soit passer un argument supplntaire aque fonction et qui contient cette valeur. C’est ce qu’il est sugg de faire dans la suite “stepcountervs@question▶ Question 3 rivez une fonc-

tion th epsilon telle que th epsilon i retourne un automate de Thompson reconnaissant le langage vide.

val th epsilon: int −> thompson ∗ int

let th_{e}psiloni = initial = i; final = i + 1; trans = []; eps_{t}rans = [i, i + 1], i+ 2 “stepcountervs@question▶ Question 4 rivez une fonc-

tion th char telle que th char c retourne un automate de Thompson reconnaissant le langage {c}.

val th char: int −> char −> thompson ∗ int

let th_{c}haric = initial = i; final = i + 1; trans = [i, c, i + 1]; eps_{t}rans = [], i+ 2 ant donneux automates de Thompson a_{1} et a_{2} reconnaissant respectivement les langages L_{1} et L_{2}, on peut construire un automate de Thompson reconnaissant le langage L_{1} ∪ L_{2} de la mani suivante :

Nw=4,Nh=4 [Nmarks=i](I)(0,0) (I1)(7,7) (I2)(7,-7) [Nmarks=r](F)(32,0) (F1)(25,7) (F2)(25,-7) (I,I1)ε [ELside=r](I,I2)ε (F1,F)ε [ELside=r](F2,F)ε [AHnb=0,dash=0.2 0.50](I1,16,14,F1) [AHnb=0,dash=0.2 0.50](I1,16,0,F1) [AHnb=0,dash=0.2 0.50](I2,16,-14,F2) [AHnb=0,dash=0.2 0.50](I2,16,0,F2) [Nframe=n](A1)(16,7)a_{1} [Nframe=n](A2)(16,-7)a_{2}

“stepcountervs@question▶ Question 5 rivez une fonc-

tion th or implntant la construction dite ci-dessus.

val th or: int −> thompson −> thompson −> thompson ∗ int

let th_{o}riab = initial = i; final = i + 1; trans = List.rev_{a}ppenda.transb.trans; eps_{t}rans = (i, a.initial) :: (i, b.initial) :: (a.final, i + 1) :: (b.final, i + 1) :: (List.rev_{a}ppenda.eps_{t}ransb.eps_{t}rans), i+ 2 De m, on peut construire un automate de Thompson reconnaissant le langage L_{1} · L_{2} comme suit :

Nw=4,Nh=4 [Nmarks=i](I1)(0,0) (F1)(18,0) (I2)(30,0) [Nmarks=r](F2)(48,0) (F1,I2)ε [AHnb=0,dash=0.2 0.50](I1,9,7,F1) [AHnb=0,dash=0.2 0.50](I1,9,-7,F1) [AHnb=0,dash=0.2 0.50](I2,39,7,F2) [AHnb=0,dash=0.2 0.50](I2,39,-7,F2) [Nframe=n](A1)(9,0)a_{1} [Nframe=n](A2)(39,0)a_{2}

“stepcountervs@question▶ Question 6 rivez une fonc-

tion th seq implntant la construction dite ci-dessus.

val th seq: int −> thompson −> thompson −> thompson ∗ int

let th_{s}eqiab = initial = a.initial; final = b.final; trans = List.rev_{a}ppenda.transb.trans; eps_{t}rans = (a.final, b.initial) :: List.rev_{a}ppenda.eps_{t}ransb.eps_{t}rans;, i Enfin, nt donn automate de Thompson a reconnaissant le langage L, l’automate suivant reconnae langage L^{∗} :

Nw=4,Nh=4 [Nmarks=i](I)(0,0) (I1)(12,0) (F1)(30,0) [Nmarks=r](F)(42,0) (I,I1)ε (F1,F)ε (I,21,15,F)ε (F1,21,-15,I1)ε [AHnb=0,dash=0.2 0.50](I1,21,7,F1) [AHnb=0,dash=0.2 0.50](I1,21,-7,F1) [Nframe=n](A)(21,0)a

“stepcountervs@question▶ Question 7 rivez la fonc-

tion th star correspondante.

val th star: int −> thompson −> thompson ∗ int

let th_{s}taria = initial = i; final = i + 1; trans = a.trans; eps_{t}rans = (i, i + 1) :: (i, a.initial) :: (a.final, i + 1) :: (a.final, a.initial) :: a.eps_{t}rans;, i+ 2 “stepcountervs@question▶ Question 8 Disez-en une

fonction thompson prenant en argument un expression rationnelle r et retournant un automate non-drministe reconnaissant le langage dtr r.

val thompson: regexp −> thompson

let thompson r = let rec aux i = function — Epsilon -¿ th_{e}psiloni|Charc− > th_{c}haric|Or(a, b)− > letx, j = auxiainlety, k = auxjbinth_{o}rkxy|Seq(a, b)− > letx, j = auxiainlety, k = auxjbinth_{s}eqkxy|Stara− > letx, j = auxiainth_{s}tarjxinfst(aux0r)

3 Suppression des ε-transitions

On cherche maintenant lever les ε-transitions de l’automate obtenus. L’ensemble d’ts initial de l’automate sans ε-transitions est l’ensemble des ts qu’on peut atteindre en suivant la cha vide, c’est-ire l’t initial de l’automate de drt, plus tous les ts qu’on peut atteindre rtir de l’t initial en suivant uniquement des ε-transitions. De m un t est final si un des ts s_{1}, …, s_{n} que l’on peut atteindre en ne suivant que des ε-transitions est final. Nous reprnterons les ensembles d’ts (d’automates nondrministes) simplement par des listes de type int list (nous supposerons qu’un m t apparau plus une fois dans une telle liste et que celle-ci est ordonn.

“stepcountervs@question▶ Question 9 rivez les fonc-

tions mem state qui teste si un t apparaans une liste d’ts et insert qui insere un ment dans une liste tricrivez lement une fonction qui renvoie l’ensemble des ts d’un automate.

val mem state: int −> int list −> bool
val insert : ’a −> ’a list −> ’a list
val states : thompson −> int list

let mem_{s}tate = List.mem

let rec insert x = function — [] -¿ [x] — a : : s -¿ if x = a then a : : s else if x ¡ a then a : : insert x s else x : : a : : s let states th = let st = List.fold_{l}eft(funl(s, c, t)− > inserts(inserttl))[]th.transinList.fold_{l}eft(funl(s, t)− > inserts(inserttl))stth.eps_{t}rans ant donn ensemble S d’ts d’un automate non-drministe, on dnit son ε-fermeture comme l’ensemble des ts accessibles rtir d’un t de S en traversant z, une ou plusieurs ε-transitions. “stepcountervs@question▶ Question 10 Dnissez une

fonction epsilon closure qui calcule la ε-fermeture d’un

d’t (d’un automate non-drministe).

val epsilon closure: thompson −> int −> int list
let epsilon_{c}losureths  =  letrecauxset  =
letnew_{s}et  =  List.fold_{l}eft(funl(x, y)−  >

ifappartientxsettheninsertylelsel)setth.eps_{t}ransinifList.lengthset = List.lengthnew_{s}etthensetelseauxnew_{s}etinaux[s] “stepcountervs@question▶ Question 11 Disez-en une

fonction remove eps trans qui construit un automate sans ε-transitions reconnaissant le m langage qu’un automate donn Cet automate peut par exemple e du type que vous avez utilisns les sujets prdents.

val remove eps trans: thompson −> int automate

type ’a automate = i : ’a list ; f : ’a list ; t : (’a * char

* ’a) list

let remove_{e}ps_{t}ransth = letstates = statesthinletdeltas = letcl = epsilon_{c}losurethsinList.fold_{l}eft(funl(t, c, v)− > ifmem_{s}tattclthen(s, c, v) :: lelsel)[]th.transinletnew_{t}rans = List.fold_{l}eft(funls− > List.rev_{a}ppend(deltas)l)[]statesinletnew_{f}inal = List.fold_{l}eft(funls− > ifmem_{s}tatth.final(epsilon_{c}losureths)thens :: lelsel)[]statesini = epsilon_{c}losurethth.initial; f = new_{f}inal; t = new_{t}rans

2 “endmulticols*

3 4

Compilation d’expressions rationnelles

Un corrigé