summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex52
1 files changed, 30 insertions, 22 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 86a9d53..b56b958 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1229,7 +1229,7 @@ servent à ancrer l'expression au début et à la fin de la chaîne
respectivement : c'est-à-dire que rechercher « \texttt{a} » recherche
un \texttt{a} quelconque à l'intérieur de la chaîne donnée, rechercher
« \texttt{\char"5E\relax a} » demande que le \texttt{a} soit au début
-de la chaîne donnée rechercher « \texttt{a\char"24} » demande que le
+de la chaîne donnée, rechercher « \texttt{a\char"24} » demande que le
\texttt{a} soit à la fin de la chaîne donnée, et rechercher
« \texttt{\char"5E\relax a\char"24} » demande que la chaîne donnée
soit exactement \texttt{a} (cet exemple n'est donc pas très utile,
@@ -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}