The Myhill-Nerode theorem.

1 files changed, 87 insertions, 0 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 7b31806..077fb5d 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2367,6 +2367,93 @@ suffit donc de prendre $i=0$ pour avoir une contradiction.
 \end{proof}
 
 
+\subsection{L'automate canonique, et la minimisation}
+
+\begin{thm}[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))$).
+
+Alors :
+\begin{itemize}
+\item le langage $L$ est rationnel si et seulement si la relation
+  d'équivalence $\equiv$ possède un nombre \emph{fini} $k$ de classes
+  d'équivalence,
+\item lorsque c'est le cas, il existe un DFA ayant $k$ états qui
+  reconnaît $L$, il est unique à renommage des
+  états\footnote{C'est-à-dire, si on préfère ce terme, isomorphisme
+    d'automates.} près, et il n'existe pas de DFA ayant $<k$ états qui
+  reconnaisse $L$.
+\end{itemize}
+\end{thm}
+\begin{proof}
+Supposons d'abord que l'ensemble $\Sigma^*/{\equiv}$ des classes
+d'équivalence pour $\equiv$ soit fini : appelons-le $Q$, et expliquons
+comment on peut construire un DFA reconnaissant $L$ et dont l'ensemble
+des états soit $Q$.  Notons $[u] := \{v \in \Sigma^* :\penalty-100
+u\equiv v\}$ pour la classe d'équivalence de $u$ pour $\equiv$.
+Posons $q_0 := [\varepsilon]$ la classe du mot vide.  Remarquons que
+si $u\equiv v$ (pour $u,v\in\Sigma^*$), alors on a $u\in L$ si et
+seulement si $v\in L$ (en effet, la définition de $\equiv$ est que
+$(ut\in L) \liff (vt \in L)$ pour tout $t$, et on applique ça
+à $t=\varepsilon$) : autrement dit, une classe $[u] \in Q$ est soit
+entièrement incluse dans $L$ soit disjointe de $L$ ; appelons $F$
+l'ensemble $\{[u] : u\in L\}$ des classes incluses dans $L$.  Enfin
+remarquons que si $u\equiv v$ (pour $u,v\in\Sigma^*$) et $x\in\Sigma$,
+on a encore $ux \equiv vx$ (en effet, $uxt \in L \liff vxt \in L$ pour
+tout $t\in L$) : il y a donc un sens à définir $\delta([u], x) =
+[ux]$.  On a ainsi fabriqué un automate fini $A = (Q,q_0,F,\delta)$.
+Vues les définitions de $q_0$ et $\delta$, il est clair que
+$\delta^*(q_0,w) = [w]$ pour cet automate, et vue la définition de
+$F$, on a $\delta^*(q_0,w) \in F$ si et seulement si $w\in L$.  Ceci
+montre bien que $A$ reconnaît le langage $L$.  On a donc prouvé que si
+$\Sigma^*/{\equiv}$ est fini, le langage $L$ est rationnel et même il
+existe un DFA ayant $k := \#(\Sigma^*/{\equiv})$ états qui le
+reconnaît.
+
+Supposons maintenant que $B = (Q_B, q_{0,B}, F_B, \delta_B)$ soit un
+DFA reconnaissant $L$.  Définissons une nouvelle relation
+d'équivalence $\mathrel{\equiv_B}$ sur $\Sigma^*$ par : $u
+\mathrel{\equiv_B} v$ si et seulement si $\delta_B^*(q_{0,B}, u) =
+\delta_B^*(q_{0,B}, v)$ (autrement dit, les mots $u$ et $v$ mettent
+l'automate $B$ dans le même état).  Si on a $u \mathrel{\equiv_B} v$,
+on a aussi $u \equiv v$ : en effet, pour tout $t\in L$ on a
+$\delta_B^*(q_{0,B}, ut) = \delta_B^*(q_{0,B}, vt)$, et notamment le
+membre de gauche appartient à $F_B$ si et seulement si le membre de
+droite y appartient, c'est-à-dire que $ut\in L \liff vt\in L$.  On
+vient donc de montrer que $u \mathrel{\equiv_B} v$ implique $u \equiv
+v$ (la relation $\equiv_B$ est \emph{plus fine} que $\equiv$) : si on
+préfère, chaque classe d'équivalence pour $\equiv$ est donc une
+réunion de classes d'équivalences pour $\equiv_B$.  Notamment, comme
+$\equiv_B$ a un nombre fini de classes d'équivalence (puisque
+$\delta_B^*(q_{0,B}, u)$ ne peut prendre qu'un nombre fini de valeurs,
+celles dans $Q_B$), il en va de même de $\equiv$, et plus précisément,
+comme $\equiv_B$ a au plus $\#Q_B$ classes d'équivalence, il en va de
+même de $\equiv$, c'est-à-dire $k \leq \#Q_B$.  Il n'existe donc pas
+de DFA ayant $<k$ états reconnaissant $L$.
+
+Enfin, si $B$ a $k$ états et reconnaît $L$, cela signifie que les deux
+relations $\equiv$ et $\equiv_B$ coïncident, et on définit une
+bijection $\psi$ entre le $Q = Q_A$ du paragraphe précédent et $Q_B$
+en associant à une classe $[w] \in Q$ l'état $\psi([w]) :=
+\delta_B^*(q_{0,B},w)$ (qui ne dépend que de la classe de $w$
+pour $\equiv_B$ et on vient de voir que c'est la classe de $w$
+modulo $\equiv$, c'est-à-dire $[w]$ : ceci est donc bien défini).
+Cette bijection $\psi$ vérifie $\psi(q_0) = \psi([\varepsilon]) =
+\delta_B^*(q_{0,B},\varepsilon) = q_{0,B}$ ; on a $[w] \in F$ si et
+seulement si $w\in L$, c'est-à-dire si et seulement si
+$\delta_B^*(q_{0,B},w) \in F_B$ autrement dit $\psi([w]) \in F_B$.  Et
+enfin, pour $w\in\Sigma^*$ et $x\in \Sigma$, on a $\psi(\delta([w],x))
+= \psi([wx]) = \delta_B^*(q_{0,B},wx) = \delta_B(\delta_B^*(q_0,w), x)
+= \delta_B(\psi([w]), x)$.  Bref, $\psi$ préserve l'état initial, les
+états finaux, et la relation de transition : c'est donc bien un
+isomorphisme d'automates (un renommage des états).
+\end{proof}
+
+
 %
 %
 %