summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-30 19:57:59 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-11-30 19:57:59 (GMT)
commit6d822f738fa288008bca407dc10d4ed3e1012863 (patch)
tree786ea6eafe8f5a4d70b157c9b9769e0350962d67 /notes-inf105.tex
parent8d7c77c96249f7e7c0f167b9710b59efa5662010 (diff)
downloadinf105-6d822f738fa288008bca407dc10d4ed3e1012863.zip
inf105-6d822f738fa288008bca407dc10d4ed3e1012863.tar.gz
inf105-6d822f738fa288008bca407dc10d4ed3e1012863.tar.bz2
The Myhill-Nerode theorem.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex87
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}
+
+
%
%
%