Clarify which states need to be considered when doing state elimination.

1 files changed, 16 insertions, 10 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 0979013..2131cb3 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3641,16 +3641,22 @@ Symboliquement :
 \end{center}
 
 Cette transformation doit être effectuée \emph{simultanément pour
-  toute paire} $(q_1,q_2)$ d'états de $A$ pour laquelle
-$q_1\not\in\{q,q_\infty\}$ et $q_2\not\in\{q,q_0\}$ : pour chaque
-telle paire, on remplace l'étiquette de la transition $r_{12}$ entre
-eux par $(r_{12}|r_1(s){*}r_2)$.  Ceci ne change pas le fonctionnement
-de l'automate, car tout chemin dans $A$ peut être remplacé par un
-chemin dans $A'$ en effaçant simplement les $q$ (si on considère
-$q_1$ et $q_2$ les états avant un bloc de $q$ dans le chemin, on
-voit que le chemin $q_1 \to q \to q \to \cdots \to q \to q_2$ peut se
-transformer en $q_1 \to q_2$ en consommant un mot qui vérifie
-l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$).
+  toute paire}\footnote{Plutôt qu'examiner toutes les paires, on peut
+  se contenter d'examiner les cas où \emph{soit} il existe une
+  transition de $q_1$ vers $q_2$ \emph{soit} il existe à la fois une
+  transition de $q_1$ vers $q$ et une transition de $q$ vers $q_2$.
+  En revanche, insistons bien sur le fait que le cas où $q_1$ et $q_2$
+  coïncide doit être traité comme les autres.} $(q_1,q_2)$ d'états
+de $A$ pour laquelle $q_1\not\in\{q,q_\infty\}$ et
+$q_2\not\in\{q,q_0\}$ : pour chaque telle paire, on remplace
+l'étiquette de la transition $r_{12}$ entre eux par
+$(r_{12}|r_1(s){*}r_2)$.  Ceci ne change pas le fonctionnement de
+l'automate, car tout chemin dans $A$ peut être remplacé par un chemin
+dans $A'$ en effaçant simplement les $q$ (si on considère $q_1$ et
+$q_2$ les états avant un bloc de $q$ dans le chemin, on voit que le
+chemin $q_1 \to q \to q \to \cdots \to q \to q_2$ peut se transformer
+en $q_1 \to q_2$ en consommant un mot qui vérifie l'expression
+rationnelle $(r_{12}|r_1(s){*}r_2)$).
 
 En éliminant (dans n'importe quel ordre) tous les états autres que
 $q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant une unique