Rewrite explanation on the state elimination algorithm to clarify which states are to be considered.printed-2022

1 files changed, 29 insertions, 21 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 86a9d53..9967dad 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3641,27 +3641,35 @@ Symboliquement :
 \end{tikzpicture}
 \end{center}
 
-Cette transformation doit être effectuée \emph{simultanément pour
-  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
-transition $(q_0,r,q_\infty)$, qui est donc essentiellement
+Pour éliminer l'état $q$, cette transformation doit être effectuée
+\emph{simultanément pour toute paire} $(q_1,q_2)$ d'états de $A$ (avec
+$q_1\not\in\{q,q_\infty\}$ et $q_2\not\in\{q,q_0\}$) pour laquelle il
+existe une transition de $q_1$ vers $q$ et une transition de
+$q$ vers $q_2$, \emph{y compris} s'il n'y avait pas déjà une
+transition de $q_1$ vers $q_2$, et \emph{y compris} si $q_1=q_2$ :
+pour \emph{chaque} telle paire, on remplace l'étiquette de la
+transition $r_{12}$ entre eux par $(r_{12}|r_1(s){*}r_2)$.  (On
+prendra garde aux cas particuliers suivants : si la transition de $q$
+vers lui-même n'existait pas, ce qui revient à prendre $s=\bot$, alors
+on remplace la transition $r_{12}$ par $(r_{12}|r_1 r_2)$ en vertu du
+fait que $(\bot){*}$ est équivalente à $\underline{\varepsilon}$ ; et
+si la transition de $q_1$ vers $q_2$ n'existait pas, ce qui revient à
+prendre $r_{12}=\bot$, alors on la crée avec l'étiquette
+$r_1(s){*}r_2$ ; et bien sûr, en combinant ces deux cas particuliers,
+s'il n'y avait ni transition de $q$ vers lui-même ni de
+$q_1$ vers $q_2$, on crée cette dernière avec l'étiquette $r_1 r_2$.)
+
+La transformation qui vient d'être décrite 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 (successivement dans n'importe quel ordre) tous les états
+autres que $q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant
+une unique transition $(q_0,r,q_\infty)$, qui est donc essentiellement
 l'expression rationnelle $r$.
 \end{proof}