\documentclass{tp-caml-2009}
\usepackage{algorithmic}
\usepackage{algorithm}
\tp{
  title=Travaillons sur les automates (suite),
  number=Septième,
  date=Jeudi 21 janvier 2010,
  class=MP
}



\begin{document}

\begin{abstract}
  On va poursuivre le travail de la séance précédente en
  commençant par un algorithme de déterminisation (notez que 
  si vous avez terminé le dernier sujet vous pouvez sauter
  cette partie). Dans la deuxième partie on s'attaquera à la 
  minimisation des automates.
\end{abstract}



\begin{corpus}
  
  % *************************************************************************
  \section{Déterminisation}

  On va ici s'intéresser à la procédure de déterminisation
  d'un automate. La technique utilisée sera, étant donné un 
  automate, de générer l'ensemble des parties de ses états,
  puis de construire l'automate qui a cet ensemble de parties
  pour ensemble d'états.

%  \subsection{Automates}

  On propose ici un type caml pour les automates mais vous
  pouvez aussi garder celui que vous avez choisi à la
  dernière séance.

  \begin{prototype}
    type 'a automate = {init:'a list; final:'a list; trans:('a * char * 'a) list}
  \end{prototype}

  \begin{question}
    Si ce n'est pas déjà fait, écrire une fonction qui renvoie
    l'ensemble d'états d'un automate et son alphabet.
    \begin{prototype}
      val states : 'a automate -> 'a list
      val alphabet : 'a automate -> char list
    \end{prototype}
  \end{question}

\begin{solution-caml}
let states a =
  List.fold_left 
    (fun states (s,c,t) -> insere s (insere t states))
    [] a.trans
\end{solution-caml}

\begin{question}
  Soit un ensemble d'états (une liste d'élément de type 
  quelconque). Écrire une fonction 
  \verb'powerset' qui construit l'\emph{ensemble} des 
  sous-ensembles de cet ensemble.
  \begin{prototype}
    val powerset : 'a list -> 'a list list
  \end{prototype}
\end{question}

\begin{solution-caml}
let rec powerset = function
  | [] -> [[]]
  | a :: s -> 
      let t = powerset s
      in List.fold_left (fun l x -> insere (insere a x) l) t t
\end{solution-caml}

\begin{question}
  Écrire une fonction qui renvoie l'automate des parties d'un
  automate passé en argument. Vous pouvez tester cette fonction
  sur les exemples d'automates de la séance dernière.
  \begin{prototype}
    val determinize : 'a automate -> 'a list automate
  \end{prototype}
\end{question}

\begin{solution-caml}
let determinize auto =
  let stat = powerset (states auto) in
  let final = List.fold_left
     (fun f s -> 
       if List.exists (fun x -> appartient x auto.final) s
       then insere s f else f) [] stat in
  let trans = List.fold_left
    (fun t s ->
       List.fold_left 
        (fun t a ->
           insere (s,a,step auto a s) t)
	 t (alphabet auto)
    ) [] stat 
  in {init=[auto.init];final=final;
      trans=trans} 
\end{solution-caml}

\section{Minimisation}

La minimisation de l'automate s'effectue en calculant les
classes d'équivalence des états. Dans la suite, nous
manipulerons des automates déterministes.
Deux états $p$ et $q$ sont \emph{équivalents} si leur langages 
associés sont les mêmes. Formellement :
\[ p \sim q \Leftrightarrow 
\forall w \in \Sigma^\ast.\ \delta^\ast(p,w) \in F
\Leftrightarrow \delta^\ast(q,w) \in F \]
La relation $\sim$ est une relation d'équivalence.
%,on note $[q]$ l'ensemble des états équivalents à un état $q$.
Une tel relation doit vérifier les propriétés suivantes :
\begin{itemize}
\item $p \sim q \Rightarrow (p\in F \Leftrightarrow q\in F)$
\item $p \sim q \Rightarrow \forall a \in \Sigma.\ \delta(
  p,a) \sim \delta(q,a)$
\end{itemize}

Pour calculer les classes d'équivalence, on procède par 
raffinements successifs.
\begin{itemize}
\item on sépare les états finaux des états non-finaux
\item dans chaque classe on sépare les états dont les 
  images par la fonction de transition en une étape ne sont pas
  équivalentes
\item on répète l'étape précédente jusqu'à ce que le nombre
  de classe d'équivalence ne bouge plus
\end{itemize}

\begin{question}
  Étant donné un automate déterministe, un alphabet (supposé être
  celui de l'automate), et un état de cet automate, écrire une
  fonction qui renvoie \emph{dans l'ordre} les images de cet 
  état par les différentes lettres de l'alphabet.
  \begin{prototype}
    val image : 'a automate -> char list -> 'a -> 'a list
  \end{prototype}
\end{question}

\begin{solution-caml}
let image auto alpha stat =
  List.map (fun a -> let x :: [] = delta auto stat a in x) alpha
\end{solution-caml}

\begin{question}
  On représente les relations d'équivalence comme une liste de
  listes d'états (correspondant à une partition de l'ensemble
  d'états en classes d'équivalence).
  Écrire une fonction \lstinline|classe| tel que deux états ait
  la même image si et seulement si ils sont équivalents.
  \begin{prototype}
    val classe : 'a list list -> 'a -> int
  \end{prototype}
\end{question}

\begin{solution-caml}
let classe part s = 
  let rec aux i = function
    | a :: l -> if List.mem s a then i else aux (i+1) l
  in aux 0 part
\end{solution-caml}

\begin{question}
Étant donnée une relation d'équivalence et une fonction 
\lstinline|f|, écrire une fonction caml qui sépare les éléments
d'une même classe ayant des images par \lstinline|f|
différentes.
  \begin{prototype}
    val refine : 'a list list -> ('a -> 'b) -> 'a list list
  \end{prototype}
\end{question}

\begin{solution-caml}
let refine part f = 
  let rec aux cl = match cl with
    | [] -> []
    | a :: s -> 
	let l = aux s in
	let fa = f a in
	let rec aux2 = function 
	  | [] -> [[a]]
	  | x :: s -> 
	      if f (List.hd x) = fa
	      then (a :: x) :: s 
	      else x :: (aux2 s)
	in aux2 l
  in List.fold_left (fun l cl -> aux cl @ l) [] part
\end{solution-caml}

\begin{question}
  Écrire une fonction qui renvoie les classes d'équivalence
  des états d'un automate.
  \begin{prototype}
    val equivalence : 'a automate -> 'a list list
  \end{prototype}
\end{question}
\begin{solution-caml}
let equivalence auto = 
  let alpha = alphabet auto in
  let part = 
    (auto.final) ::
      (List.filter (fun x -> not (List.mem x auto.final))
	 (states auto)) :: []
  in
  let rec aux part = 
    let npart = 
      refine part
	(fun x -> List.map (classe part) 
	   (image auto alpha x))
    in 
      if List.length npart = List.length part 
      then part 
      else aux npart
  in aux part
\end{solution-caml}

Pour minimiser un automate déterministe, on procède en 
supprimant les états non atteignables et en construisant 
un automate dont les états sont les classes d'équivalence du
premier.

\begin{question}
  Écrire une fonction qui calcule les états accessibles d'un
  automate déterministe.
  \begin{prototype}
    val accessible : 'a automate -> 'a list
  \end{prototype}
\end{question}
\begin{solution-caml}
let accessible auto = 
  let init = auto.init in
  let alpha = alphabet auto in
  let step sl = 
    List.fold_left 
      (fun l s -> 
         List.fold_left
	   (fun l a ->
	     insere (List.hd(delta auto s a)) l
	   ) l alpha) [] sl
  in
  let rec aux accu ns =
    if ns = [] then accu
    else aux (ns @ accu) (step ns)
  in aux [] init
\end{solution-caml}

\begin{question}
  Écrire une fonction qui minimise un automate déterministe.
  \begin{prototype}
    val minimize : 'a automate -> int automate
  \end{prototype}
\end{question}
\begin{solution-caml}
let minimize auto = 
  let access = accessible auto in
  let final = 
    List.filter (fun x -> List.mem x access) auto.final
  in
  let trans = 
    List.filter (fun (p,a,q) -> List.mem p access) auto.trans
  in 
  let auto = 
    { init = auto.init ; 
      final = final;
      trans = trans
    }
  in 

  let part = equivalence auto in
  let alpha = alphabet auto in 
  let trans = 
    List.fold_left 
      (fun t c -> 
         let i = image auto alpha (List.hd c) in
	   List.map2 
	     (fun leter st -> (classe part (List.hd c),leter,classe part st))
	     alpha i
	   @ t
      ) [] part
  in
  let final = List.fold_left (fun l s -> insere (classe part s) l) [] auto.final
  in
    {init=[classe part (List.hd auto.init)];
     final=final;
     trans=trans} 
\end{solution-caml}

Pour comparer les langages reconnus par des automates, on 
construit les automates minimaux associés, et on regarde si il
existe une bijection entre les états de ces automates minimaux
compatible avec les fonctions de transition.

\begin{question}
  Écrire une fonction qui dit si deux automates reconnaissent le
  même langage. 
  \begin{prototype}
    val eq : 'a automate -> 'b automate -> bool
  \end{prototype}
\end{question}
\begin{solution-caml}
exception No

let eq auto1 auto2 = 
  try
    (
      let a1,a2 = minimize auto1, minimize auto2 in
      let alpha = alphabet a1 in
	if not (egal alpha (alphabet a2)) then raise No;
      let l,m = List.length (states a1), List.length (states a2) in
	if not (l = m) then raise No
	else
	  let tab = Array.make l None in
	  let eq s t = match tab.(s) with
	    | None -> tab.(s) <- Some t
	    | Some x -> if not (x = t) then raise No
	  in 
	  let () = eq (List.hd a1.init) (List.hd a2.init) in
	  let rec aux visited to_visit =
	    if to_visit = [] then ()
	    else
	      aux (to_visit @ visited) 
		(List.fold_left
		   (fun tv x ->
		      match tab.(x) with
			  Some y -> 
			    List.fold_left2
			      (fun tv x y -> eq x y ; 
				 if List.mem x visited
				   || List.mem x to_visit
				 then tv
				 else x :: tv)
			      tv (image a1 alpha x) (image a2 alpha y)
		   ) [] to_visit
		)
	  in aux [] a1.init;
	    true
    ) 
  with No -> false
\end{solution-caml}


\end{corpus}

\end{document}



%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
