diff options
| -rw-r--r-- | notes-inf105.tex | 10 |
1 files changed, 5 insertions, 5 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 60881fb..b70fc0f 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -3989,7 +3989,7 @@ algorithmique à partir d'un DFA quelconque qui reconnaît $L$. 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 +minimal $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 \[ @@ -4009,7 +4009,7 @@ 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ù +l'automate minimal 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 @@ -4020,11 +4020,11 @@ $q \equiv q'$ si et seulement si $\delta^*_B(q,t)\in F_B \liff $\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)$ +de l'automate minimal 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 +l'automate minimal en fusionnant chaque classe d'équivalence pour $\equiv$. Montrons maintenant comment on peut construre $\equiv$ @@ -4058,7 +4058,7 @@ 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 += ({\equiv_i})$, et l'automate minimal $A$ s'obtient en fusionnant chaque classe d'équivalence pour $\equiv$. \end{proof} |