Moore's algorithm.

1 files changed, 89 insertions, 2 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 077fb5d..a44d1ad 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -34,6 +34,7 @@
 \newtheorem{algo}[comcnt]{Algorithme}
 \renewcommand{\qedsymbol}{\smiley}
 %
+\newcommand{\limp}{\mathrel{\Longrightarrow}\relax}
 \newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
 %
 \DeclareUnicodeCharacter{00A0}{~}
@@ -2369,13 +2370,13 @@ suffit donc de prendre $i=0$ pour avoir une contradiction.
 
 \subsection{L'automate canonique, et la minimisation}
 
-\begin{thm}[Myhill-Nerode]
+\begin{thm}[Myhill-Nerode]\label{myhill-nerode}
 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))$).
+préfère, que $\forall t\in \Sigma^*\,((ut\in L) \liff (vt \in L))$).
 
 Alors :
 \begin{itemize}
@@ -2453,6 +2454,92 @@ enfin, pour $w\in\Sigma^*$ et $x\in \Sigma$, on a $\psi(\delta([w],x))
 isomorphisme d'automates (un renommage des états).
 \end{proof}
 
+\thingy Ce théorème affirme donc qu'il existe (à renommage des états
+près) un unique DFA ayant un nombre minimal d'états parmi ceux qui
+reconnaissent le langage rationnel $L$ : on l'appelle \textbf{automate
+  canonique} ou \textbf{automate minimal} du langage $L$.  La
+démonstration ci-dessus en donne une construction à 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}
+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
+canonique $A$ de $L$ peut s'obtenir en fusionnant dans $B$ chaque
+classe d'équivalence pour la relation d'équivalence $\equiv$ définie
+sur $Q_B$ par
+\[
+q \equiv q' \;\liff\; \forall t\in\Sigma^*\,(\delta^*_B(q,t)\in F_B \liff \delta^*_B(q',t)\in F_B)
+\]
+(Fusionner chaque classe d'équivalence signifie qu'on construit
+l'automate $A$ dont l'ensemble d'états est l'ensemble $Q_A :=
+Q_B/{\equiv}$ des classes d'équivalence, l'état initial $q_{0,A}$ est
+la classe $[q_{0,B}]$ de $q_{0,B}$ pour $\equiv$, les états finaux
+sont les classes contenant au moins un état final et qui d'ailleurs
+sont entièrement constituées d'états finaux, et la relation de
+transition est donnée par $\delta_A([q],x) = [\delta_B(q,x)]$ en
+notant $[q]$ la classe de $q$ pour $\equiv$.)
+
+De plus, cet automate $A$ (ou de façon équivalente, la
+relation $\equiv$) peut se déduire algorithmiquement de $B$.
+\end{prop}
+\begin{proof}
+On a vu dans le cours de la démonstration de \ref{myhill-nerode} que
+l'automate canonique a pour ensemble d'états $\Sigma^*/{\equiv_L}$ où
+$\equiv_L$ désigne la relation d'équivalence (alors notée $\equiv$)
+définie par $u \mathrel{\equiv_L} v$ lorsque $\forall t\in \Sigma^*
+((ut\in L) \liff (vt \in L))$.  Si $q,q' \in Q_B$, comme $q,q'$ sont
+accessibles, il existe $w,w'\in\Sigma^*$ tels que
+$\delta_B^*(q_{0,B},w) = q$ et $\delta_B^*(q_{0,B},w') = q'$ ; et on a
+$q \equiv q'$ si et seulement si $\delta^*_B(q,t)\in F_B \liff
+\delta^*_B(q',t)\in F_B$ pour tout $t\in\Sigma^*$, c'est-à-dire
+$\delta^*_B(q_{0,B},wt)\in F_B \liff \delta^*_B(q_{0,B},w't)\in F_B$,
+c'est-à-dire $wt\in L \liff w't\in L$, autrement dit, $w
+\mathrel{\equiv_L} w'$.  L'application $\varphi$ qui à un état $[w]_L$
+de l'automate canonique associe la classe de $\delta_B^*(q_{0,B},w)$
+pour $\equiv$ est donc une bijection, et comme dans la démonstration
+de \ref{myhill-nerode} on vérifie qu'elle préserve l'état initial, les
+états finaux, et la relation de transition.  On obtient donc bien
+l'automate canonique en fusionnant chaque classe d'équivalence
+pour $\equiv$.
+
+Montrons maintenant comment on peut construre $\equiv$
+algorithmiquement.  Pour cela, on va définir des relations
+d'équivalence $\equiv_i$ pour $i\in\mathbb{N}$ par
+\[
+q \mathrel{\equiv_i} q' \;\liff\; \forall t\, (|t|\leq i \limp (\delta^*_B(q,t)\in F_B \liff \delta^*_B(q',t)\in F_B))
+\]
+C'est-à-dire par récurrence
+\[
+\begin{aligned}
+q \mathrel{\equiv_0} q' \;&\liff\; (q\in F_B \liff q'\in F_B)\\
+q \mathrel{\equiv_{i+1}} q' \;&\liff\; (q\mathrel{\equiv_{i}}q' \hbox{~et~} \forall x\in\Sigma\,(\delta_B(q,x) \mathrel{\equiv_i} \delta_B(q',x)))\\
+\end{aligned}
+\]
+(la première équivalence vient de ce que $\delta^*_B(q,\varepsilon) =
+q$, et la seconde de ce que $\delta^*_B(q,xt) =
+\delta^*_B(\delta_B(q,x), t)$).
+
+Il est trivial que $q \mathrel{\equiv_{i+1}} q'$ implique $q
+\mathrel{\equiv_i} q'$, c'est-à-dire que $\equiv_{i+1}$ est plus fine
+que $\equiv_i$, mais $\equiv$ est plus fine que toutes, et comme elle
+n'a qu'un nombre fini de classes d'équivalence, le nombre de classes
+ne peut croître strictement qu'un nombre fini de fois, et il doit donc
+stationner : il existe $i$ tel que $({\equiv_{i+1}}) = ({\equiv_i})$,
+et à ce moment-là, la seconde équivalence de la récurrence montre que
+$({\equiv_j}) = ({\equiv_i})$ pour tout $j\geq i$ et donc $(\equiv) =
+({\equiv_i})$.
+
+On peut donc calculer $\equiv$ selon l'algorithme suivant : calculer
+$\equiv_0$, et par récurrence calculer les $\equiv_i$ jusqu'à ce que
+la relation ne change plus, $({\equiv_{i+1}}) = ({\equiv_i})$, auquel
+cas la dernière relation calculée est la relation recherchée $(\equiv)
+= ({\equiv_i})$, et l'automate canonique $A$ s'obtient en fusionnant
+chaque classe d'équivalence pour $\equiv$.
+\end{proof}
+
 
 %
 %