diff options
| -rw-r--r-- | notes-inf105.tex | 26 |
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 |