Incomplete DFAs. Change formating of self-loops in graphs.

1 files changed, 198 insertions, 35 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index a8572db..ded4af0 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={}]
+\tikzstyle{automaton}=[>=stealth',initial text={},every loop/.style={min distance=7mm,looseness=5}]
 \tikzstyle{state}=[]
 \tikzstyle{final}=[accepting by arrow]
 %
@@ -368,7 +368,7 @@ qu'on ne demande pas que $L$ soit fini (mais il peut l'être).
 nombre quelconque (éventuellement nul) de $c$ est un langage sur
 l'alphabet $\Sigma = \{a,b,c,d\}$.  On verra plus loin que ce langage
 est « rationnel » (et pourra être désigné par l'expression rationnelle
-$dc*$).
+$dc{*}$).
 
 Voici quelques autres exemples de langages :
 \begin{itemize}
@@ -597,7 +597,7 @@ introduit un nouvel objet, les \textbf{expressions rationnelles}
 (certains préfèrent le terme d'\textbf{expressions régulières}), qui
 sont des expressions servant à désigner un langage rationnel.  Par
 exemple, plutôt que d'écrire « $\{d\}(\{c\}^*)$ », on parlera du
-langage désigné par l'expression rationnelle $dc*$.
+langage désigné par l'expression rationnelle $dc{*}$.
 
 Plus exactement, une expression rationnelle (sur un alphabet $\Sigma$)
 est un mot sur l'alphabet $\Sigma \cup \{\bot,
@@ -626,14 +626,14 @@ l'expression $r$, de la manière suivante :
   alors $(r_1|r_2)$ est une expression rationnelle et son langage
   désigné est $L_{(r_1|r_2)} := L_1\cup L_2$,
 \item si $r$ est une expression rationnelle et $L = L_r$ les langage
-  désigné correspondant, alors $(r)*$ est une expression rationnelle
-  et son langage désigné est $L_{(r)*} := L^*$.
+  désigné correspondant, alors $(r){*}$ est une expression rationnelle
+  et son langage désigné est $L_{(r){*}} := L^*$.
 \end{itemize}
 
 À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, $c$ est une
-expression rationnelle qui désigne le langage $\{c\}$, donc $(c)*$ en
+expression rationnelle qui désigne le langage $\{c\}$, donc $(c){*}$ en
 est une qui désigne le langage $\{c\}^* = \{\varepsilon, c, cc,
-ccc,\ldots\}$, et enfin $d(c)*$ en est une qui désigne le langage $\{d,
+ccc,\ldots\}$, et enfin $d(c){*}$ en est une qui désigne le langage $\{d,
 dc, dcc, \ldots\}$ des mots formés d'un $d$ et d'une succession
 quelconques de $c$.  Voici quelques autres exemples, toujours sur
 $\Sigma = \{a,b,c,d\}$ :
@@ -642,11 +642,11 @@ $\Sigma = \{a,b,c,d\}$ :
   \{b\} = \{a,b\}$ formé des deux mots d'une seule lettre $a$ et $b$ ;
 \item l'expression rationnelle $(a|b)c$ désigne le langage
   $\{a,b\}\{c\} = \{ac,bc\}$, de même que $(ac|bc)$ ;
-\item l'expression rationnelle $(bc)*$ désigne le langage $\{bc\}^* =
+\item l'expression rationnelle $(bc){*}$ désigne le langage $\{bc\}^* =
   \{\varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ;
-\item l'expression rationnelle $(a|(bc)*)$ désigne le langage $\{a\}
+\item l'expression rationnelle $(a|(bc){*})$ désigne le langage $\{a\}
   \cup \{bc\}^* = \{a, \varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ;
-\item l'expression rationnelle $(a|(bc)*)d$ désigne le langage $\{a, d,
+\item l'expression rationnelle $(a|(bc){*})d$ désigne le langage $\{a, d,
   bcd, bcbcd, bcbcbcd, \ldots\}$.
 \end{itemize}
 
@@ -655,16 +655,16 @@ pour lequel il existe une expression rationnelle qui le désigne.
 
 On dira qu'un mot $w$ \textbf{vérifie} une expression rationnelle $r$
 lorsque ce mot appartient au langage qu'elle désigne (i.e., $w \in
-L_r$).  Par exemple, $dccc$ vérifie l'expression rationnelle $d(c)*$.
+L_r$).  Par exemple, $dccc$ vérifie l'expression rationnelle $d(c){*}$.
 
 La convention de parenthésage introduite ci-dessus est inambiguë mais
 parfois inutilement lourde : on se permettra parfois de l'alléger, par
 exemple d'écrire $(r_1|r_2|r_3)$ pour $((r_1|r_2)|r_3)$ (ou pour
 $(r_1|(r_2|r_3))$, ce qui n'a guère d'importance vu qu'elles désignent
-le même langage), ou encore $x*$ pour $(x)*$ lorsque $x$ est formé
+le même langage), ou encore $x{*}$ pour $(x){*}$ lorsque $x$ est formé
 d'un seul caractère.  La convention essentielle est que l'opération
-d'étoile $*$ est la plus prioritaire ($ab*$ se lit comme $a(b)*$ et
-non pas comme $(ab)*$), la concaténation vient après, et la barre de
+d'étoile ${*}$ est la plus prioritaire ($ab{*}$ se lit comme $a(b){*}$ et
+non pas comme $(ab){*}$), la concaténation vient après, et la barre de
 disjonction $|$ est la moins prioritaire ($ab|cd$ se lit comme
 $(ab|cd)$ et pas comme $a(b|c)d$).
 
@@ -680,7 +680,7 @@ notée $+$ par les mathématiciens.  Il y a ici un risque de confusion
 lié au fait que, en informatique, le symbole \texttt{+} est utilisé
 par de nombreux moteurs d'expressions régulières (par exemple,
 \texttt{egrep}) pour désigner l'opération évoquée en \ref{kleene-plus}
-(de sorte que $r+$ a le même sens que $rr*$).
+(de sorte que $r+$ a le même sens que $rr{*}$).
 
 
 \section{Automates finis}
@@ -748,8 +748,8 @@ dont le nombre de $b$ est pair.
   \node (q0) at (18bp,20.306bp) [draw,circle,state,initial] {$0$};
   \draw [->] (q1) ..controls (75.212bp,3.6347bp) and (64.284bp,-1.3057bp)  .. (54bp,1.3057bp) .. controls (50.042bp,2.3107bp) and (46.047bp,3.8633bp)  .. node[auto] {$b$} (q0);
   \draw [->] (q0) ..controls (46.106bp,20.306bp) and (58.578bp,20.306bp)  .. node[auto] {$b$} (q1);
-  \draw [->] (q1) ..controls (89.406bp,46.931bp) and (91.75bp,56.306bp)  .. (98bp,56.306bp) .. controls (102bp,56.306bp) and (104.4bp,52.458bp)  .. node[auto] {$a$} (q1);
-  \draw [->] (q0) ..controls (9.4062bp,46.931bp) and (11.75bp,56.306bp)  .. (18bp,56.306bp) .. controls (22.004bp,56.306bp) and (24.405bp,52.458bp)  .. node[auto] {$a$} (q0);
+  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
+  \draw [->] (q0) to[loop above] node[auto] {$a$} (q0);
 %
 \end{tikzpicture}
 
@@ -765,8 +765,10 @@ ordre.  Le fait de consommer une lettre $x$ fait passer l'automate de
 l'état $q$ à l'état $\delta(q,x)$ (autrement dit, l'automate passe
 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)$).  Si $q_n$ est l'état dans lequel se trouve
-l'automate une fois qu'il a consommé le mot $w$, on dira que
+\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
+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$.
 
@@ -779,9 +781,10 @@ actuellement).  Si à la fin l'état $q_n$ est acceptant (représenté par
 une flèche pointant vers nulle part), le mot $w$ est accepté, sinon il
 est rejeté.
 
-\thingy Formellement : si $A = (Q,q_0,F,\delta)$ est un DFA sur
-l'alphabet $\Sigma$, on définit une fonction $\delta^* \colon
-Q\times\Sigma^* \to Q$ par $\delta^*(q,x_1\cdots x_n) =
+\thingy\label{definition-multiple-transition-function} Formellement :
+si $A = (Q,q_0,F,\delta)$ est un DFA sur l'alphabet $\Sigma$, on
+définit une fonction $\delta^* \colon Q\times\Sigma^* \to Q$ par
+$\delta^*(q,x_1\cdots x_n) =
 \delta(\cdots\delta(\delta(q,x_1),x_2)\cdots,x_n)$ ou, ce qui revient
 au même (par récurrence sur la longueur du second argument) :
 \begin{itemize}
@@ -799,14 +802,13 @@ Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$
 $\delta^*(q_0,w) =: q_n \in F$ ; dans le cas contraire, on dira qu'il
 \textbf{rejette} le mot $w$.
 
-L'ensemble $L_A$ des mots acceptés par l'automate $A$ s'appelle
-\textbf{langage accepté}, ou \textbf{reconnu}, ou \textbf{défini}, par
-l'automate $A$.
+\thingy\label{definition-recognizable-language} L'ensemble $L_A$ des
+mots acceptés par l'automate $A$ s'appelle \textbf{langage accepté},
+ou \textbf{reconnu}, ou \textbf{défini}, par l'automate $A$.
 
-\textbf Un langage $L \subseteq \Sigma^*$ qui peut s'écrire sous la
-forme du langage $L_A$ accepté par un DFA $A$ s'appelle
-\textbf{reconnaissable} (sous-entendu : par automate déterministe
-fini).
+Un langage $L \subseteq \Sigma^*$ qui peut s'écrire sous la forme du
+langage $L_A$ accepté par un DFA $A$ s'appelle \textbf{reconnaissable}
+(sous-entendu : par automate déterministe fini).
 
 On dit que deux DFA $A,A'$ sont \textbf{équivalents} lorsqu'ils
 reconnaissent le même langage, i.e., $L_A = L_{A'}$.
@@ -828,10 +830,10 @@ constitue un état acceptant.
   \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] {$a$} (q1);
-  \draw [->] (q1) ..controls (89.406bp,44.625bp) and (91.75bp,54bp)  .. (98bp,54bp) .. controls (102bp,54bp) and (104.4bp,50.152bp)  .. node[auto] {$a,c$} (q1);
+  \draw [->] (q1) to[loop above] node[auto] {$a,c$} (q1);
   \draw [->] (q1) ..controls (126.11bp,18bp) and (138.58bp,18bp)  .. node[auto] {$b$} (q2);
-  \draw [->] (q0) ..controls (9.4062bp,44.625bp) and (11.75bp,54bp)  .. (18bp,54bp) .. controls (22.004bp,54bp) and (24.405bp,50.152bp)  .. node[auto] {$b,c$} (q0);
-  \draw [->] (q2) ..controls (169.41bp,44.625bp) and (171.75bp,54bp)  .. (178bp,54bp) .. controls (182bp,54bp) and (184.4bp,50.152bp)  .. node[auto] {$a,b,c$} (q2);
+  \draw [->] (q0) to[loop above] node[auto] {$b,c$} (q0);
+  \draw [->] (q2) to[loop above] node[auto] {$a,b,c$} (q2);
 %
 \end{tikzpicture}
 
@@ -842,7 +844,8 @@ Cette description rend claire le fait que l'automate en question
 accepte exactement les mots contenant un $a$ suivi, pas forcément
 immédiatement, d'un $b$ ; autrement dit, les mots dont $ab$ est un
 sous-mot (cf. \ref{definition-subword}).  Ce langage est donc
-reconnaissable.
+reconnaissable.  (Il est aussi rationnel puisque désigné par
+l'expression rationnelle $(b|c){*}a(b|c){*}b(a|b|c){*}$.)
 
 \thingy Un état $q$ d'un DFA $A$ est dit \textbf{accessible} lorsqu'il
 existe un mot $w \in \Sigma^*$ tel que $q = \delta(q_0,w)$, autrement
@@ -868,8 +871,8 @@ cet état soit final ou non.
   \node (q2) at (172bp,20.306bp) [draw,circle,state,final] {$2$};
   \draw [->] (q1) ..controls (75.212bp,3.6347bp) and (64.284bp,-1.3057bp)  .. (54bp,1.3057bp) .. controls (50.042bp,2.3107bp) and (46.047bp,3.8633bp)  .. node[auto] {$b$} (q0);
   \draw [->] (q0) ..controls (46.106bp,20.306bp) and (58.578bp,20.306bp)  .. node[auto] {$b$} (q1);
-  \draw [->] (q1) ..controls (90.319bp,47.164bp) and (92.445bp,56.306bp)  .. (98bp,56.306bp) .. controls (101.47bp,56.306bp) and (103.6bp,52.735bp)  .. node[auto] {$a$} (q1);
-  \draw [->] (q0) ..controls (9.4062bp,46.931bp) and (11.75bp,56.306bp)  .. (18bp,56.306bp) .. controls (22.004bp,56.306bp) and (24.405bp,52.458bp)  .. node[auto] {$a$} (q0);
+  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
+  \draw [->] (q0) to[loop above] node[auto] {$a$} (q0);
 %
 \end{tikzpicture}
 
@@ -889,6 +892,166 @@ automates déterministes finis incomplets et on va donc commencer par
 eux.
 
 
+\subsection{Automates finis déterministes à spécification incomplète (=DFAI)}
+
+\thingy Un \textbf{automate fini déterministe à spécification
+  incomplète} ou \textbf{...partielle}, ou simplement \textbf{automate
+  fini déterministe incomplet}, en abrégé \textbf{DFAI}, sur un
+alphabet $\Sigma$ est la donnée
+\begin{itemize}
+\item d'un ensemble fini $Q$ d'états,
+\item d'un état initial $q_0 \in Q$,
+\item d'un ensemble $F \subseteq Q$ d'états finaux,
+\item d'une fonction de transition \emph{partielle}\footnote{Une
+  « fonction partielle » $f\colon X\dasharrow Y$, où $X, Y$ sont deux
+  ensembles est, par définition, la même chose qu'une fonction
+  $f\colon D\to Y$ où $D\subseteq X$ est un sous-ensemble de $X$
+  appelé \textbf{ensemble de définition} de $f$.} $\delta \colon
+  Q\times\Sigma \dasharrow Q$,
+\end{itemize}
+autrement dit, la seule différence avec la définition faite
+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$.
+
+\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
+partant de $q$ et étiquetée par $x$.
+
+\thingy Le fonctionnement d'un DFAI est le même que celui d'un DFA, à
+la modification suivante près : si on donne à consommer à l'automate
+un symbole pour lequel la transition n'est pas définie, i.e., s'il
+rencontre un $x$ pendant qu'il se trouve dans un état $q$ pour lequel
+$\delta(q,x)$ n'est pas défini, alors l'automate cesse de
+fonctionner : l'automate n'a plus d'état, n'effectue plus de
+transition, et n'acceptera pas le mot quelles que soient les lettres
+ultérieures.
+
+\thingy Formellement : si $A = (Q,q_0,F,\delta)$ est un DFAI sur
+l'alphabet $\Sigma$, on définit une fonction $\delta^* \colon
+Q\times\Sigma^* \dasharrow Q$ par $\delta^*(q,x_1\cdots x_n) =
+\delta(\cdots\delta(\delta(q,x_1),x_2)\cdots,x_n)$ avec la convention
+que dès qu'une sous-expression n'est pas définie, toute l'expression
+n'est pas définie, ou, ce qui revient au même (par récurrence sur la
+longueur du second argument) :
+\begin{itemize}
+\item $\delta^*(q,\varepsilon) = q$ quel que soit $q\in Q$ (où
+  $\varepsilon$ désigne le mot vide),
+\item $\delta^*(q,wx) = \delta(\delta^*(q,w),x)$ à condition que $q'
+  := \delta^*(q,w)$ soit défini et que $\delta(q',x)$ le soit (et si
+  ces deux conditions ne sont pas satisfaites, $\delta^*(q,wx)$ n'est
+  pas défini).
+\end{itemize}
+
+Enfin, l'automate $A$ accepte un mot $w$ lorsque $\delta^*(q_0,w)$
+\emph{est défini} et appartient à $F$ ; dans le cas contraire (que ce
+soit parce que $\delta^*(q_0,w)$ n'est pas défini ou parce qu'étant
+défini il n'appartient pas à $F$), l'automate rejette le mot.
+
+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-example2b} Voici un exemple de DFAI sur
+l'alphabet $\Sigma = \{a,b,c\}$.  Cet automate reconnaît exactement
+les mots formés d'un nombre quelconque de $c$, suivis d'un $a$, suivis
+d'un nombre quelconque de $c$, suivis d'un $b$, suivis d'un nombre
+quelconque de $c$.
+
+\begin{center}
+%%% begin example2b %%%
+
+\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] {$a$} (q1);
+  \draw [->] (q1) to[loop above] node[auto] {$c$} (q1);
+  \draw [->] (q1) ..controls (126.11bp,18bp) and (138.58bp,18bp)  .. node[auto] {$b$} (q2);
+  \draw [->] (q0) to[loop above] node[auto] {$c$} (q0);
+  \draw [->] (q2) to[loop above] node[auto] {$c$} (q2);
+%
+\end{tikzpicture}
+
+%%% end example2b %%%
+\end{center}
+
+(Ce langage est aussi désigné par l'expression rationnelle
+$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$.
+\end{prop}
+\begin{proof}
+On définit $Q' = Q \cup \{q_\bot\}$ où $q_\bot$ est un nouvel état
+(n'appartenant pas à $Q$), qu'on appellera « puits ».  On garde l'état
+initial $q'_0 = q_0$.  On garde l'ensemble $F' = F$ d'états finaux,
+c'est-à-dire notamment que le puits n'est pas acceptant.  Enfin, on
+définit $\delta'(q,x)$ pour $q\in Q'$ et $x\in\Sigma$ par
+\[
+\begin{aligned}
+\delta'(q,x) &= \delta(q,x)\text{ si $\delta(q,x)$ est défini}\\
+\delta'(q,x) &= q_\bot\text{ sinon}\\
+\end{aligned}
+\]
+(notamment, $\delta'(q_\bot,x) = q_\bot$ quel que soit $x$).
+
+Il est alors facile de voir que $A'$ a le même comportement que $A$ au
+sens où $\delta^{\prime*}(q,w) = \delta^*(q,w)$ lorsque le terme de
+droite est défini et $\delta^{\prime*}(q,w) = q_\bot$ sinon (le DFA
+$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 À titre d'exemple, le DFA suivant représente la complétion du
+DFAI représenté en \ref{discussion-example2b} :
+
+\begin{center}
+%%% begin example2c %%%
+
+\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,182bp) -- (214bp,182bp) -- (214bp,0bp) -- cycle;
+\end{scope}
+  \node (q1) at (102bp,131bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,85bp) [draw,circle,state,initial] {$0$};
+  \node (q2) at (196bp,85bp) [draw,circle,state,final] {$2$};
+  \node (qbot) at (102bp,22bp) [draw,circle,state] {$\bot$};
+  \draw [->] (q1) to[loop above] node[auto] {$c$} (q1);
+  \draw [->] (q2) to[loop above] node[auto] {$c$} (q2);
+  \draw [->] (qbot) to[loop below] node[auto] {$a,b,c$} (qbot);
+  \draw [->] (q0) ..controls (44.565bp,65.359bp) and (61.506bp,52.343bp)  .. node[auto] {$b$} (qbot);
+  \draw [->] (q0) to[loop above] node[auto] {$c$} (q0);
+  \draw [->] (q1) ..controls (102bp,96.993bp) and (102bp,73.356bp)  .. node[auto] {$a$} (qbot);
+  \draw [->] (q0) ..controls (46.061bp,100.18bp) and (63.141bp,109.76bp)  .. node[auto] {$a$} (q1);
+  \draw [->] (q2) ..controls (166.87bp,65.735bp) and (145.76bp,51.281bp)  .. node[auto] {$a,b$} (qbot);
+  \draw [->] (q1) ..controls (132.83bp,116.08bp) and (154.08bp,105.46bp)  .. node[auto] {$b$} (q2);
+%
+\end{tikzpicture}
+
+%%% end example2c %%%
+\end{center}
+
+
 %
 %
 %