NFAs with spontaneous transitions.

3 files changed, 144 insertions, 16 deletions

diff --git a/figs/example4det.dot b/figs/example4det.dot
index 2d88a37..7121690 100644
--- a/figs/example4det.dot
+++ b/figs/example4det.dot
@@ -1,10 +1,10 @@
 digraph example4det {
 	rankdir="LR";
 	node [texmode="math",shape="circle",style="state"];
-	q0 [style="state,initial",label="\{0\}"];
-	q01 [style="state",label="\{0,1\}"];
-	q02 [style="state,final",label="\{0,2\}"];
-	q012 [style="state,final",label="\{0,1,2\}"];
+	q0 [style="state,initial",label="0",texlbl="$\{0\}$"];
+	q01 [style="state",label="01",texlbl="$\{0,1\}$"];
+	q02 [style="state,final",label="02",texlbl="$\{0,2\}$"];
+	q012 [style="state,final",label="012",texlbl="$\{0,1,2\}$"];
 	edge [texmode="math",lblstyle="auto"];
 	q0 -> q0 [label="b",topath="loop above"];
 	q0 -> q01 [label="a"];
diff --git a/figs/example5.dot b/figs/example5.dot
new file mode 100644
index 0000000..7c5e403
--- /dev/null
+++ b/figs/example5.dot
@@ -0,0 +1,13 @@
+digraph example5 {
+	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="e",texlbl="$\varepsilon$"];
+	q1 -> q1 [label="b",topath="loop above"];
+	q1 -> q2 [label="e",texlbl="$\varepsilon$"];
+	q2 -> q2 [label="c",topath="loop above"];
+}
diff --git a/notes-inf105.tex b/notes-inf105.tex
index f46a27a..ae1f0e1 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -37,6 +37,7 @@
 \newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
 %
 \DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
 %
 \DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
 \DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
@@ -1136,8 +1137,9 @@ $(q_{i-1},x_i,q_i) \in \delta$ pour chaque $1\leq i\leq n$ ; ou, ce
 qui revient au même (par récurrence sur la longueur de $w$) :
 \begin{itemize}
 \item $(q,\varepsilon,q') \in \delta^*$ si et seulement si $q'=q$,
-\item $(q,wx,q') \in \delta^*$ si et seulement si il existe $q_1$ tel
-  que $(q,w,q_1) \in \delta^*$ et $(q_1,x,q') \in \delta$.
+\item $(q,wx,q') \in \delta^*$ si et seulement si il existe $q^\sharp$
+  tel que $(q,w,q^\sharp) \in \delta^*$ et $(q^\sharp,x,q') \in
+  \delta$.
 \end{itemize}
 
 Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$
@@ -1285,19 +1287,19 @@ procédant ainsi, on constuit l'automate à $4$ états qui suit :
   \pgfsetstrokecolor{strokecol}
   \definecolor{fillcol}{rgb}{1.0,1.0,1.0};
   \pgfsetfillcolor{fillcol}
-  \filldraw (0bp,0bp) -- (0bp,204bp) -- (274bp,204bp) -- (274bp,0bp) -- cycle;
+  \filldraw (0bp,0bp) -- (0bp,155bp) -- (212bp,155bp) -- (212bp,0bp) -- cycle;
 \end{scope}
-  \node (q02) at (236bp,30bp) [draw,circle,state,final] {$\{0,2\}$};
-  \node (q0) at (24bp,54bp) [draw,circle,state,initial] {$\{0\}$};
-  \node (q01) at (123bp,94bp) [draw,circle,state] {$\{0,1\}$};
-  \node (q012) at (236bp,134bp) [draw,circle,state,final] {$\{0,1,2\}$};
-  \draw [->] (q01) ..controls (164.77bp,70.495bp) and (183.92bp,59.452bp)  .. node[auto] {$b$} (q02);
-  \draw [->] (q0) ..controls (57.935bp,67.582bp) and (72.263bp,73.49bp)  .. node[auto] {$a$} (q01);
+  \node (q02) at (188bp,19bp) [draw,circle,state,final] {$\{0,2\}$};
+  \node (q0) at (18bp,40bp) [draw,circle,state,initial] {$\{0\}$};
+  \node (q01) at (100bp,71bp) [draw,circle,state] {$\{0,1\}$};
+  \node (q012) at (188bp,98bp) [draw,circle,state,final] {$\{0,1,2\}$};
+  \draw [->] (q01) ..controls (129.79bp,53.593bp) and (147.53bp,42.867bp)  .. node[auto] {$b$} (q02);
+  \draw [->] (q0) ..controls (45.781bp,50.378bp) and (59.874bp,55.839bp)  .. node[auto] {$a$} (q01);
   \draw [->] (q0) to[loop above] node[auto] {$b$} (q0);
-  \draw [->] (q01) ..controls (163.68bp,108.3bp) and (177.52bp,113.29bp)  .. node[auto] {$a$} (q012);
+  \draw [->] (q01) ..controls (129.27bp,79.877bp) and (142.8bp,84.122bp)  .. node[auto] {$a$} (q012);
   \draw [->] (q012) to[loop above] node[auto] {$a$} (q012);
-  \draw [->] (q02) ..controls (176.26bp,31.326bp) and (130.91bp,33.455bp)  .. (92bp,39bp) .. controls (80.643bp,40.618bp) and (68.355bp,43.14bp)  .. node[auto] {$a,b$} (q0);
-  \draw [->] (q012) ..controls (236bp,87.978bp) and (236bp,79.013bp)  .. node[auto] {$b$} (q02);
+  \draw [->] (q02) ..controls (146.97bp,21.169bp) and (110.83bp,23.684bp)  .. (80bp,28bp) .. controls (68.696bp,29.582bp) and (56.322bp,31.905bp)  .. node[auto] {$a,b$} (q0);
+  \draw [->] (q012) ..controls (188bp,65.926bp) and (188bp,56.965bp)  .. node[auto] {$b$} (q02);
 %
 \end{tikzpicture}
 
@@ -1317,6 +1319,119 @@ $\{0,1,2\}$ mémorise « les deux dernières lettres étaient des $a$ »,
 et l'état $\{0,2\}$ mémorise « la dernière lettre était un $b$, mais
   la précédente était un $a$ ».
 
+
+\subsection{Automates finis non-déterministes à transitions spontanées (=εNFA)}
+
+\thingy Un \textbf{automate fini non-déterministe à transitions
+  spontanées} ou \textbf{...à $\varepsilon$-transitions}, en abrégé
+\textbf{εNFA}, sur un alphabet $\Sigma$ est la donnée
+\begin{itemize}
+\item d'un ensemble fini $Q$ d'états,
+\item d'un ensemble $I \subseteq Q$ d'états dits initiaux,
+\item d'un ensemble $F \subseteq Q$ d'états dits finaux,
+\item d'une relation de transition $\delta \subseteq Q \times
+  (\Sigma\cup\{\varepsilon\}) \times Q$.
+\end{itemize}
+Autrement dit, on autorise maintenant des transitions étiquetées par
+le mot vide $\varepsilon$ plutôt que par une lettre $x \in\Sigma$ :
+ces transitions sont dites spontanées, ou $\varepsilon$-transitions.
+
+Soulignons qu'on ne définit les $\varepsilon$-transitions \emph{que}
+pour les automates non-déterministes : ou, pour dire les choses
+autrement, \emph{un automate qui possède des $\varepsilon$-transitions
+  est par nature même non-déterministe}.
+
+La représentation graphique des εNFA est évidente (on utilisera le
+symbole « $\varepsilon$ » pour étiqueter les transitions spontanées).
+
+\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 Voici une formalisation possible : si $A = (Q,I,F,\delta)$ est
+un εNFA sur l'alphabet $\Sigma$, on définit une relation $\delta^*
+\subseteq Q \times \Sigma^* \times Q$ par $(q,w,q') \in \delta^*$
+lorsqu'il existe $q_0,\ldots,q_n \in Q$ et $t_1,\ldots,t_n \in
+(\Sigma\cup\{\varepsilon\})$ tels que $q_0 = q$ et $q_n = q'$ et
+$(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
+de façon analogue aux DFA
+(cf. \ref{definition-recognizable-language}).
+
+\thingy Voici un exemple de εNFA particulièrement simple sur $\Sigma =
+\{a,b,c\}$:
+
+\begin{center}
+%%% begin example5 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (98bp,18bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
+  \node (q2) at (178bp,18bp) [draw,circle,state,final] {$2$};
+  \draw [->] (q0) ..controls (46.106bp,18bp) and (58.578bp,18bp)  .. node[auto] {$\varepsilon$} (q1);
+  \draw [->] (q1) to[loop above] node[auto] {$b$} (q1);
+  \draw [->] (q1) ..controls (126.11bp,18bp) and (138.58bp,18bp)  .. node[auto] {$\varepsilon$} (q2);
+  \draw [->] (q0) to[loop above] node[auto] {$a$} (q0);
+  \draw [->] (q2) to[loop above] node[auto] {$c$} (q2);
+%
+\end{tikzpicture}
+
+%%% end example5 %%%
+\end{center}
+
+En considérant les différents chemins possibles entre $0$ et $2$ sur
+ce graphe, on comprend que le langage qu'il reconnaît est celui des
+mots sur $\{a,b,c\}$ formés d'un nombre quelconque de $a$ suivi d'un
+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{*}$.
+
 %
 %
 %