\documentclass{tp-caml}

\usepackage{tikz}

\tp{
  title={Automates},
  number=5ème,
  date=Vendredi 01 février 2012,
  class=MP
}

\begin{document}

\begin{abstract}
Voir \texttt{http://caml.inria.fr/pub/docs/manual-caml-light/} pour
des fonctions pratiques sur les listes.
\end{abstract}

\begin{corpus}

\section{Rappels}

\begin{exo}
Trouver ce que fait puis se familiariser avec les fonctions :
\begin{itemize}
\item mem
\item union
\item intersect
\item exists
\item it\_list
\end{itemize}
\end{exo}

\section{DFA}
On définit le type automate suivant :

\begin{caml}
type 'a automate = { initial : 'a ; 
                  transition : 'a -> char -> 'a ;
                  finaux : 'a list };;
\end{caml}

\begin{exo}
Trouver un automate déterministe qui reconnaît le langage
$L=aa(a+ba)^*ba$ sur l'alphabet ${a,b}$.
\end{exo}

\begin{exo}
Écrire la fonction \texttt{reconnaitre : automate -> char list -> bool}
qui détermine si l'automate donné reconnaît le mot fournit.
\end{exo}

\section{NDFA}

On change maintenant le type de l'automate en :

\begin{caml}
type 'a automate = { initiaux : 'a list ; transition : 'a -> char -> 'a list ;
  finaux : 'a list };;
\end{caml}

On note $\mathcal{R}_i(u)$ le fait que le mot $u$ soit reconnu à
partir d'un état $i$.

\begin{exo}
Utiliser la relation : $$\mathcal{R}_i(u.v) \Leftrightarrow \exists s ~|~ s \in \delta(i,u) \wedge
\mathcal{R}_s(v)$$ pour écrire une fonction qui reconnaît un mot avec un NDFA.
\end{exo}

\subsection*{Un meilleur algorithme}
\begin{exod}
Écrire une fonction qui calcule l'ensemble des états que l'on peut
obtenir depuis un état $i$ en lisant le mot $m$.
\end{exod}

\begin{exod}
En déduire une fonction qui, en temps polynomial, reconnaît si un mot
appartient au langage d'un automate non déterministe.
\end{exod}
\section{Exercices}

\begin{exo}
Écrire une fonction qui étant donné un automate qui reconnaît le
langage $\mathcal{L}$, renvoie l'automate qui reconnaît le langage
$\mathcal{L}^2 = \{uv | u,v \in \mathcal{L}\}$.
\end{exo}

\begin{exo}
Écrire une fonction qui étant donné un automate qui reconnaît le
langage $\mathcal{L}_1$ et un qui reconnaît $\mathcal{L}_2$ renvoie l'automate qui reconnaît le langage $\mathcal{L}_1\cap \mathcal{L}_2$
\end{exo}

\section{Expressions régulières}
\begin{exo}
Ajouter le support pour des $\epsilon$-transitions.
\end{exo}
On définit le type d'expressions régulières suivant :
\begin{caml}
type expression = 
| Etoile of expression
| Concat of expression*expression
| Lettre of char
| Union of expression*expression
| Vide
;;
\end{caml}

\begin{exod}
Compiler les expressions régulières en automates.
\textit{Commencer par compiler dans l'ordre : Lettre, Concat, Etoile, Vide}

\end{exod}
\end{corpus}


\end{document}