\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}

\noindent
sp�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}

\noindent
Ce 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}

\noindent
sp�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