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