NFAs with spontaneous transitions: equivalence.

2 files changed, 123 insertions, 9 deletions

diff --git a/figs/example5ne.dot b/figs/example5ne.dot
new file mode 100644
index 0000000..8371593
--- /dev/null
+++ b/figs/example5ne.dot
@@ -0,0 +1,14 @@
+digraph example5ne {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	q0 [style="state,initial",label="0"];
+	q1 [style="state",label="1"];
+	q2 [style="state,final",label="2"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q0 [label="a",topath="loop above"];
+	q0 -> q1 [label="b"];
+	q1 -> q1 [label="b",topath="loop above"];
+	q1 -> q2 [label="c"];
+	q2 -> q2 [label="c",topath="loop above"];
+	q0 -> q2 [label="c"];
+}
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 1c9646f..1098ac5 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -918,6 +918,9 @@ en \ref{definition-dfa} est que la fonction $\delta$ est partielle, ce
 qui signifie qu'elle n'est pas obligatoirement définie sur tout couple
 $(q,x) \in Q\times\Sigma$.
 
+(Un DFA est considéré comme un DFAI particulier où la fonction de
+transition $\delta$ se trouve être définie partout.)
+
 \thingy Graphiquement, on représente un DFAI comme un DFA, à la
 différence près que pour chaque $q\in Q$ et chaque $x\in \Sigma$, il y
 a maintenant \emph{au plus une} (et non plus exactement une) arête
@@ -1095,6 +1098,13 @@ initiaux, et de même, au lieu qu'un état $q$ et un symbole $x$
 déterminent un unique état $q' = \delta(q,x)$, on a maintenant affaire
 à un ensemble quelconque de triplets $(q,x,q')$.
 
+\thingy Un DFAI (ou \textit{a fortiori} un DFA) est considéré comme un
+NFA particulier en définissant l'ensemble des états initiaux du NFA
+comme $I_{\mathrm{NFA}} = \{q_{0,\mathrm{DFAI}}\}$ et en définissant
+la relation de transition du NFA comme le graphe de la fonction de
+transition du DFAI (c'est-à-dire $(q,x,q') \in \delta_{\mathrm{NFA}}$
+lorsque $\delta_{\mathrm{DFAI}}(q,x)$ est défini et vaut $q'$).
+
 \thingy Graphiquement, on représente un NFA comme un DFA comme un
 graphe orienté dont les nœuds sont les éléments de $Q$, et où on place
 une arête étiquetée $x$ de $q$ vers $q'$ pour chaque triplet $(q,x,q')
@@ -1343,6 +1353,8 @@ autrement, \emph{un automate qui possède des $\varepsilon$-transitions
 
 La représentation graphique des εNFA est évidente (on utilisera le
 symbole « $\varepsilon$ » pour étiqueter les transitions spontanées).
+Un NFA est considéré comme un εNFA particulier pour lequel il n'y a
+pas de ε-transition.
 
 \thingy Un εNFA accepte un mot $w$ lorsqu'il existe un chemin
 conduisant d'un état initial à un état final et dont les arêtes sont
@@ -1432,15 +1444,103 @@ nombre quelconque de $b$ suivi d'un nombre quelconque de $c$, ou, si
 on préfère, le langage désigné par l'expression rationnelle
 $a{*}b{*}c{*}$.
 
-\thingy Si $q$ est un état d'un εNFA, on appelle
-\textbf{$\varepsilon$-fermeture} de $q$ l'ensemble des états $q'$ (y
-compris $q$ lui-même) accessibles depuis $q$ par une succession
-quelconque de ε-transitions, c'est-à-dire, si on veut, $\{q'\in Q
-:\penalty0 (q,\varepsilon,q') \in\delta^*\}$.  On notera
-temporairement $C(q)$ cet ensemble.  (Par exemple, dans
-l'exemple \ref{discussion-example5} ci-dessus, on a $C(0) = \{0,1,2\}$
-et $C(1) = \{1,2\}$ et $C(2) = \{2\}$.  Dans tout NFA sans
-ε-transitions, on a $C(q) = \{q\}$ pour tout état $q$.)
+\thingy Si $q$ est un état d'un εNFA, on appelle \textbf{ε-fermeture}
+de $q$ l'ensemble des états $q'$ (y compris $q$ lui-même) accessibles
+depuis $q$ par une succession quelconque de ε-transitions,
+c'est-à-dire, si on veut, $\{q'\in Q :\penalty0 (q,\varepsilon,q')
+\in\delta^*\}$.  On notera temporairement $C(q)$ cet ensemble.  (Par
+exemple, dans l'exemple \ref{discussion-example5} ci-dessus, on a
+$C(0) = \{0,1,2\}$ et $C(1) = \{1,2\}$ et $C(2) = \{2\}$.  Dans tout
+NFA sans ε-transitions, on a $C(q) = \{q\}$ pour tout état $q$.)
+
+Il est clair qu'on peut calculer algorithmiquement $C(q)$ (par exemple
+par un algorithme de Dijkstra sur le graphe dont l'ensemble des
+sommets est $Q$ et l'ensemble des arêtes est l'ensemble des
+ε-transitions de $A$ : la ε-fermeture $C(q)$ est simplement l'ensemble
+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$.
+\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
+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
+$(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.
+
+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
+étiquetées par $t_1,\ldots,t_n \in (\Sigma\cup\{\varepsilon\})$
+(c'est-à-dire $(q_{i-1},t_i,q_i) \in \delta$), appelons
+$j_1<\ldots<j_m$ les indices tels que $t_j \in\Sigma$, autrement dit,
+tels que la transition $q_{j-1} \to q_j$ ne soit pas spontanée, et
+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
+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
+$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.
+\end{proof}
+
+\thingy On dit que le NFA $A'$ 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.
+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$.
+
+\thingy À titre d'exemple, supprimons les ε-transitions du εNFA $A$
+présenté en \ref{discussion-example5} : comme $C(0) = \{0,1,2\}$, on
+fait partir de $0$ toutes les transitions partant d'un des états
+$0,1,2$ et étiquetées par une lettre, et de même, comme $C(1) =
+\{1,2\}$, on fait pratir de $1$ toutes les transitions partant d'un
+des états $1,2$ et étiquetées par une lettre.  On obtient finalement
+l'automate suivant :
+
+\begin{center}
+%%% begin example5ne %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (97bp,48bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
+  \node (q2) at (176bp,18bp) [draw,circle,state,final] {$2$};
+  \draw [->] (q0) ..controls (47.643bp,10.917bp) and (64.2bp,7.4655bp)  .. (79bp,6bp) .. controls (94.922bp,4.4234bp) and (99.078bp,4.4234bp)  .. (115bp,6bp) .. controls (125.98bp,7.0877bp) and (137.94bp,9.2693bp)  .. node[auto] {$c$} (q2);
+  \draw [->] (q2) to[loop above] node[auto] {$c$} (q2);
+  \draw [->] (q0) to[loop above] node[auto] {$a$} (q0);
+  \draw [->] (q1) to[loop above] node[auto] {$b$} (q1);
+  \draw [->] (q1) ..controls (124.28bp,37.762bp) and (137.94bp,32.438bp)  .. node[auto] {$c$} (q2);
+  \draw [->] (q0) ..controls (45.279bp,28.238bp) and (58.943bp,33.562bp)  .. node[auto] {$b$} (q1);
+%
+\end{tikzpicture}
+
+%%% end example5ne %%%
+\end{center}
+
+(Sur cet exemple précis, on obtient un automate déterministe
+incomplet, mais ce n'est pas un phénomène général : en général il faut
+s'attendre à obtenir un NFA.)
+
 
 %
 %