summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-23 19:05:04 +0100
committerDavid A. Madore <david+git@madore.org>2016-11-23 19:05:04 +0100
commit36ba46eccdbe995358d11a0febaed52e6c035b17 (patch)
treefd411025c43952b6f4a9999ce7dd4c4b3b6602a3 /notes-inf105.tex
parent9a5b5be7a96cf857529211906aed559eafd407e1 (diff)
downloadinf105-36ba46eccdbe995358d11a0febaed52e6c035b17.zip
inf105-36ba46eccdbe995358d11a0febaed52e6c035b17.tar.gz
inf105-36ba46eccdbe995358d11a0febaed52e6c035b17.tar.bz2
NFAs with spontaneous transitions.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex139
1 files changed, 127 insertions, 12 deletions
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{*}$.
+
%
%
%