\documentclass{tpcaml}

\def\ext{png}

\usepackage{graphicx}

\tp{4}{Automates}

\begin{document}

  \maketitle

\begin{codesection}
  type automate = \{\+\\
  final : bool vect;\\
  initial : int;\\
  transitions : (char*int) list vect;\-\\
  \};;
\end{codesection}

  Dans ce TP, on travaillera sur des automates dont le type est donné
  ci-contre. On remarque que ce type peut servir à représenter à la fois
  des automates déterministes et des automates non-déter\-ministes: il suffit
  de faire apparaître plusieurs transitions pour la même lettre et le même
  état de départ. 

\section{Automates Déterministes}

  On rappelle qu'un automate est la description d'un ensemble d'états (on
  choisira ici $Q = \{0\ldots n-1\}$, où $n$ est le nombre d'états), des
  transitions d'un état à l'autre en réponse aux caractères d'un alphabet
  (ici, $\Sigma = \{a,b\}$), et d'un ensemble d'états finaux $\cal F$ dans
  lesquels se trouvera l'automate si la suite de caractères a été
  reconnue. On représentera ici la fonction de transition comme une liste
  de transitions $(c,e) \in \Sigma\times Q$, chaque état disposant de sa
  liste de transitions propres.

\vspace{12pt}
\sideimage{a1.\ext}
\begin{question}
  \'Ecrire une fonction de création d'automate \code{make\_automate n i}
  qui crée un automate à $n$ états, dont l'état initial est $i$, et ne
  contenant aucune transition ni aucun état final. 

  \'Ecrire une fonction \code{ajoute\_final a f} qui marque l'état $f$ de
  l'automate $a$ comme étant un état final.

  \'Ecrire enfin une fonction d'ajout de transition appelée
  \code{ajoute\_transition a (c,i,j)} qui ajoute une transition de l'état
  $i$ à l'état $j$ dans l'automate $a$ lorsque le caractère $c$ est
  lu.

  Utiliser ces trois fonctions pour définir en \cli\ l'automate dessiné
  ci-contre.
\end{question}
\vspace{12pt}

  On souhaite désormais reconnaitre des mots. Cependant, le système de
  reconnaissance dépend de si l'automate representé par le type
  \code{automate} est déterministe (auquel cas, on se trouve dans un seul
  état à la fois) ou non-déterministe (il faut alors stocker tous les états
  possibles en même temps). 

\begin{codesection}
  type lecteur = \{ \+\\
  lire : char -> unit;\\
  reconnu : unit -> bool;\-\\
  \};;\\
  \\
  let reconnaitre lecteur mot =\+\\
    for i = 0 to string\_length mot - 1 do\+\\
      lecteur.lire mot.[i]\-\\
    done;\\
    lecteur.reconnu ();;
\end{codesection}
  Pour s'abstraire de ce détail technique, on crée un type \code{lecteur}
  qui cache le fonctionnement réel de l'automate derrière une interface
  simplifiée: une fonction \code{lire} qui lit un caractère, et une
  fonction \code{reconnu} indiquant si le mot (composé des caractères lus
  un à un) est reconnu ou non.

  Dans ces conditions, reconnaître un mot devient très simple: la fonction
  \code{reconnaitre} utilise un lec\-teur fourni en argument pour reconnaître
  un mot en épelant ce mot au lecteur, puis en déterminant si le lecteur
  est dans un état acceptant ou non. Pour faire la liaison entre les
  lecteurs d'un côté et les automates de l'autre, il faudra juste écrire
  les fonctions \code{lire} et \code{reconnu}.
  
\vspace{12pt}
\begin{question}
  \'Ecrire une fonction \code{deterministe} de type \code{automate ->
  lecteur} qui suppose que son argument est un automate déterministe à
  états finis et crée un lecteur permettant de reconnaître des mots à
  l'aide de cet automate.

  Tester l'automate de la question précédente.
\end{question}
\vspace{12pt}

\clearpage
\section{Automates Non-Déterministes}

  Pour des raisons de simplicité des preuves, on utilise parfois des
  automates non-déterministes: ceux-ci peuvent se trouver dans plusieurs
  états à la fois. On choisira de représenter ici cet ensemble d'états par
  une liste. Un automate non-déterministe, contrairement à un automate
  déterministe, peut avoir n'importe quel nombre de flèches sortantes pour
  un caractère donné et un état donné (contre exactement une flèche par
  caractère par état pour un automate déterministe).

\vspace{12pt}
\sideimage{a2.\ext}
\begin{question}
  Représenter l'automate non-déter\-ministe ci-contre à l'aide des
  fonctions définies à la question 1.
\end{question}
\vspace{12pt}

  Effectuer une transition dans un automate non-déterministe consiste à
  prendre, pour chaque état cou\-rant, l'ensemble des états vers lesquels une
  transition aboutirait en suivant le caractère lu, puis à fusionner les
  ensembles d'états ainsi obtenus pour obtenir l'ensemble complet. 

\vspace{12pt}
\begin{question}
  \'Ecrire une fonction \code{assoc\_all c l} qui fonctionne comme la
  fonction \code{assoc}, mais qui renvoie tous les éléments de la liste
  \code{l} associés à \code{c}, plutôt que seulement le premier.

  \'Ecrire une liste \code{fusion l} qui prend en argument une liste de
  listes d'états \code{l} et renvoie une liste contenant tous les états s'y
  trouvant une et une seule fois (on pourra utiliser la fonction
  \code{union} de \cli).

  En déduire une fonction \code{nondeterministe} de type \code{automate ->
  lecteur} qui crée un lecteur à partir d'un automate non-déterministe.
\end{question}

\section{Automates Non-Déterministes à $\varepsilon$-Transitions}

  Un automate à $\varepsilon$-transitions peut toujours suivre un nombre
  arbitraire d'$\varepsilon$-transitions juste avant ou juste après avoir
  lu un caractère. 

\sideimage{a3.\ext}
  De la même façon qu'un automate non-déterminis\-te peut se réduire à un
  automate déterministe (où un état de l'automate déterministe correspond à
  un sous-ensemble des états de l'automate non-déterministe) il est
  possible de réduire un automate non-déterministe à
  $\varepsilon$-transitions à un automate non-déterministe sans
  $\varepsilon$-transitions. Cette réduction peut se faire sans ajou\-ter
  d'états, et seulement en ajoutant des transitions.

\vspace{12pt}
\begin{question}
  Montrer qu'on peut toujours supprimer une transition $A
  \stackrel{\varepsilon}{\longrightarrow} A$, et qu'on peut supprimer une
  transition $A \stackrel{\varepsilon}{\longrightarrow} B$ en ajoutant à
  $A$ toutes les transitions sortantes de $B$ et, si $B$ était final, en
  rendant $A$ final.

  Montrer que, s'il n'y a pas de cycles dans les $\varepsilon$-transitions
  (autrement dit, qu'on ne peut pas boucler infiniment sans lire de
  caractères) alors il y a un ordre optimal évident dans lequel on peut
  traiter les transitions (en termes de nombre de transitions traitées). 

  En déduire une représentation de l'automate ci-contre comme un automate
  non-déterministe sans $\varepsilon$-transitions.
\end{question}

\section{Question Difficile}

\begin{question}
  On donne un automate sous une forme états-transitions de votre
  choix. \'Ecrire un programme qui prend en argument un automate sous cette
  forme et un entier \code{n}, et qui affiche les $n$ mots les plus courts
  reconnus par l'automate (on n'impose pas d'ordre sur les mots qui ont la
  même longueur). L'énumération doit être exhaustive (il ne doit manquer
  aucun mot).
\end{question}

\end{document}