summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-11-01 16:51:11 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-11-01 16:51:11 (GMT)
commit2b1a0ea899c9d7d08c0a48f8a663ccd4660f0250 (patch)
tree7f7a25e114f23ae38567af931efa46e104e0dec6 /notes-inf105.tex
parent82c0f39067062dd072fe9203b30bd92cac7c0cd4 (diff)
downloadinf105-2b1a0ea899c9d7d08c0a48f8a663ccd4660f0250.zip
inf105-2b1a0ea899c9d7d08c0a48f8a663ccd4660f0250.tar.gz
inf105-2b1a0ea899c9d7d08c0a48f8a663ccd4660f0250.tar.bz2
Primary terminology is "minimal" automaton, not "canonical".
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex10
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}