Moore's algorithm (further description).

1 files changed, 33 insertions, 3 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index e027205..7c10b3f 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2396,8 +2396,8 @@ Soit $L$ un langage.  Pour $w\in \Sigma^*$, notons $w^{-1} L := \{t
 \in \Sigma^* : wt \in L\}$ (autrement dit, l'ensemble des mots qu'on
 peut concaténer à $w$ pour obtenir un mot de $L$).  Considérons la
 relation d'équivalence $\equiv$ sur $\Sigma^*$ définie par $u \equiv
-v$ si et seulement si $u^{-1}L = v^{-1}L$ (ce qui signifie, si on
-préfère, que $\forall t\in \Sigma^*\,((ut\in L) \liff (vt \in L))$).
+v$ si et seulement si $u^{-1}L = v^{-1}L$ ; ce qui signifie, si on
+préfère, que $\forall t\in \Sigma^*\,((ut\in L) \liff (vt \in L))$.
 
 Alors :
 \begin{itemize}
@@ -2484,7 +2484,7 @@ partir d'une relation d'équivalence, mais cette démonstration n'est
 pas algorithmique : on va voir comment on peut le construire de fącon
 algorithmique à partir d'un DFA quelconque qui reconnaît $L$.
 
-\begin{prop}
+\begin{prop}\label{dfa-minimization}
 Soit $B = (Q_B, q_{0,B}, F_B, \delta_B)$ un DFA (complet !)
 reconnaissant un langage $L$, et dont tous les états sont accessibles
 (cf. \ref{definition-dfa-accessible-state}).  Alors l'automate
@@ -2561,6 +2561,36 @@ cas la dernière relation calculée est la relation recherchée $(\equiv)
 chaque classe d'équivalence pour $\equiv$.
 \end{proof}
 
+\thingy L'algorithme décrit par la proposition \ref{dfa-minimization}
+porte le nom d'algorithme \textbf{de Moore} ou \textbf{de
+  minimisation} ou \textbf{de réduction}.  Voici comment on peut le
+mettre en œuvre de façon plus concrète :
+\begin{itemize}
+\item s'assurer qu'on a affaire à un DFA \underline{\emph{complet sans
+    état inaccessible}} (si nécessaire, déterminiser l'automate s'il
+  n'est pas déterministe, le compléter s'il est incomplet, et
+  supprimer les états inaccessibles s'il y en a) ;
+\item appeler $\Pi$ la partition des automates en deux classes : les
+  états finaux d'un côté, et les non-finaux de l'autre ;
+\item répéter l'opération suivante tant que la partition $\Pi$
+  change : pour chaque classe $C$ de $\Pi$ et chaque lettre $x \in
+  \Sigma$, s'il existe deux états $q,q' \in C$ tels que $\delta(q,x)$
+  et $\delta(q',x)$ ne tombent pas dans la même classe de $\Pi$,
+  séparer cette classe $C$ selon la classe de $\delta(\tiret,x)$
+  (autrement dit, $q,q'$ restent dans la même classe pour la nouvelle
+  partition lorsqu'ils sont dans la même classe pour l'ancienne et que
+  pour chaque lettre $x$ leurs images $\delta(q,x)$ et $\delta(q',x)$
+  sont aussi dans la même classe) ;
+\item si $\Pi$ est la (dernière) partition ainsi obtenue, l'ensemble
+  des états de l'automate construit est l'ensemble des classes
+  de $\Pi$, les états finaux sont les classes qui contiennent un état
+  final (ils sont alors forcément tous finaux), et la fonction de
+  transition est obtenue en prenant la fonction de transition sur un
+  représentant quelconque de la classe (la classe ne doit pas dépendre
+  du représentant).
+\end{itemize}
+
+
 
 %
 %