\documentclass{tp-caml}


\tp{
  title={Automates d'arbres},
  date={Vendredi 14 mars 2014},
  class=MP
}

\begin{document}

Les automates d'arbres sont une extension des automates classiques
(qui travaillent sur des chaînes de caractères) aux arbres. Il existe
plusieurs variantes d'automates travaillant sur les arbres mais nous
allons nous intéresser à la variante "ascendante binaire" qui ne
s'occupe que des arbres binaires où les nœuds sont annotés par des
labels.


Un automate d'arbre est défini par le quadruplet $(Q,F,i,\Delta)$ :
\begin{itemize}
\item $Q$ est l'ensemble des états de l'automate
\item $F\subset Q$ est l'ensemble des états finaux
\item $i$ est l'état initial (l'état des feuilles donc)
\item $\Delta\subset Q\times \mbox{Label} \times Q\rightarrow Q$ est
  la fonction de transition. Ici on considère un automate déterministe
  et complet donc elle prend deux états (associés au nœud de gauche et
  de droite), un label (celui du nœud) et renvoie un état (celui
  associé au nœud)
\end{itemize}


\begin{corpus}

\section{Reconnaissance par automate d'arbre déterministe}

\subsection{Arbres}

On pose tout d'abord le type d'arbre suivant :

\begin{caml}
    type arbre = 
                  Feuille 
                 |  Noeud of arbre*string*arbre
    ;;
\end{caml}

Un exemple de tel arbre où les nœuds sont étiquetés "Rouge" ou "Noir" :

\begin{caml}
let a = 
  Noeud(
   Noeud(Feuille,"Rouge",Feuille),
   "Rouge",
   Noeud(
      Feuille,
      Noir,
      Noeud(Feuille,"Rouge",Feuille)
      )
)
\end{caml}

\subsection{Automates}

\begin{caml}
  type automate = 
  { initial : int ; 
    labels : string array ;
    transition : int array array array ;
    final : bool array }
  ;;
\end{caml}

Dans notre automate, les états sont des \texttt{int} et les labels des
chaînes de caractères. Afin de pouvoir manipuler facilement les
labels, on veut une fonction qui associe à un label un entier.

\begin{exo}
Écrire une fonction \texttt{trad} qui associe à un label et à un
automate a, l'indice du label dans le tableau \texttt{a.labels}.
\end{exo}


\subsection{Reconnaissance}

\begin{exo}
Écrire une fonction qui prend en paramètre un arbre et un automate et
qui renvoie si l'arbre est reconnu par l'automate.
\end{exo}

\begin{exo}
Donner un automate qui teste si un nœud annoté "Rouge" est fils d'un
nœud lui aussi annoté "Rouge".
\end{exo}

\section{Automates non déterministe}

On relâche la contrainte de déterminisme. Le type de l'automate est
donc maintenant :

\begin{caml}
  type automate_nondeterministe = 
  { initial : int ; 
    labels : string array ;
    transition : int list array array array ;
    final : bool array }
  ;;
\end{caml}

\begin{exo}
Écrire une fonction qui prend un automate et un arbre et qui teste si
l'arbre est reconnu par l'automate. 
\end{exo}

\begin{exod}
Écrire une fonction qui prend un automate non déterministe et renvoie
un automate déterministe en utilisant l'algorithme des parties.
\end{exod}

\end{corpus}

\end{document}