Remark on elimination of spontaneous transitions and automaton transpose.

1 files changed, 84 insertions, 33 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index df65faa..da90f2d 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1618,28 +1618,29 @@ des sommets accessibles depuis $q$ dans ce graphe).
 
 \begin{prop}\label{removal-of-epsilon-transitions}
 Soit $A = (Q,I,F,\delta)$ un εNFA sur un alphabet $\Sigma$.  Alors il
-existe un NFA $A' = (Q,I',F',\delta')$ (sur le même alphabet $\Sigma$)
-ayant le même ensemble d'états $Q$ que $A$ et qui soit équivalent
-à $A$ au sens où il reconnaît le même langage $L_{A'} = L_A$.  De
-plus, $A'$ se déduit algorithmiquement de $A$.
+existe un NFA $A^\S = (Q,I^\S,F^\S,\delta^\S)$ (sur le même
+alphabet $\Sigma$) ayant le même ensemble d'états $Q$ que $A$ et qui
+soit équivalent à $A$ au sens où il reconnaît le même langage
+$L_{A^\S} = L_A$.  De plus, $A^\S$ se déduit algorithmiquement de $A$.
 \end{prop}
 \begin{proof}
-On pose $I' = I$ (mêmes états initiaux).  L'idée est maintenant de
-faire une transition $(q,x,q') \in \delta'$ à chaque fois qu'on peut
+On pose $I^\S = I$ (mêmes états initiaux).  L'idée est maintenant de
+faire une transition $(q,x,q') \in \delta^\S$ à chaque fois qu'on peut
 atteindre $q'$ à partir de $q$ dans $A$ par une suite quelconque de
 ε-transitions suivie d'une unique transition étiquetée par $x$,
 autrement dit, $(q,\varepsilon,q^\sharp) \in \delta^*$ (c'est-à-dire
 $q^\sharp \in C(q)$) et $(q^\sharp,x,q') \in \delta$.
 
-On définit donc $\delta' \subseteq Q\times\Sigma\times Q'$ par
-$(q,x,q') \in \delta'$ lorsqu'il existe $q^\sharp \in C(q)$ tel que
+On définit donc $\delta^\S \subseteq Q\times\Sigma\times Q$ par
+$(q,x,q') \in \delta^\S$ lorsqu'il existe $q^\sharp \in C(q)$ tel que
 $(q^\sharp,x,q') \in \delta$ : autrement dit, pour créer les
-transitions $q\to q'$ dans $A'$, on parcourt tous les $q^\sharp \in
-C(q)$, et on crée une transition $q\to q'$ étiquetée par $x$ dans $A'$
-lorsqu'il existe une transition $q^\sharp\to q'$ étiquetée par ce $x$
-dans $A$.  De même, on définit $F' \subseteq Q$ comme l'ensemble des
-$q\in Q$ tels que $C(q) \cap F \neq \varnothing$, c'est-à-dire, qu'on
-peut atteindre un état final par une succession de ε-transitions.
+transitions $q\to q'$ dans $A^\S$, on parcourt tous les $q^\sharp \in
+C(q)$, et on crée une transition $q\to q'$ étiquetée par $x$
+dans $A^\S$ lorsqu'il existe une transition $q^\sharp\to q'$ étiquetée
+par ce $x$ dans $A$.  De même, on définit $F^\S \subseteq Q$ comme
+l'ensemble des $q\in Q$ tels que $C(q) \cap F \neq \varnothing$,
+c'est-à-dire, qu'on peut atteindre un état final par une succession de
+ε-transitions.
 
 Si on a un chemin $q_0 \to q_1 \to \cdots \to q_n$ dans $A$ menant
 d'un état initial $q_0 \in I$ à un état final $q_n \in F$ et
@@ -1651,22 +1652,23 @@ posons $j_0 = 0$.  Alors on passe de $q_{j_{i-1}}$ à $q_{j_i}$ par une
 succession de ε-transitions (de $q_{j_{i-1}}$ à $q_{(j_i)-1}$) suivie
 par une unique transition non spontanée : on a $q_{(j_i)-1} \in
 C(q_{j_{i-1}})$ et $(q_{(j_i)-1},t_{j_i},q_{j_i}) \in \delta$,
-autrement dit $(q_{j_{i-1}},t_{j_i},q_{j_i}) \in \delta'$ ; et comme
+autrement dit $(q_{j_{i-1}},t_{j_i},q_{j_i}) \in \delta^\S$ ; et comme
 le mot $w = t_1\cdots t_n$ s'écrit aussi $t_{j_1}\cdots t_{j_m}$, on a
-un chemin reliant $q_{j_0} = q_0 \in I$ à $q_{j_m} \in F'$ (puisque
+un chemin reliant $q_{j_0} = q_0 \in I$ à $q_{j_m} \in F^\S$ (puisque
 $q_n \in C(q_{j_m}) \cap F$).  Le mot $w$ supposé accepté par $A$ est
-donc accepté par $A'$.  La réciproque est analogue.
+donc accepté par $A^\S$.  La réciproque est analogue.
 \end{proof}
 
-\thingy On dit que le NFA $A'$ est obtenu en \textbf{supprimant les
+\thingy On dit que le NFA $A^\S$ est obtenu en \textbf{supprimant les
   ε-transitions} dans le εNFA $A$ lorsqu'il est obtenu par la
 procédure décrite dans la démonstration de cette proposition, et en
-supprimant tous les états non-initiaux de $A'$ auxquels n'aboutissent
-dans $A$ que des ε-transitions (ces états sont devenus inaccessibles
-dans $A'$).  Algorithmiquement, il s'agit donc, pour chaque état $q\in
-Q$ et chaque $q^\sharp$ dans la ε-femerture $C(q)$ de $q$, de créer
-une transition $q\to q'$ étiquetée par $x$ dans $A'$ pour chaque
-transition $q^\sharp\to q'$ étiquetée par $x$ dans $A$.
+supprimant tous les états non-initiaux de $A^\S$ auxquels
+n'aboutissent dans $A$ que des ε-transitions (ces états sont devenus
+inaccessibles dans $A^\S$).  Algorithmiquement, il s'agit donc, pour
+chaque état $q\in Q$ et chaque $q^\sharp$ dans la ε-femerture $C(q)$
+de $q$, de créer une transition $q\to q'$ étiquetée par $x$
+dans $A^\S$ pour chaque transition $q^\sharp\to q'$ étiquetée par $x$
+dans $A$.
 
 \thingy À titre d'exemple, supprimons les ε-transitions du εNFA $A$
 présenté en \ref{discussion-example5} : comme $C(0) = \{0,1,2\}$, on
@@ -1700,6 +1702,45 @@ l'automate suivant :
 incomplet, mais ce n'est pas un phénomène général : en général il faut
 s'attendre à obtenir un NFA.)
 
+{\footnotesize
+
+\thingy\textbf{Remarque :} La manière dont on a éliminé les
+ε-transitions ci-dessus consiste à remplacer \emph{une succession de
+  ε-transitions suivie d'une unique transition étiquetée $x$} par une
+transition étiquetée $x$ (et de même, on modifie les états finaux,
+mais pas les états initiaux).  Il existait un moyen « dual »
+d'éliminer les ε-transitions, à savoir remplacer \emph{une unique
+  transition étiquetée $x$ suivie d'une succession de ε-transitions}
+par une transition étiquetée $x$ (et de même, on modifie les états
+initiaux, mais pas les états finaux).  Autrement dit, la construction
+$A \mapsto A^\S$ décrite en \ref{removal-of-epsilon-transitions}
+définit $(q,x,q') \in \delta^\S$ lorsqu'il existe $q^\sharp \in C(q)$
+tel que $(q^\sharp,x,q') \in \delta$, et $I^\S=I$ et $F^\S$ comme
+l'ensemble des états $q$ tels que $C(q) \cap F \neq \varnothing$ ; la
+construction « duale » $A \mapsto A^\P$ consiste à poser $(q,x,q') \in
+\delta^\P$ lorsqu'il existe $q^{\flat\prime} \in C(q)$ tel que
+$(q,x,q^{\flat\prime}) \in \delta$, et $F^\P=F$ et $I^\P$ comme la
+réunion des $C(q)$ pour tout $q\in I$.
+
+Ces deux manières d'éliminer les ε-transitions donnent des NFA
+équivalents.  En fait, on peut passer de l'une à l'autre en utilisant
+la définition de l'automate transposé $A^{\mathsf{R}}$ présentée
+en \ref{nfa-mirror} plus bas (et qui consiste simplement à inverser le
+sens de toutes les flèches de l'automate) : si on inverse les flèches,
+qu'on élimine les ε-transitions à la manière décrite
+en \ref{removal-of-epsilon-transitions}, et qu'on inverse de nouveau
+les flèches, on obtient l'élimination « duale », autrement dit, $A^\P
+= ((A^{\mathsf{R}})^\S)^{\mathsf{R}}$.
+
+L'une ou l'autre manière d'éliminer les ε-transitions était possible,
+mais il vaut mieux ne pas les mélanger.  C'est pour cette raison qu'on
+a fait un choix en \ref{removal-of-epsilon-transitions} ; la présente
+remarque a principalement pour objectif d'expliquer la raison d'une
+perte de symétrie (notamment entre états initiaux et finaux) dans ce
+choix.
+
+\par}
+
 
 \section{Langages reconnaissables et langages rationnels}
 
@@ -1798,17 +1839,27 @@ Si $L$ est un langage reconnaissable sur un alphabet $\Sigma$, alors
 le langage miroir (cf. \ref{definition-mirror-language})
 $L^{\mathsf{R}}$ de $L$ est reconnaissable ; de plus, un NFA ou εNFA
 reconnaissant l'un se déduit algorithmiquement d'un NFA ou εNFA
-reconnaissant l'autre.
+reconnaissant l'autre : il s'agit simplement d'inverser le sens de
+toutes les flèches (y compris celles qui marquent les états initiaux
+et finaux).
 \end{prop}
+
+L'automate ainsi construit en inversant toutes les flèches d'un
+automate $A$ (la définition précise est donnée dans la démonstration
+qui suit) et qui reconnaît le langage miroir de celui reconnu par $A$
+peut s'appeller automate \textbf{transposé} $A^{\mathsf{R}}$ de $A$.
+
 \begin{proof}
 Par hypothèse, il existe un εNFA ou un NFA $A = (Q,I,F,\delta)$ tel
-que $L = L_A$.  Considérons l'automate $A'$ de même type défini par
-l'ensemble d'états $Q' = Q$ et inversant toutes les flèches de $A$,
-c'est-à-dire $I' = F$ et $F' = I$ et $(q,t,q') \in \delta'$ si et
-seulement si $(q',t,q) \in \delta$.  Un chemin existe dans $A'$ si et
-seulement si le même chemin inversé existe dans $A$, ce qui montre
-qu'un mot appartient à $L_{A'}$ si et seulement si son miroir
-appartient à $L_A$.
+que $L = L_A$.  Considérons l'automate $A^{\mathsf{R}}$ de même type
+défini par l'ensemble d'états $Q^{\mathsf{R}} = Q$ et inversant toutes
+les flèches de $A$, c'est-à-dire $I^{\mathsf{R}} = F$ et
+$F^{\mathsf{R}} = I$ et $(q,t,q') \in \delta^{\mathsf{R}}$ si et
+seulement si $(q^{\mathsf{R}},t,q) \in \delta$.  Un chemin existe dans
+$A^{\mathsf{R}}$ si et seulement si le même chemin inversé existe
+dans $A$, ce qui montre qu'un mot appartient à $L_{A^{\mathsf{R}}}$ si
+et seulement si son miroir appartient à $L_A$.  On a donc bien
+$L_{A^{\mathsf{R}}}=L^{\mathsf{R}}$, langage miroir de $L$.
 \end{proof}
 
 \thingy Alors que les constructions du complémentaire et de
@@ -1817,7 +1868,7 @@ langage miroir s'effectue naturellement sur les NFA.  (On peut, bien
 sûr, considérer un DFA comme un NFA particulier, et effectuer dessus
 l'opération d'inversion des flèches qu'on vient de décrire, mais en
 général on n'obtiendra pas un DFA, seulement un NFA ; les NFA dont
-l'inversion des flèches est déterministe — c'est-à-dire tels que, pour
+l'automate transposé est déterministe — c'est-à-dire tels que, pour
 chaque état $q$ et chaque lettre $x$, il existe une unique arête
 aboutissant à $q$ et étiquetée par $x$ — sont parfois dits
 « co-déterministes ».)