\documentclass{tpcaml}

\def\ext{png}

\usepackage{graphicx}

\tp{5}{Algorithme de Thompson}

\begin{document}

  \maketitle

\begin{codesection}
type regexp = \+\\
  | Mot of string \\
  | Ou of regexp * regexp \\
  | Et of regexp * regexp \\
  | Etoile of regexp;;
\end{codesection}

  L'algorithme de Thompson permet de construire un automate à partir d'une
  expression rationelle de manière automatique. Dans ce TP, on choisit de
  représenter les expressios rationelles à l'aide du type \code{regexp}
  donné ci-contre. À titre d'échauffement, et pour réviser les concepts
  d'expressions rationelles d'il y a deux semaines, on se donne les deux
  expressions rationelles suivantes:
  \[ E_1 = (ba|a)^*(b|\varepsilon)\qquad E_2 = (a|b)^*(ab|ba) \]
  
\vspace{12pt}
\begin{question}
  Quels sont les langages reconnus par les expressions rationelles $E_1$ et 
  $E_2$ ? Représenter ces expressions à l'aide du type \code{regexp} donné
  précédemment.
\end{question}

\section{Construction}

\begin{codesection}
  type auto\_ndet = \{\+\\
      etats : int;\\
      char : (char * int * int) list;\\
      epsilon : (int * int) list;\-\\
  \};; 
\end{codesection}
  On représente les automates non-déterministes à $\varepsilon$-transitions
  par le type \code{auto\_ndet} défini ci-contre, avec la convention que
  l'état \code{0} est l'état initial, et que l'état \code{a.etats - 1} est
  l'unique état final de l'automate. On représente l'ensemble complet des
  transitions et $\varepsilon$-transitions par des listes, plutôt que de
  constituer une liste pour chaque état.

\vspace{12pt}
\begin{question}
  Représenter les automates non-déterministes à $\varepsilon$-transitions
  donnés ci-dessous à l'aide du type \code{auto\_ndet}.
\end{question}

\twoimages{a1.\ext}{a2.\ext}

  L'algorithme de Thompson consiste à construire un automate pour chaque
  sous-expression d'une expression rationelle donnée, puis de combiner ces
  automates en un seul automate représentant l'expression rationelle dans
  son ensemble. Par exemple, la concaténation de deux expressions
  rationelles $\alpha\beta$ peut se transformer récursivement en automate
  non-déterministe à $\varepsilon$-transitions en transformant $\alpha$ en
  un automate $A(\alpha)$, $\beta$ en un automate $A(\beta)$, et en reliant
  l'état final de $A(\alpha)$ à l'état initial de $A(\beta)$ par une
  $\varepsilon$-transition (et rendant au passage l'état final de
  $A(\alpha)$ non-final).

\vspace{12pt}
\begin{question}
  \'Ecrire deux fonctions d'aide, \code{decaler auto n} et \code{fusionner
  n a b liens}. 

\vspace{12pt}
  La fonction \code{decaler} crée un nouvel automate à partir
  de \code{auto}, de taille \code{auto.etats + n}, et décale ensuite toutes
  les transitions de \code{n} états (ainsi, si une transition partait ou
  arrivait sur l'état $i$, elle part ou arrive désormais sur l'état
  $i+n$). 

\vspace{12pt}
  La fonction \code{fusionner} construit un automate de taille \code{n}
  vierge, puis y insère toutes les transitions des automates \code{a} et
  \code{b} (ce qui revient à combiner les automates en question au sein
  d'un même automate plus grand) puis ajoute \code{liens} à la liste des
  $\varepsilon$-transitions de cet automate (pour relier, par exemple, un
  état final à un état initial).

\vspace{12pt}
  En déduire des fonctions \code{et a b}, \code{ou a b} et \code{etoile a}
  construisant les automates de concaténation, d'alternative et d'étoile à
  partir de sous-automates \code{a} et \code{b}.
\end{question}
\vspace{12pt}

  Une fois qu'il est possible de combiner des automates, on peut passer à
  l'étape suivante: traverser récursivement l'expression rationelle pour
  construire l'automate complet la représentant.

\vspace{12pt}
\begin{question}
  \'Ecrire une fonction \code{transforme e} qui renvoie un automate
  non-déterministe à $\varepsilon$-transitions qui reconnaît le même
  langage que l'expression rationelle \code{e}. On pourra, pour s'aider,
  commencer par écrire une fonction \code{mot s} qui renvoie un automate
  reconaissant le langage $\{ s \}$ constitué du seul mot \code{s}.
\end{question}

\section{Reconnaissance}

  On souhaite maintenant écrire un algorithme de reconnaissance
  d'une expression rationelle. Pour cela, on transforme cette expression en
  un algorithme non-déterministe à $\varepsilon$-transitions par
  l'algorithme de Thompson, et on utilise cet automate pour reconnaître des
  mots.

\begin{codesection}
  let rec insere e = function \+\\
  | [] -> [e]\\
  | t::q -> \+\\
      if t = e then t :: q \\
      else if t < e then t :: insere e q\\
      else e :: t :: q;;
\end{codesection}

  On choisit de représenter l'ensemble des états dans lesquels se trouve
  l'automate à un moment donné par une liste triée d'entiers. On utilisera,
  pour ajouter un élément à une liste, la fonction \code{insere} donnée
  ci-contre, qui permet de conserver l'ordre de la liste tout en évitant
  les doublons.

\vspace{12pt}
\begin{question}
  \'Ecrire une fonction \code{applique\_transition c etats transitions}
  qui, en supposant que l'automate se trouve dans les états \code{etats} et
  lit une lettre \code{c}, calcule le nouvel ensemble d'états à partir des
  transitoins de l'automate.

\vspace{12pt}
  \'Ecrire une fonction \code{applique\_epsilon etats transitions} qui,
  en supposant que l'automate se trouve dans les états \code{etats},
  calcule le nouvel ensemble d'états (contenant le précédent) qui peut être
  atteint à partir de cette position initial en suivant des
  $\varepsilon$-transitions. Attention, c'est mois évident qu'il n'y
  parait.

\vspace{12pt}
  En dédure une fonction \code{reconnaitre auto mot} qui renvoie vrai si et
  seulement si le mot fourni est reconnu par l'automate fourni.
\end{question}

\section{Question Difficile --- Déterminisation}

\begin{codesection}
  type automate = \{\+\\
      transitions : (char * int) list vect;\\
      initial : int;\\
      final : bool vect;\-\\
  \};;
\end{codesection}
  On reprend maintenant la définition d'un automate déterministe telle
  qu'elle a été fournie au TP précédent, et on se fixe pour objectif de
  construire un automate déterministe à partir d'une expression
  rationelle. Puisqu'un dispose déjà, grâce à l'algorithme de Thompson,
  d'un automate non-déterministe à $\varepsilon$-transitions, on peut se
  contenter de déterminiser celui-ci. 

  Pour déterminiser l'automate, on considère l'ensemble des sous-ensembles
  d'états de l'automate non-déterministe, chacun de ces sous-ensembles
  étant vu comme un état de
  l'automate déterministe. On calcule les transitions entre eux suivant
  la règle que si l'automate non-déterministe, dans les états $A$, passe
  dans les états $B$ après lecture du caractère $c$ (et application des
  $\varepsilon$-transitions), alors $A \stackrel{c}{\rightarrow} B$ dans
  l'automate déterministe. Un état est final si l'ensemble correspondant
  contient l'état final $n-1$.
  Pour des raisons de performances, on ne choisit que les états qui sont
  accessibles à partir de l'état initial.

\vspace{12pt}
\begin{question}
  Choisir des structures de données pour représenter l'automate durant sa
  construction, et programmer l'algorithme de déterminisation.
\end{question}

\end{document}