NFAs and determinization of them.

3 files changed, 284 insertions, 15 deletions

diff --git a/figs/example4.dot b/figs/example4.dot
new file mode 100644
index 0000000..a4ee46f
--- /dev/null
+++ b/figs/example4.dot
@@ -0,0 +1,11 @@
+digraph example4 {
+	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,b",topath="loop above"];
+	q0 -> q1 [label="a"];
+	q1 -> q2 [label="a,b"];
+}
diff --git a/figs/example4det.dot b/figs/example4det.dot
new file mode 100644
index 0000000..2d88a37
--- /dev/null
+++ b/figs/example4det.dot
@@ -0,0 +1,16 @@
+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\}"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q0 [label="b",topath="loop above"];
+	q0 -> q01 [label="a"];
+	q01 -> q012 [label="a"];
+	q01 -> q02 [label="b"];
+	q012 -> q012 [label="a",topath="loop above"];
+	{ rank="same"; q012 -> q02 [label="b"]; }
+	q02 -> q0 [label="a,b"];
+}
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 90a0889..f46a27a 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -53,7 +53,7 @@
 %
 % NOTE: compile dot files with
 % dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
-\tikzstyle{automaton}=[>=stealth',initial text={},every loop/.style={min distance=7mm,looseness=5}]
+\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
 \tikzstyle{state}=[]
 \tikzstyle{final}=[accepting by arrow]
 %
@@ -716,12 +716,12 @@ ou en abrégé \textbf{DFA} (pour \textit{deterministic finite
 \thingy Graphiquement, on représente un DFA comme un graphe orienté
 aux arêtes étiquetées par des éléments de $\Sigma$ : plus exactement,
 on trace un nœud pour chaque élément $q \in Q$, et lorsque
-$\delta(q,x) = q'$ on introduit une arête $q \to q'$ étiquetée par la
+$\delta(q,x) = q'$ on introduit une flèche $q \to q'$ étiquetée par la
 lettre $x$.  La condition sur $\delta$ (pour être un DFA) est alors
 que, pour chaque état $q \in Q$ et chaque lettre $x \in \Sigma$, il
 existe une unique arête partant de $q$ et étiquetée par $x$.  En
-outre, on introduit une arête pointant de nulle part vers $q_0$, et
-pour chaque $q\in F$ une arête pointant de $q$ vers nulle
+outre, on introduit une flèche pointant de nulle part vers $q_0$, et
+pour chaque $q\in F$ une flèche pointant de $q$ vers nulle
 part\footnote{Certains auteurs préfèrent d'autres conventions, par
   exemple celle consistant à entourer deux fois les états finaux.}.
 
@@ -767,7 +767,7 @@ successivement dans les états $q_0$ puis $q_1 := \delta(q_0,x_1)$ puis
 $q_2 := \delta(q_1,x_2)$, et ainsi de suite jusqu'à $q_n :=
 \delta(q_{n-1},x_n)$) ; on dit que l'automate effectue les transitions
 $q_0\to q_1$ (en consommant $x_1$) puis $q_1\to q_2$ (en
-consommant $x_2$q) et ainsi de suite.  Si $q_n$ est l'état dans lequel
+consommant $x_2$) et ainsi de suite.  Si $q_n$ est l'état dans lequel
 se trouve l'automate une fois qu'il a consommé le mot $w$, on dira que
 l'automate \emph{acepte} ou \emph{rejette} le mot selon que $q_n \in
 F$ ou que $q_n \not\in F$.
@@ -986,10 +986,11 @@ $c{*}ac{*}bc{*}$.)
 
 \begin{prop}
 Soit $A = (Q,q_0,F,\delta)$ un DFAI sur un alphabet $\Sigma$.  Alors
-il existe un DFA $A' = (Q',q'_0,F',\delta')$ qui é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$ en ajoutant au plus un état
-\textbf{puits} à $A$ : on a $\#Q' \leq \#Q + 1$.
+il existe un DFA $A' = (Q',q'_0,F',\delta')$ (sur le même
+alphabet $\Sigma$) 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$ en ajoutant au plus un état \textbf{puits}
+à $A$ : on a $\#Q' \leq \#Q + 1$.
 \end{prop}
 \begin{proof}
 On définit $Q' = Q \cup \{q_\bot\}$ où $q_\bot$ est un nouvel état
@@ -1012,12 +1013,12 @@ $A'$ « tombe dans le puits » lorsque le DFAI $A$ cesse de
 fonctionner).  En particulier, ils reconnaissent les mêmes langages.
 \end{proof}
 
-On dit que le DFA $A'$ est obtenu en \textbf{complétant} le DFAI $A$
-lorsqu'il est obtenu par la procédure décrite par la démonstration de
-cette proposition, c'est-à-dire par l'addition d'un état puits, sauf
-si $A$ est déjà complet, auquel cas on convient qu'il est son propre
-complété (i.e., on n'ajoute un puits que quand c'est réellement
-nécessaire).
+\thingy On dit que le DFA $A'$ est obtenu en \textbf{complétant} le
+DFAI $A$ lorsqu'il est obtenu par la procédure décrite dans la
+démonstration de cette proposition, c'est-à-dire par l'addition d'un
+état puits, sauf si $A$ est déjà complet, auquel cas on convient qu'il
+est son propre complété (i.e., on n'ajoute un puits que quand c'est
+réellement nécessaire).
 
 \thingy À titre d'exemple, le DFA suivant représente la complétion du
 DFAI représenté en \ref{discussion-example2b} :
@@ -1075,6 +1076,247 @@ co-accessibles (on les dit aussi \textbf{utiles}) est parfois appelé
 états utiles : ainsi, tout DFAI est équivalent à un DFAI émondé.
 
 
+\subsection{Automates finis non-déterministes (=NFA)}
+
+\thingy Un \textbf{automate fini non-déterministe}, 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 \emph{relation} de transition $\delta \subseteq Q \times
+  \Sigma \times Q$ (c'est-à-dire une partie du produit cartésien $Q
+  \times \Sigma \times Q$, i.e., un ensemble de triplets $(q,x,q') \in
+  Q \times \Sigma \times Q$).
+\end{itemize}
+Autrement dit, on autorise maintenant un ensemble quelconque d'états
+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 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')
+\in \delta$ ; comme précédemment, on marque les états initiaux par une
+flèche entrante (i.e., pointant de nulle part) et les états finaux par
+une flèche sortante (i.e., pointant vers nulle part).
+
+\thingy Il faut comprendre le fonctionnement d'un NFA de la manière
+suivante : un mot $w = x_1\cdots x_n$ est accepté par l'automate
+lorsqu'\emph{il existe} un chemin conduisant d'\emph{un} état initial
+à un état final et dont les arêtes sont étiquetées par les lettres
+$x_1,\ldots,x_n$ de $w$ (dans l'ordre) ; autrement dit, $w$ est
+accepté lorsqu'\emph{il existe} $q_0,\ldots,q_n \in Q$ tels que $q_0
+\in I$ et $q_n\in F$ et $(q_{i-1},x_i,q_i) \in \delta$ pour
+chaque $1\leq i\leq n$.
+
+Il existe plusieurs manières de reformuler ce comportement : on peut
+par exemple dire que l'automate est dans plusieurs états à la fois,
+qu'il commence dans tous les états initiaux à la fois, et qu'à chaque
+fois qu'il consomme un symbole $x$, il effectue toutes les transitions
+possibles à partir d'un état où et étiquetées par ce symbole, et qu'au
+bout du compte l'automate accepte le mot lorsqu'il est dans \emph{au
+  moins un} état acceptant (même s'il est, par ailleurs, dans d'autres
+états).  C'est cette façon de voir les choses qui conduira à
+l'équivalence entre NFA et DFA (cf. \ref{determinization-of-nfa}).
+
+Une autre façon de présenter les choses est que l'automate « devine »
+par quel état initial commencer, et à chaque symbole consommé,
+« devine » quelle transition effectuer, de manière à accepter le mot
+si c'est possible.
+
+En tout état de cause, la définition formelle va être donnée
+ci-dessous.
+
+\thingy 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^*$ lorsque $w = x_1\cdots x_n$ et qu'il
+existe $(q_0,\ldots,q_n)$ tels que $q_0 = q$ et $q_n = q'$ et
+$(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$.
+\end{itemize}
+
+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\label{discussion-example4} Pour illustrer le fonctionnement
+des NFA, considérons l'automate à trois états sur $\Sigma=\{a,b\}$
+représenté par la figure suivante : on a $Q = \{0,1,2\}$ avec
+$I=\{0\}$ et $F=\{2\}$ et $\delta = \{(0,a,0),\penalty0
+(0,b,0),\penalty-100 (0,a,1),\penalty-50 (1,a,2),\penalty0 (1,b,2)\}$.
+
+\begin{center}
+%%% begin example4 %%%
+
+\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 (188bp,18bp) [draw,circle,state,final] {$2$};
+  \draw [->] (q0) ..controls (46.106bp,18bp) and (58.578bp,18bp)  .. node[auto] {$a$} (q1);
+  \draw [->] (q1) ..controls (128.76bp,18bp) and (145.63bp,18bp)  .. node[auto] {$a,b$} (q2);
+  \draw [->] (q0) to[loop above] node[auto] {$a,b$} (q0);
+%
+\end{tikzpicture}
+
+%%% end example4 %%%
+\end{center}
+
+Cet automate n'est pas déterministe car il existe deux transitions
+étiquetées $a$ partant de l'état $0$.  En considérant les différents
+chemins possibles entre $0$ et $2$ dans ce graphe, on comprend que le
+langage qu'il reconnaît est le langage des mots sur $\{a,b\}$ dont
+l'avant-dernière lettre est un $a$ (c'est aussi le langage désigné par
+l'expression rationnelle $(a|b){*}a(a|b)$).  Une façon de présenter le
+non-déterminisme est que l'automate « devine », quand il est dans
+l'état $0$ et qu'on lui fait consommer un $a$, si ce $a$ sera
+l'avant-dernière lettre, et, dans ce cas, passe dans l'état $1$ pour
+pouvoir accepter le mot.
+
+\begin{prop}\label{determinization-of-nfa}
+Soit $A = (Q,I,F,\delta)$ un NFA sur un alphabet $\Sigma$.  Alors il
+existe un DFA $A' = (Q',q'_0,F',\delta')$ (sur le même
+alphabet $\Sigma$) 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$ avec une augmentation au plus exponentielle
+du nombre d'états : $\#Q' \leq 2^{\#Q}$.
+\end{prop}
+\begin{proof}
+On définit $Q' = \mathscr{P}(Q) = \{\mathbf{q} \subseteq Q\}$
+l'\emph{ensemble des parties} de $Q$ : c'est ce qui servira d'ensemble
+d'états du DFA $A'$ qu'on construit (i.e., un état de $A'$ est un
+ensemble d'états de $A$ — intuitivement, c'est l'ensemble des états
+dans lesquels on se trouve simultanément).  On pose $q'_0 = I$ et $F'
+= \{\mathbf{q}\subseteq Q :\penalty-100 \mathbf{q}\cap F
+\neq\varnothing\}$ l'ensemble des états de $A'$ qui, vus comme des
+ensembles d'états de $A$, contiennent \emph{au moins un} état final.
+Enfin, pour $\mathbf{q}\subseteq Q$ et $x \in \Sigma$, on définit
+$\delta'(\mathbf{q},x) = \{q_1\in Q : \exists q_0\in\mathbf{q}
+((q_0,x,q_1) \in \delta)\}$ comme l'ensemble de tous les états $q_1$
+de $A$ auxquels on peut accéder depuis un état $q_0$ dans $\mathbf{q}$
+par une transition $(q_0,x,q_1)$ (étiquetée par $x$) de $A$.
+
+Il est alors facile de voir (par récurrence sur $|w|$) que
+$\delta^{\prime*}(\mathbf{q},w)$ est l'ensemble de tous les les états
+$q_1 \in Q$ tels que $(q_0,w,q_1)\in\delta^*$, i.e., auxquels on peut
+accéder depuis un état $q_0$ dans $\mathbf{q}$ par une suite de
+transitions de $A$ étiquetées par les lettres de $w$.  En particulier,
+$\delta^{\prime*}(I,w)$ est l'ensemble de tous les états de $A$
+auxquels on peut accéder depuis un état initial de $A$ par une suite
+de transitions de $A$ étiquetées par les lettres de $w$ : le mot $w$
+appartient à $L_A$ si et seulement si cet ensemble contient un élément
+de $F$, ce qui par définition de $F'$ signifie exactement
+$\delta^{\prime*}(I,w) \in F'$.  On a bien prouvé $L_{A'} = L_A$.
+
+Enfin, $\#Q' = \#\mathscr{P}(Q) = 2^{\#Q}$ (car une partie de $Q$ peut
+se voir comme sa fonction indicatrice, qui est une fonction $Q \to
+\{0,1\}$).
+\end{proof}
+
+\thingy On dit que le DFA $A'$ est obtenu en \textbf{déterminisant} le
+NFA $A$ lorsqu'il est obtenu par la procédure décrite dans la
+démonstration de cette proposition en ne gardant que les états
+accessibles.
+
+Algorithmiquement, la déterminisation de $A$ s'obtient par la
+procéduire suivante :
+\begin{itemize}
+\item créer une file (ou une pile) d'ensembles d'états de $A$ ;
+  initialiser cette file avec le seul élément $I$ (vu comme un
+  sous-ensemble de $Q$) ; et créer l'automate $A'$ avec initialement
+  l'unique état $I$, marqué comme état initial, et aussi comme final
+  s'il contient un état final de $A$ ;
+\item tant que la file/pile n'est pas vide : en extraire un élément
+  $\mathbf{q}$, et, pour chaque lettre $x\in\Sigma$,
+\begin{itemize}
+\item calculer l'ensemble $\mathbf{q}' = \{q_1\in Q : \exists
+  q_0\in\mathbf{q} ((q_0,x,q_1) \in \delta)\}$ (en listant tous les
+  triplets $(q_0,x,q_1)$ dont le premier élément est dans $\mathbf{q}$
+  et le second élément est $x$),
+\item si $\mathbf{q}'$ n'existe pas déjà comme état de $A'$, l'y
+  ajouter, et dans ce cas, l'ajouter à la file/pile, et de plus, si
+  $\mathbf{q}'$ contient un état final de $A$, marquer cet état comme
+  final pour $A'$,
+\item et ajouter à $A'$ la transition $\delta'(\mathbf{q},x) =
+  \mathbf{q}'$.
+\end{itemize}
+\end{itemize}
+
+La file/pile sert à stocker les états de $A'$ qui ont été créés mais
+pour lesquels les transitions sortantes n'ont pas encore été
+calculées.  L'algorithme se termine quand la file/pile se vide, ce qui
+se produit toujours en au plus $2^{\#Q}$ étapes car chaque $\mathbf{q}
+\subseteq Q$ ne peut apparaître qu'une seule fois dans la file/pile.
+
+Il se peut que l'état $\varnothing$ soit créé : cet état servira
+effectivement de puits, au sens où on aura $\delta'(\varnothing,x) =
+\varnothing$ quel que soit $x$ (et l'état n'est pas acceptant).
+
+Il arrive souvent que l'automate déterminisé soit plus petit que les
+$2^{\#Q}$ états qu'il a dans le pire cas.
+
+\thingy À titre d'exemple, déterminisons le NFA $A$ présenté
+en \ref{discussion-example4} : on commence par construire un état
+$\{0\}$ pour $A'$ car le NFA a $\{0\}$ pour ensemble d'états
+initiaux ; on a $\delta'(\{0\},a) = \{0,1\}$ car $0$ et $1$ sont les
+deux états auxquels on peut arriver dans $A$ par une transition
+partant de $0$ et étiquetée par $a$, tandis que $\delta'(\{0\},b) =
+\{0\}$ ; ensuite, $\delta'(\{0,1\},a) = \{0,1,2\}$ car $0,1,2$ sont
+les trois états auxquels on peut arriver dans $A$ par une transition
+partant de $0$ ou $1$ et étiquetée par $a$ ; et ainsi de suite.  En
+procédant ainsi, on constuit l'automate à $4$ états qui suit :
+
+\begin{center}
+\footnotesize
+%%% begin example4det %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\begin{scope}
+  \pgfsetstrokecolor{black}
+  \definecolor{strokecol}{rgb}{1.0,1.0,1.0};
+  \pgfsetstrokecolor{strokecol}
+  \definecolor{fillcol}{rgb}{1.0,1.0,1.0};
+  \pgfsetfillcolor{fillcol}
+  \filldraw (0bp,0bp) -- (0bp,204bp) -- (274bp,204bp) -- (274bp,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);
+  \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 [->] (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);
+%
+\end{tikzpicture}
+
+%%% end example4det %%%
+\end{center}
+
+On remarquera qu'on a construit moins que les $2^3 = 8$ états qu'on
+pouvait craindre.
+
+Il est par ailleurs instructif de regarder comment fonctionne
+l'automate $A'$ ci-dessus pour déterminer si l'avant-dernière lettre
+d'un mot est un $a$ : intuitivement, l'état $\{0\}$ mémorise
+l'information « la dernière lettre n'était pas un $a$, et la
+  précédente ne l'était pas », l'état $\{0,1\}$ mémorise « la dernière
+  lettre était un $a$, mais la précédente ne l'état pas », l'état
+$\{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$ ».
+
 %
 %
 %