From 2b1a0ea899c9d7d08c0a48f8a663ccd4660f0250 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Wed, 1 Nov 2017 17:51:11 +0100
Subject: Primary terminology is "minimal" automaton, not "canonical".

---
 notes-inf105.tex | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

(limited to 'notes-inf105.tex')

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}
 
-- 
cgit v1.2.3

