\begin{panneau}Nous nous intŽressons au probl�me suivant: Žtant donnŽ un langage rationnel $L$ non vide sur un alphabet $\Alphabet$, dŽterminer la longueur minimale d'un mot de $L$. Nous envisagerons deux situations: celle o� $L$ est dŽcrit par une expression rationnelle; celle o� $L$ est reconnu par un automate fini. L'algorithme devra dŽtecter le cas o� $L$ est vide.\end{panneau}\begin{panneau}Nous Žtudions la premi�re situation; l'ensemble des expressions rationnelles sur $\Alphabet$ sera notŽ ${\cal ER}(\Alphabet)$. Le langage dŽcrit par l'expression rationnelle $e$ sera notŽ $\LangER(e)$.\end{panneau}\begin{question}\label{def-alg-lambda}DŽfinissez par induction structurelle une fonction $\lambda:{\cal ER}(\Alphabet) \mapsto \{\vvv,\fff\}$ spŽcifiŽe comme suit: \begin{itemize} \item $\lambda(e) = \vvv$ si $\LangER(e)$ est vide;  \item $\lambda(e) = \fff$ dans le cas contraire.\end{itemize}\end{question}\begin{panneau}Supposons dŽfini le type Caml suivant:\begin{programme}\begin{verbatim}type 'a exprat = Vide | Epsilon | Lettre of 'a  | Union of 'a exprat * 'a exprat  | Produit of 'a exprat * 'a exprat | Etoile of 'a exprat ;;\end{verbatim}\end{programme}\end{panneau}\begin{question}RŽdigez en Caml une fonction de signature:\begin{programme}\begin{verbatim}lambda : 'a exprat -> bool \end{verbatim}\end{programme}\noindentspŽcifiŽe comme suit: \verb+lambda e+ calcule $\lambda(e)$. Objectif: sept lignes.\end{question}\begin{question}DŽfinissez par induction structurelle une fonction $\mu:{\cal ER}(\Alphabet) \mapsto \N \cup \{-°\}$ spŽcifiŽe comme suit: \begin{itemize} \item $\mu(e)$ est la longueur minimale d'un mot de $\LangER(e)$ si ce langage n'est pas vide;  \item $\mu(e) = -°$ sinon.\end{itemize}\end{question}\begin{panneau}Rappel: ˆ tout type \verb+'a+, Caml associe le type \verb+'a option+, qu'il dŽfinit comme suit:\begin{programme}\begin{verbatim}type 'a option = Some 'a | None ;;\end{verbatim}\end{programme}\noindentCe mŽcanisme permet donc d'ajouter ˆ un ensemble $E$ un ŽlŽment dont on est certain qu'il n'appartient pas ˆ $E$.\end{panneau}\begin{question}RŽdigez en Caml une fonction de signature:\begin{programme}\begin{verbatim}mu : 'a exprat -> int option \end{verbatim}\end{programme}\noindentspŽcifiŽe comme suit: si $e$ dŽcrit un langage non vide, alors \verb+mu e+ rend \verb+Some n+, o� $n = \mu(e)$; sinon, \verb+mu e+ rend \verb+None+. Objectif: treize lignes.\end{question}\begin{panneau}Nous supposons dŽsormais que $L$ est reconnu par un automate fini dŽterministe ${\cal A} = (Q,\delta,i,F)$.\end{panneau}\begin{question}Rappelez le principe de l'algorithme de parcours en largeur du graphe d'un automate fini exposŽ en cours.\end{question}\begin{question}En vous inspirant de cet algorithme, proposez un algorithme de calcul de $\lambda(L)$.\end{question}\begin{question}Dans le m�me esprit, proposez un algorithme de calcul de $\mu(L)$.\end{question}\begin{question}Proposez un algorithme dŽterminant un mot de $L$ de longueur $\mu(L)$, lorsque ce langage n'est pas vide.\end{question}\begin{question}Proposez un algorithme dŽterminant l'ensemble des mots de $L$ de longueur $\mu(L)$, lorsque ce langage n'est pas vide. Que pouvez-vous dire de son cožt dans le pire des cas?\end{question}\endinput