Clarification of how automata with spontaneous transitions work.

1 files changed, 22 insertions, 45 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 5bce718..ead466a 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1874,22 +1874,27 @@ 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
-étiquetées par les lettres de $w$ ou bien des $\varepsilon$ insérés à
-n'importe quel endroit et en n'importe quel nombre.  Autrement dit,
-$w$ est accepté lorsqu'\emph{il existe} $q_0,\ldots,q_n \in Q$ et
-$t_1,\ldots,t_n \in (\Sigma\cup\{\varepsilon\})$ tels que $q_0 \in I$
-et $q_n\in F$ et $(q_{i-1},t_i,q_i) \in \delta$ pour chaque $1\leq
-i\leq n$ et $w = t_1\cdots t_n$ (\emph{attention} : dans cette
-écriture, $t_1,\ldots,t_n$ ne sont pas forcément les lettres de $w$,
-certains des $t_i$ peuvent être le symbole $\varepsilon$, les lettres
-de $w$ sont obtenues en ignorant ces symboles).
-
-De façon plus intuitive, cela signifie que l'automate a la possibilité
-de passer spontanément, c'est-à-dire sans consommer de lettre, d'un
-état $q$ à un état $q'$, lorsque ces états sont reliés par une
-ε-transition.
+\thingy Intuitivement, les transitions spontanées signifient que
+l'automate a la possibilité de passer spontanément, c'est-à-dire
+\emph{sans consommer de lettre}, d'un état $q$ à un état $q'$, lorsque
+ces états sont reliés par une ε-transition.  (On comprend, du coup,
+pourquoi un automate à transition spontanée est forcément
+non-déterministe : ces transitions spontanées ne sont qu'une
+\emph{possibilité}, ce qui sous-entend le non-déterminisme.)
+
+De façon plus précise, un εNFA accepte un mot $w$ lorsqu'\emph{il
+  existe} un chemin orienté conduisant d'un état initial $q_0$ à un
+état final $q_n$ et tel que $w$ coïncide avec le mot obtenu en lisant
+dans l'ordre les étiquettes $x_i$ des différentes arêtes $q_{i-1} \to
+q_i$ de ce chemin, quitte à ignorer les $\varepsilon$.
+
+Autrement dit, $w$ est accepté lorsqu'\emph{il existe} $q_0,\ldots,q_n
+\in Q$ et $t_1,\ldots,t_n \in (\Sigma\cup\{\varepsilon\})$ tels que
+$q_0 \in I$ et $q_n\in F$ et $(q_{i-1},t_i,q_i) \in \delta$ pour
+chaque $1\leq i\leq n$ et $w = t_1\cdots t_n$ (\emph{attention} : dans
+cette écriture, $t_1,\ldots,t_n$ ne sont pas forcément les lettres
+de $w$, certains des $t_i$ peuvent être le symbole $\varepsilon$, les
+lettres de $w$ sont obtenues en ignorant ces symboles).
 
 \thingy Voici une formalisation possible : si $A = (Q,I,F,\delta)$ est
 un εNFA sur l'alphabet $\Sigma$, on définit une relation $\delta^*
@@ -1899,34 +1904,6 @@ lorsqu'il existe $q_0,\ldots,q_n \in Q$ et $t_1,\ldots,t_n \in
 $(q_{i-1},t_i,q_i) \in\delta$ pour chaque $1\leq i\leq n$, et enfin $w
 = t_1\cdots t_n$.
 
-Si on préfère, on peut définir par récurrence sur $n \geq 0$ une
-relation $\delta^{(n)} \subseteq Q \times \Sigma^* \times Q$ de la
-manière suivante :
-\begin{itemize}
-\item $(q,w,q') \in \delta^{(0)}$ si et seulement si $q'=q$ et
-  $v=\varepsilon$,
-\item $\delta^{(1)} = \delta \subseteq Q \times
-  (\Sigma\cup\{\varepsilon\})$ (faisant partie de la donnée de $A$),
-\item $(q,v,q') \in \delta^{(n+1)}$ si et seulement si il existe
-  $q^\sharp \in Q$ et $t \in \Sigma\cup\{\varepsilon\}$ tels que
-  $(q,w,q^\sharp) \in \delta^{(n)}$ et $(q^\sharp,t,q') \in \delta$ et
-  $v = wt$ (ce qui signifie que : soit $t=\varepsilon$ et $v=w$, soit
-  $t\in\Sigma$ est la dernière lettre de $w$ et $v$ est le préfixe
-  correspondant) ;
-\end{itemize}
-et on définit $\delta^* = \bigcup_{n=1}^{+\infty} \delta^{(n)}$,
-autrement dit $(q,w,q') \in \delta^*$ lorsqu'il existe $n$ tel que
-$(q,w,q') \in \delta^{(n)}$.
-
-Concrètement, $(q,w,q') \in \delta^{(n)}$ signifie que le εNFA peut
-passer de l'état $q$ à l'état $q'$ en effectuant (exactement) $n$
-transitions ($q_0\to q_1 \to \cdots \to q_n$ étiquetées par
-$t_1,\ldots,t_n \in (\Sigma\cup\{\varepsilon\})$) et en consommant le
-mot $w$ (soit $w = t_1\cdots t_n$) ; et $(q,w,q') \in \delta^*$
-signifie la même chose mais sans contrainte sur le nombre de
-transitions.  La différence avec les NFA est que le nombre $n$ de
-transitions n'est plus forcément égal à la longueur de $w$.
-
 Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$
 et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$.  Le
 langage accepté $L_A$ et l'équivalence de deux automates sont définis
@@ -2408,7 +2385,7 @@ lorsqu'il existe $q_0,\ldots,q_n \in Q$ et $r_1,\ldots,r_n \in
 $(q_{i-1},r_i,q_i) \in\delta$ pour chaque $1\leq i\leq n$, et enfin $w
 \in L_{r_1\cdots r_n}$.
 
-Concrètement, $(q,w,q') \in \delta^{(n)}$ signifie que le RNFA peut
+Concrètement, $(q,w,q') \in \delta^*$ signifie que le RNFA peut
 passer de l'état $q$ à l'état $q'$ en effectuant des transitions
 ($q_0\to q_1 \to \cdots \to q_n$ étiquetées par $r_1,\ldots,r_n \in
 \mathrm{regexp}(\Sigma)$) et en consommant le mot $w$ au sens où ce