\begin{question}\label{def-alg-lambda}Ceci a ŽtŽ vu en TD:\begin{itemize} \item $\lambda(\emptyset) = \vvv$;  \item $\lambda(\mv) = \fff$;  \item $\lambda(x) = \fff$ pour toute lettre $x$;  \item $\lambda(e+e') = \lambda(e) \mbox{ et } \lambda(e')$;  \item $\lambda(e \cdot e') = \lambda(e) \mbox{ ou } \lambda(e')$;  \item $\lambda(e^*) = \fff$.\end{itemize}\end{question}\begin{question}Il suffit de transcrire la spŽcification prŽcŽdente: \begin{programme}\begin{verbatim}let rec lambda = function  | Vide -> true  | Epsilon | Lettre _ -> false  | Union(e,e') -> lambda e & lambda e'  | Produit(e,e') -> lambda e || lambda e'  | Etoile _ -> false ;;\end{verbatim}\end{programme}\end{question}\begin{question}Le travail est plus compliquŽ qu'ˆ la question~\ref{def-alg-lambda}:\begin{itemize} \item $\mu(\emptyset) = -°$;  \item $\mu(\mv) = 0$;  \item $\mu(x) = 1$ pour toute lettre $x$;  \item $\mu(e+e') = \mu(e)$ si $\mu(e') = -°$;  \item $\mu(e+e') = \mu(e')$ si $\mu(e) = -°$;  \item $\mu(e+e') = \min\bigl( \mu(e),\mu(e') \bigr)$ dans les autres cas;  \item $\mu(e \cdot e') = -°$ si $\mu(e) = -°$ ou $\mu(e') = -°$;  \item $\mu(e \cdot e') = \mu(e) + \mu(e')$ sinon;  \item $\mu(e^*) = 0$.\end{itemize}\end{question}\begin{question}Ici encore, on transcrit la spŽcification algŽbrique. Deux remarques: \begin{itemize} \item utiliser $\lambda$ pour tester si le langage dŽcrit par une sous-expression est vide serait une erreur, puisqu'il faudrait parcourir deux fois chaque sous-arbre, dans le pire des cas; ceci m�nerait ˆ un cožt exponentiel en la taille de l'expression; \item attention aux filtrages imbriquŽs: il faut parenthŽser tout \verb+match ... with+ qui est ˆ l'intŽrieur d'un autre \verb+match ... with+.\end{itemize}\begin{programme}\begin{verbatim}let rec mu = function  | Vide -> None  | Epsilon ->  Some 0  | Lettre _ -> Some 1  | Union(e,e') -> ( match (mu e,mu e') with    | None,None -> None    | None,Some x' -> Some x'    | Some x,None -> Some x    | Some x,Some x' -> Some(min x x')    ) | Produit(e,e') -> ( match (mu e,mu e') with    | None,_ | _,None -> None    | Some x,Some x' -> Some(x+x')    ) | Etoile _ -> Some 0 ;;\end{verbatim}\end{programme}\end{question}\begin{question}Notons $E_0$ l'ensemble des Žtats initiaux; puis, pour $n\in\N$, notons $E_{n+1}$ la rŽunion de $E_n$ et de l'ensemble des Žtats que l'on peut atteindre par une transition partant d'un Žtat appartenant ˆ $E_n$. Cette suite croissante prend ses valeurs dans l'ensemble fini ${\cal P}(Q)$ donc elle stationne. On Žtablit que si $E_{n+1} = E_n$, alors la suite stationne ˆ partir du rang $n$ (voire plus t™t). Si $|I|³1$, la suite stationne au plus tard ˆ partir du rang $|Q|-|I|$. Ceci nous fournit bien un algorithme.\end{question}\begin{question}Construisons la suite $(E_n)_{n\in\N}$ en nous arr�tant au premier des deux ŽvŽnements suivants:\begin{itemize} \item $E_n$ contient un Žtat final: alors $\lambda(L) = \fff$;  \item $E_{n+1} = E_n$: alors $\lambda(L) = \vvv$.\end{itemize}\end{question}\begin{question}M�me dŽmarche, c'est juste la conclusion qui change:\begin{itemize} \item $E_n$ contient un Žtat final: alors $\mu(L) = n$;  \item $E_{n+1} = E_n$: alors $\mu(L) = -°$.\end{itemize}\end{question}\begin{question}Nous supposons $L$ non vide. Notons $n_0$ le rang ˆ partir duquel la suite $(E_n)_{n\in\N}$ stationne: $n_0 = \mu(L)$. Choisissons $q_{n_0}\in E_{n_0}$: $q_{n_0}$ est final, et il existe $q_{n_0-1} \in E_{n_0-1}$ et $u_{n_0} \in \Alphabet$ tels que $q_{n-1} \donne{u_{n_0}} q_{n_0}$. Nous pouvons poursuivre ce parcours: pour chaque $k\in\IntervalleDiscret{1}{n}$, il existe $q_{k-1} \in E_{k-1}$ et $u_k \in \Alphabet$ tels que $q_{k-1} \donne{u_k} q_k$. Notons $u = u_1 u_2 \ldots u_n$. Alors $q_0 \donne{x} q_n$, et $q_0$ est un Žtat initial; donc $u$ est un mot de $L$ de longueur minimale.\end{question}\begin{panneau}Remarque: programmer le calcul de l'ensemble de mots de $L$ de longueur $\mu(L)$ est un exercice intŽressant; le cožt doit rester linŽaire par rapport ˆ la taille de l'expression rationnelle dŽcrivant $L$.\end{panneau}\begin{question}Notons ${\cal S}({\cal A},n)$ l'ensemble des mots de longueur $n$ du langage reconnu par l'automate dŽterministe complet ${\cal A} = (Q,\delta,i,F)$. Deux remarques: \smallskip\begin{itemize} \item ${\cal S}({\cal A},0)$ est vide ssi $i \notin F$;  \item ${\cal S}({\cal A},n+1)$ est la rŽunion des $|\Alphabet|$ langages $\{x\} \cdot {\cal S}({\cal A}_x,n)$ o� ${\cal A}_x = (Q,\delta,i \cdot x,F)$.\end{itemize}\noindentIl suffit donc de calculer $\mu(L)$, puis de construire la suite des ${\cal S}({\cal A},n)$ pour $n\in\IntervalleDiscret{0}{\mu(L)}$. Le dernier terme de cette suite est le langage cherchŽ. Le cožt est au moins Žgal au nombre de mots ˆ ŽnumŽrer, il peut donc �tre exponentiel en $\mu(L)$.\end{question}\endinput