\documentclass{tp-caml-2009}

\usepackage{gastex}

\tp{
  title=Compilation d'expressions rationnelles,
  number=Septième,
  date=Jeudi 4 février 2010,
  class=MP
}

\newenvironment{indication}
{\small\vspace{-1em}\begin{list}{}
{\leftmargin=0.5cm\labelwidth=0cm\itemindent=0cm}
\item $\vartriangleright$ \textsf{Indication.}
}
{\end{list}\normalfont\medskip}
%{\small\vspace{-1em}\textsf{Indication} $\triangleright$\slshape}
%{\normalfont\medskip}


\begin{document}

\begin{abstract}
%  \tpsource{D'après « Le Langage Caml », Pierre Weis et Xavier Leroy,
%    Dunod (1999)}
  Nous nous intéressons aujourd'hui au problème de déterminer si une
  expression rationnelle reconnaît une chaîne de caractères.  La
  traduction naïve de la définition des chaînes reconnues par une
  expression rationnelle mène à un algorithme par essais et erreurs
  qui est très inefficace dans certains cas.  La manière efficace de
  déterminer si une expression rationnelle reconnaît une chaîne de
  caractères est de transformer d'abord l'expression rationnelle en un
  automate qui reconnaît les mêmes mots, puis d'exécuter l'automate
  sur ladite chaîne de caractères.
\end{abstract}



\begin{corpus}


% *************************************************************************
%\section{Automates non-déterministes et expressions rationnelles}
%\label{section:nfa}

% -------------------------------------------------------------------------
\section{Expressions rationnelles}

On considère un \emph{alphabet} $\Sigma$ (les éléments de $\Sigma$,
les \emph{caractères}, sont notés $c$).  Une \emph{expression
  rationnelle} permet de représenter de manière finie un
\emph{langage} sur $\Sigma$, c'est-à-dire une partie de l'ensemble des
mots sur $\Sigma$, usuellement noté $\Sigma^*$.  Les \emph{expressions
  rationnelles} $r$ sur $\Sigma$ sont définies par la grammaire
suivante:
$$
\begin{array}{rcl}
  r & ::=  & \varepsilon \\
  & \mid & c \\
  & \mid & (r \mid r) \\
  & \mid & (r r) \\
  & \mid & r^\ast
\end{array}
$$
On définit le langage dénoté par une expression rationnelle de
manière récursive.  $\varepsilon$ dénote le langage contenant le mot vide
$\varepsilon$ tandis que $c$ dénote le langage $\{c\}$.  Si $r_1$ et $r_2$
dénotent respectivement les langages $L_1$ et $L_2$ alors $(r_1 \mid r_2)$
dénote l'union des langages : $L_1 \cup L_2$ et $(r_1 r_2)$ dénote la
concatenation $L_1 \cdot L_2$.  Enfin $r_1^\ast$ dénote le langage $L_1^\ast$.

Dans la suite de cet énoncé, nous supposerons que les éléments de
$\Sigma$ sont représentés en Caml par des \emph{caractères} de type
\lstinline"char".  

\begin{question}
  Donner une définition par un type \lstinline|regexp| inductif (comme
  pour les arbres), pour representer les expressions rationnelles
  (\emph{regular expressions} en anglais). 
\end{question}

\begin{solution-caml}
type regexp = 
  | Epsilon
  | Char of char
  | Or of regexp * regexp
  | Seq of regexp * regexp
  | Star of regexp
\end{solution-caml}

Pour pouvoir tester les fonctions construites on va se donner un petit
exemple. 

\begin{question}
  Écrivez en Caml, dans le type définit à la question précedente, l'expression
  rationnelle correspondant à $a ( b c \mid d )^\ast e$.
\end{question}

\begin{solution-caml}
let example = 
  Seq (Seq (Char 'a' , Star ( Or (
    Seq (Char 'b', Char 'c') , Char 'd') ) ) , Char 'e')
\end{solution-caml}


% -------------------------------------------------------------------------
% \subsection{Automates non-déterministes}

%% Nous représentons un \emph{état} d'un \emph{automate fini
%%   non-déterministe} (NFA) par un enregistrement à quatre champs du
%%   type suivant :

%% \begin{caml}[2]
%%   type nfa_state =
%%     { mutable trans: (char * nfa_state) list;
%%       mutable eps_trans: nfa_state list;
%%       mutable terminal: bool;
%%       index: int
%%     }
%%   ;;
%% \end{caml}

%% Le champ \lstinline"terminal" est un booléen indiquant si l'état est
%% terminal.  Les champs \lstinline"trans" et \lstinline"eps_trans"
%% contiennent la liste des transitions dont l'état en question est
%% l'origine.  Le champ \lstinline"index" sert à identifier les états de
%% manière unique : deux états différents portent des numéros différents.

%% \begin{question}
%%   Écrivez une fonction \lstinline"nfa_create" qui crée un nouvel
%%   état, sans transitions.  L'index de l'état créé devra être
%%   \emph{unique}, i.e.\ chaque appel à la fonction doit retourner un
%%   état avec un index différent.  (Vous pourrez utiliser à cette fin
%%   une référence globale.)

%%   \begin{prototype}
%%     value nfa_create: unit -> nfa_state
%%   \end{prototype}
%% \end{question}

%% \begin{solution}
%%   On définit tout d'abord une compteur entier « global », dont le
%%   contenu initial est $0$.

%%   \begin{caml}[2]
%%   let counter = ref 0
%%   ;;
%%   \end{caml}

%%   À chaque appel de la fonction \lstinline"nfa_create", ce compteur
%%   est incrémenté d'une unité et un nouvel état est créé.

%%   \begin{caml}[2]
%%   let nfa_create () =
%%     counter := !counter + 1;
%%     { trans = [];
%%       eps_trans = [];
%%       terminal = false;
%%       index = !counter
%%     }
%%   ;;
%%   \end{caml}
%% \end{solution}



%% \begin{question}
%%   Écrivez deux fonctions \lstinline"add_trans" et
%%   \lstinline"add_eps_trans" permettant d'ajouter une transition ou une
%%   $\epsilon$-transition entre deux états.

%%   \begin{prototype}
%%     value add_trans: nfa_state -> char -> nfa_state -> unit
%%     value add_eps_trans: nfa_state -> nfa_state -> unit
%%   \end{prototype}
%% \end{question}

%% \begin{solution}
%%   Pour ajouter une transition, il suffit de modifier en place une des
%%   listes \lstinline"trans" ou \lstinline"eps_trans" de l'état origine.

%%   \begin{caml}[4]
%%     let add_trans s1 c s2 =
%%       s1.trans <- (c, s2) :: s1.trans
%%     ;;

%%     let add_eps_trans s1 s2 =
%%       s1.eps_trans <- s2 :: s1.eps_trans
%%     ;;
%%   \end{caml}
%% \end{solution}



% -------------------------------------------------------------------------
\section{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 particularité d'avoir
un seul état final.  De plus aucune transition ne sort de l'état final.
En revanche les epsilon transitions sont authorisés.
Ainsi, un automate de Thompson pourrat être représenté en Caml par un
enregistrement du type suivant :

\begin{caml}
type thompson = 
  {
    initial : int ;
    final : int ; 
    trans : (int * char * int) list ; 
    eps_trans : (int * int) list ; 
  }
\end{caml}

La construction de Thompson procède par récurrence sur la structure de
l'expression rationnelle.  Les
questions~\ref{question:thompson-epsilon}
à~\ref{question:thompson-star} introduisent quelques fonctions
auxiliaires permettant d'effectuer les opérations de base sur les
automates, que vous pourrez ensuite utiliser pour réaliser la
construction de Thompson à la question~\ref{question:thompson}.

Au fur et a mesure de la construction on va avoir besoin de nouveau états,
comme ils sont représenter de façon unique par un entier, il est neccessaire
de connaître ceux qui sont déjà utilisé. Pour cela on peut soit déclarer une
reference qui contiendra le nombre d'états, soit passer un argument
supplémentaire à chaque fonction et qui contient cette valeur.
C'est ce qu'il est suggéré de faire dans la suite

\begin{question}
  \label{question:thompson-epsilon}
  Écrivez une fonction \lstinline"th_epsilon" telle que
  \lstinline"th_epsilon i" retourne un automate de Thompson
  reconnaissant le langage vide.

  \begin{prototype}
    val th_epsilon: int -> thompson * int
  \end{prototype}
\end{question}

\begin{solution-caml}
let th_epsilon i =
  {initial = i ; final = i + 1 ;
   trans = [] ; eps_trans = [i,i + 1] } , i + 2
\end{solution-caml}



\begin{question}
  Écrivez une fonction \lstinline"th_char" telle que
  \lstinline"th_char c" retourne un automate de Thompson
  reconnaissant le langage $\{c\}$.

  \begin{prototype}
    val th_char: int -> char -> thompson * int
  \end{prototype}
\end{question}

\begin{solution-caml}
let th_char i c = 
  { initial = i ; final = i + 1 ;
    trans = [i,c,i + 1] ; eps_trans = [] } , i + 2
\end{solution-caml}



Étant donnés deux 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 \cup L_2$ de la
manière suivante :
%
\begin{center}
\begin{picture}(32,22)(0,-11)
  \gasset{Nw=4,Nh=4}
  \node[Nmarks=i](I)(0,0){}
  \node(I1)(7,7){}
  \node(I2)(7,-7){}
  \node[Nmarks=r](F)(32,0){}
  \node(F1)(25,7){}
  \node(F2)(25,-7){}

  \drawedge(I,I1){$\varepsilon$}
  \drawedge[ELside=r](I,I2){$\varepsilon$}
  \drawedge(F1,F){$\varepsilon$}
  \drawedge[ELside=r](F2,F){$\varepsilon$}
  \drawqbedge[AHnb=0,dash={0.2 0.5}0](I1,16,14,F1){}
  \drawqbedge[AHnb=0,dash={0.2 0.5}0](I1,16,0,F1){}
  \drawqbedge[AHnb=0,dash={0.2 0.5}0](I2,16,-14,F2){}
  \drawqbedge[AHnb=0,dash={0.2 0.5}0](I2,16,0,F2){}
  \node[Nframe=n](A1)(16,7){$a_1$}
  \node[Nframe=n](A2)(16,-7){$a_2$}
\end{picture}
\end{center}



\begin{question}
  Écrivez une fonction \lstinline"th_or" implémentant la
  construction décrite ci-dessus.

  \begin{prototype}
    val th_or: int -> thompson -> thompson -> thompson * int
  \end{prototype}
\end{question}

\begin{solution-caml}
let th_or i a b = 
  {
    initial = i ; 
    final = i + 1 ;
    trans = List.rev_append a.trans b.trans ;
    eps_trans = 
      (i , a.initial)
      :: (i , b.initial)
      :: (a.final , i + 1)
      :: (b.final , i + 1)
      :: (List.rev_append a.eps_trans b.eps_trans) 
  } , i + 2

\end{solution-caml}


De même, on peut construire un automate de Thompson reconnaissant le
langage $L_1 \cdot L_2$ comme suit :
%
\begin{center}
\begin{picture}(48,10)(0,-5)
  \gasset{Nw=4,Nh=4}
  \node[Nmarks=i](I1)(0,0){}
  \node(F1)(18,0){}
  \node(I2)(30,0){}
  \node[Nmarks=r](F2)(48,0){}

  \drawedge(F1,I2){$\varepsilon$}
  \drawqbedge[AHnb=0,dash={0.2 0.5}0](I1,9,7,F1){}
  \drawqbedge[AHnb=0,dash={0.2 0.5}0](I1,9,-7,F1){}
  \drawqbedge[AHnb=0,dash={0.2 0.5}0](I2,39,7,F2){}
  \drawqbedge[AHnb=0,dash={0.2 0.5}0](I2,39,-7,F2){}
  \node[Nframe=n](A1)(9,0){$a_1$}
  \node[Nframe=n](A2)(39,0){$a_2$}
\end{picture}
\end{center}



\begin{question}
  Écrivez une fonction \lstinline"th_seq" implémentant la
  construction décrite ci-dessus.

  \begin{prototype}
    val th_seq: int -> thompson -> thompson -> thompson * int
  \end{prototype}
\end{question}

\begin{solution-caml}
let th_seq i a b =
  {
    initial = a.initial ;
    final = b.final;
    trans = List.rev_append a.trans b.trans ;
    eps_trans = (a.final,b.initial) :: List.rev_append a.eps_trans b.eps_trans ;
  }, i 
\end{solution-caml}


Enfin, étant donné un automate de Thompson $a$ reconnaissant le
langage $L$, l'automate suivant reconnaît le langage $L^{\ast}$ :
%
\begin{center}
\begin{picture}(42,20)(0,-10)
  \gasset{Nw=4,Nh=4}
  \node[Nmarks=i](I)(0,0){}
  \node(I1)(12,0){}
  \node(F1)(30,0){}
  \node[Nmarks=r](F)(42,0){}

  \drawedge(I,I1){$\varepsilon$}
  \drawedge(F1,F){$\varepsilon$}

  \drawqbedge(I,21,15,F){$\varepsilon$}
  \drawqbedge(F1,21,-15,I1){$\varepsilon$}

  \drawqbedge[AHnb=0,dash={0.2 0.5}0](I1,21,7,F1){}
  \drawqbedge[AHnb=0,dash={0.2 0.5}0](I1,21,-7,F1){}
  \node[Nframe=n](A)(21,0){$a$}
\end{picture}
\end{center}



\begin{question}
  \label{question:thompson-star}
  Écrivez la fonction \lstinline"th_star" correspondante.

  \begin{prototype}
    val th_star: int -> thompson -> thompson * int
  \end{prototype}
\end{question}

\begin{solution-caml}
let th_star i a =
  {
    initial = i ;
    final = i + 1 ;
    trans = a.trans ;
    eps_trans = 
      (i,i + 1) :: (i,a.initial) :: (a.final,i + 1) :: (a.final,a.initial)
      :: a.eps_trans ;
  }, i + 2
\end{solution-caml}



\begin{question}
  \label{question:thompson}
  Déduisez-en une fonction \lstinline"thompson" prenant en argument un
  expression rationnelle $r$ et retournant un automate
  non-déterministe reconnaissant le langage dénoté par $r$.

  \begin{prototype}
    val thompson: regexp -> thompson
  \end{prototype}
\end{question}

\begin{solution-caml}
let thompson r = 
  let rec aux i = function
    | Epsilon -> th_epsilon i
    | Char c -> th_char i c
    | Or (a, b) -> 
        let x,j = aux i a in 
        let y,k = aux j b in
          th_or k x y
    | Seq (a, b) ->
        let x,j = aux i a in 
        let y,k = aux j b in
          th_seq k x y
    | Star a -> 
        let x,j = aux i a in 
          th_star j x
  in fst (aux 0 r)
\end{solution-caml}



% *************************************************************************
%% \section{Déterminisation}

%% Ayant obtenu un automate qui reconnaît les mêmes chaînes que
%% l'expression rationnelle de départ, il nous reste à programmer une
%% fonction qui teste si une chaîne est reconnue ou non par l'automate.
%% La réalisation d'un tel test sur un automate non déterministe est
%% susceptible d'être peu efficace : puisque plusieurs transitions
%% portant le même caractère peuvent sortir d'un même état, il faut
%% quelquefois essayer plusieurs chemins qui épellent la chaîne à
%% reconnaître.  C'est la raison pour laquelle il est généralement
%% préférable d'effectuer la reconnaissance sur un automate
%% \emph{déterministe}.  L'objet de cette partie est donc de produire un
%% tel automate à partir de celui obtenu grâce à la construction de
%% Thompson.




%% % -------------------------------------------------------------------------
%% \subsection{Automates déterministes}


%% On rappelle que, en Caml (comme dans beaucoup de langages de
%% programmation), les caractères sont «~numérotés~» de 0 à 255.  Dans
%% cet énoncé, on note $c_i$ le caractère qui porte le numéro $i$ (par
%% exemple $c_{97}$ représente le caractère «~a~»).  Les deux fonctions
%% suivantes de la librairie standard permettent de convertir un
%% caractère en son numéro et réciproquement :

%% \begin{caml}[2]
%%   value int_of_char: char -> int
%%   value char_of_int: int -> char
%% \end{caml}

%% Nous représentons un état d'un automate déterministe (DFA) par un
%% enregistrement du type suivant :

%% \begin{caml}[2]
%%   type dfa_state =
%%     { mutable dtrans: dfa_state vect;
%%       mutable dterminal: bool
%%     }
%%   ;;
%% \end{caml}

%% Le champ \lstinline"dterminal" est un booléen indiquant si l'état est
%% terminal ou non.  Un tableau \lstinline"dtrans" à 256 cases (une par
%% caractère) décrit les transitions dont l'état est l'origine : étant
%% donnés un état $s$ et un entier $i$ compris entre $0$ et $255$,
%% $s.\mathit{dtrans}.(i)$ est l'extrémité de la transition d'origine $s$
%% et étiquetée par $c_i$.  Par souci de simplicité, nous supposons que
%% chaque état est origine d'exactement une transition étiquetée par
%% chaque caractère.  Vous avez probablement vu en cours qu'il est
%% toujours possible de se ramener à une telle situation en introduisant
%% un état «~poubelle~» (i.e.\ un état $s$ tel que pour tout $i$,
%% $s.\mathit{dtrans}.(i) = s$).



%% \begin{question}
%%   Écrivez une fonction \lstinline"dfa_create" telle que
%%   \lstinline"dfa_create ()" retourne un nouvel état d'un automate
%%   déterministe (dont toutes les transitions bouclent sur lui-même).
%% \end{question}

%% \begin{solution}
%%   Une écriture naturelle de la fonction \lstinline"dfa_state" serait
%%   la suivante :

%%   \begin{caml}[2]
%%   let dfa_create () =
%%     let rec s = 
%%       { dtrans = make_vect 256 s;
%%         dterminal = false
%%       }
%%     in
%%     s
%%   ;;
%%   \end{caml}

%%   Cependant, la définition récursive de \lstinline"s" utilisée n'est
%%   pas acceptée par le compilateur Caml.  Il faut donc procéder en deux
%%   étapes : d'abord créer l'état \lstinline"s" avec un vecteur de
%%   transitions vide puis modifier en place ce vecteur.

%%   \begin{caml}[2]
%%   let dfa_create () =
%%     let s = 
%%       { dtrans = [||];
%%         dterminal = false
%%       }
%%     in
%%     s.dtrans <- make_vect 256 s;
%%     s
%%   ;;
%%   \end{caml}
%% \end{solution}



%% Dans notre représentation des automates, chaque état contient
%% directement la liste de ses successeurs.  Ainsi, pour désigner un
%% automate, il suffit de donner son état initial.

%% \begin{question}
%%   Écrivez une fonction \lstinline"accept" déterminant si un
%%   automate déterministe reconnaît une chaîne de caractères.

%%   \begin{prototype}
%%     value accept: dfa_state -> string -> bool
%%   \end{prototype}
%% \end{question}

%% \begin{solution}
%%   Pour tester si un automate déterministe reconnaît une chaîne, il
%%   suffit de lire cette dernière caractère par caractère en effectuant
%%   simultanément les transitions sur l'automate.  La chaîne est
%%   reconnue si le dernier état obtenu est terminal.  (La lecture ne
%%   peut pas échouer car nous avons supposé que tout état est l'origine
%%   d'exactement une transition étiquetée par chaque caractère.)

%%   \begin{caml}[2]
%%   let accept initial string =
%%     let n = string_length string in
%%     let rec aux state i =
%%       if i = n then state.dterminal
%%       else aux state.dtrans.(int_of_char string.[i]) (i + 1)
%%     in
%%     aux initial 0
%%   ;;
%%   \end{caml}
%% \end{solution}



%% % -------------------------------------------------------------------------
%% \subsection{Construction des sous-ensembles}

\section{Suppression des $\varepsilon$-transitions}
%% L'algorithme que nous allons mettre en \oe{}uvre pour déterminiser un
%% automate est connu sous le nom de «~construction des sous-ensembles~»
%% (\emph{subset construction} en anglais).  Les états de l'automate
%% déterministe correspondent à des ensembles d'états de l'automate de
%% départ : tous les états qu'on peut atteindre à partir de l'état
%% initial en suivant une certaine chaîne de caractères.
On cherche maintenant à enlever les $\varepsilon$-transitions de l'automate
obtenus. 
L'ensemble d'états initial de l'automate sans  $\varepsilon$-transitions est l'ensemble
des états qu'on peut atteindre en suivant la chaîne vide, c'est-à-dire l'état
initial de l'automate de départ, plus tous les états qu'on peut
atteindre à partir de l'état initial en suivant uniquement des
$\varepsilon$-transitions.  
De même un état est final si un des états $s_1, \hdots, s_n$ que l'on peut
atteindre en ne suivant que des $\varepsilon$-transitions est final.

%% Pour voir où mène la transition sur un caractère $c$ issue de
%% l'ensemble d'états $\{s_1, \hdots, s_m\}$, on regarde toutes les
%% transitions sur $c$ issues des états $s_1$ à $s_m$ dans l'automate
%% initial.  Soient $t_1, \hdots, t_n$ les états auxquelles elles mènent.
%% Soit $\{t_1, \hdots, t_n, t'_1, \hdots, t'_{n'}\}$ la
%% $\epsilon$-fermeture de cet ensemble d'états (c'est-à-dire les états
%% accessibles à partir de $t_1, \hdots, t_n$ en suivant uniquement des
%% $\epsilon$-transitions).  
%% On ajoute alors, dans l'automate
%% déterministe produit, une transition sur $c$ depuis l'état $\{s_1,
%% \hdots, s_m\}$ vers l'état $\{t_1, \hdots, t_n, t'_1, \hdots,
%% t'_{n'}\}$.  On répète ce procédé jusqu'à ce qu'il soit impossible
%% d'ajouter de nouvelles transitions.

Nous représenterons les ensembles d'états (d'automates
non-déterministes) simplement par des listes de type
\lstinline"int list" (nous supposerons qu'un même état
apparaît au plus une fois dans une telle liste et que celle-ci est ordonnée). 

\columnbreak
\begin{question}
  Écrivez les fonctions \lstinline"mem_state" qui teste si un état
  apparaît dans une liste d'états
  et \lstinline|insert| qui insere un élement dans une liste trié.
  Écrivez également une fonction qui renvoie l'ensemble des états d'un
  automate. 
  \begin{prototype}
    val mem_state: int -> int list -> bool
    val insert : 'a -> 'a list -> 'a list
    val states : thompson -> int list
  \end{prototype}
\end{question}

%% \begin{indication}
%%   Vous ne pouvez pas utiliser l'égalité polymorphe de Caml
%%   (\lstinline"=") pour tester l'égalité de deux états : un état peut
%%   en effet se contenir récursivement dans sa liste des transitions et
%%   ainsi former une structure cyclique sur laquelle la comparaison ne
%%   terminerait pas.  Pour comparer deux états, le plus simple est
%%   d'utiliser leurs index.
%% \end{indication}

\begin{solution-caml}
let mem_state = 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_left (fun l (s,c,t) -> insert s (insert t l))
      [] th.trans
  in 
    List.fold_left (fun l (s,t) -> insert s (insert t l))
      st th.eps_trans

\end{solution-caml}

%% La représentation d'un ensemble d'état n'est pas unique : à un même
%% ensemble correspond plusieurs listes ordonnées différemment.  C'est
%% pourquoi, pour pouvoir identifier de manière unique un ensemble
%% d'état, nous définissons son \emph{empreinte} comme la liste
%% \textbf{triée} des numéros de ses états.

%% \begin{question}
%%   Écrivez une fonction \lstinline"trace" qui calcule l'empreinte d'une
%%   liste d'états.

%%   \begin{prototype}
%%     value trace: nfa_state list -> int list
%%   \end{prototype}
%% \end{question}

%% \begin{indication}
%%   Vous pouvez utiliser les fonctions suivantes de la bibliothèque
%%   standard.

%%     \lstinline"value sort__sort: ('a -> 'a -> bool) -> 'a list -> 'a list"
%%     \\
%%     \lstinline"sort__sort cmp list" retourne la liste
%%     \lstinline"list" triée en utilisant la relation d'ordre
%%     \lstinline"cmp".

%%     \lstinline"value map: ('a -> 'b) -> 'a list -> 'b list"
%%     \\
%%     \lstinline"map f [x1; ... xn]" retourne la liste
%%     \lstinline"[f x1; ...; f xn]".
%% \end{indication}

%% \begin{solution}
%%   Il suffit de combiner deux appels aux fonctions de la bibliothèque
%%   standard \lstinline"map" (afin d'obtenir la liste des index) et
%%   \lstinline"sort__sort" (pour la trier).

%%   \begin{caml}[4]
%%     let trace list =
%%       sort__sort (prefix <=) (map (function s -> s.index) list)
%%     ;;
%%   \end{caml}
%% \end{solution}


Étant donné un ensemble $S$ d'états d'un automate non-déterministe, on
définit son $\varepsilon$-fermeture comme l'ensemble des états
accessibles à partir d'un état de $S$ en traversant zéro, une ou
plusieurs $\varepsilon$-transitions.

\begin{question}
  Définissez une fonction \lstinline"epsilon_closure" qui calcule la
  $\varepsilon$-fermeture d'un d'état (d'un automate
  non-déterministe).

  \begin{prototype}
    val epsilon_closure: thompson -> int -> int list
  \end{prototype}
\end{question}

\begin{solution-caml}
let epsilon_closure th s =
  let rec aux set = 
    let new_set =
      List.fold_left (fun l (x,y) -> 
                        if appartient x set
                        then insert y l else l)
        set th.eps_trans
    in 
      if List.length set = List.length new_set 
      then set else aux new_set
  in aux [s]
\end{solution-caml}



\begin{question}
  Déduisez-en une fonction \lstinline"remove_eps_trans" qui construit
  un automate sans $\varepsilon$-transitions reconnaissant le même langage
  qu'un automate donnée. 
  Cet automate peut par exemple être du type que vous avez utilisé dans les
  sujets précedents.
  \begin{prototype}
    val remove_eps_trans: thompson -> int automate
  \end{prototype}
\end{question}

\begin{solution-caml}
type 'a automate =
    {
      i : 'a list ; 
      f : 'a list;
      t : ('a * char * 'a) list
    }


let remove_eps_trans th =
  let states = states th in
  let delta s =
    let cl = epsilon_closure th s in
      List.fold_left 
	(fun l (t,c,v) -> 
	   if mem_stat t cl then (s,c,v) :: l else l) []  th.trans
  in
  let new_trans = 
    List.fold_left
      (fun l s -> List.rev_append (delta s) l)
      [] states
  in 
  let new_final = 
    List.fold_left
      (fun l s -> 
	 if mem_stat th.final (epsilon_closure th s)
	 then s :: l else l) [] states
  in
    {
      i = epsilon_closure th th.initial;
      f = new_final; 
      t = new_trans
    }

\end{solution-caml}

\end{corpus}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
