diff options
| -rw-r--r-- | notes-inf105.tex | 87 |
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} + + % % % |