Various clarifications. Try to explicitate when DFAs need to be complete.

1 files changed, 72 insertions, 52 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 3e2e511..e027205 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1049,8 +1049,10 @@ eux.
 
 \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
+  fini déterministe incomplet}\footnote{Le mot « incomplet » signifie
+  en fait « non nécessairement complet », i.e., l'automate a le droit
+  de manquer certaines transitions, il peut très bien être complet.},
+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$,
@@ -1059,7 +1061,8 @@ alphabet $\Sigma$ est la donnée
   « 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
+  appelé \textbf{ensemble de définition} de $f$.  (Lorsque en fait
+  $D=X$, la fonction est dite « totale ».)} $\delta \colon
   Q\times\Sigma \dasharrow Q$,
 \end{itemize}
 autrement dit, la seule différence avec la définition faite
@@ -1228,6 +1231,10 @@ co-accessibles (on les dit aussi \textbf{utiles}) est parfois appelé
 \textbf{émondé}.  On peut émonder un DFAI en ne conservant que ses
 états utiles : ainsi, tout DFAI est équivalent à un DFAI émondé.
 
+\thingy Il faut prendre garde au fait que certains auteurs définissent
+les automates finis déterministes comme étant complets, d'autres comme
+étant incomplets.
+
 
 \subsection{Automates finis non-déterministes (=NFA)}
 
@@ -1254,7 +1261,7 @@ la relation de transition du NFA comme le graphe de la fonction de
 transition du DFAI (c'est-à-dire $(q,x,q') \in \delta_{\mathrm{NFA}}$
 lorsque $\delta_{\mathrm{DFAI}}(q,x)$ est défini et vaut $q'$).
 
-\thingy Graphiquement, on représente un NFA comme un DFA comme un
+\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
@@ -1716,11 +1723,11 @@ plus, un DFA reconnaissant l'un se déduit algorithmiquement d'un DFA
 reconnaissant l'autre.
 \end{prop}
 \begin{proof}
-Par hypothèse, il existe un DFA $A = (Q,q_0,F,\delta)$ tel que $L =
-L_A$.  Considérons le DFA $A'$ défini par l'ensemble d'états $Q' = Q$,
-l'état initial $q'_0 = q_0$, la fonction de transition $\delta' =
-\delta$ et pour seul changement l'ensemble d'états finaux $F' = Q
-\setminus F$ complémentaire de $F$.
+Par hypothèse, il existe un DFA (complet !) $A = (Q,q_0,F,\delta)$ tel
+que $L = L_A$.  Considérons le DFA $A'$ défini par l'ensemble d'états
+$Q' = Q$, l'état initial $q'_0 = q_0$, la fonction de transition
+$\delta' = \delta$ et pour seul changement l'ensemble d'états finaux
+$F' = Q \setminus F$ complémentaire de $F$.
 
 Si $w \in \Sigma^*$, on a $w \in L_{A'}$ si et seulement si
 $\delta^{\prime*}(q_0,w) \in F'$, c'est-à-dire $\delta^*(q_0,w) \in
@@ -1732,7 +1739,11 @@ L_A$.  Ceci montre bien que $L_{A'}$ est le complémentaire de $L_A$.
 \thingy Cette démonstration a utilisé la caractérisation des langages
 reconnaissables par les DFA : il était crucial de le faire, et les
 autres sortes d'automates définis plus haut n'auraient pas permis
-d'arriver (simplement) à la même conclusion.  Pourquoi ?
+d'arriver (simplement) à la même conclusion.  Il est intéressant de
+réfléchir à pourquoi.  (Essentiellement, dans un NFA, un mot est
+accepté dès qu'\emph{il existe} un chemin qui l'accepte, or
+l'existence d'un chemin aboutissant à un état non-final n'est pas la
+même chose que l'inexistence d'un chemin aboutissant à un état final.)
 
 \begin{prop}\label{dfa-union-and-intersection}
 Si $L_1,L_2$ sont des langages reconnaissables (sur un même
@@ -1742,36 +1753,45 @@ l'un comme l'autre se déduit algorithmiquement de DFA reconnaissant
 $L_1$ et $L_2$.
 \end{prop}
 \begin{proof}
-Par hypothèse, il existe des DFA $A_1 = (Q_1,q_{0,1},F_1,\delta_1)$ et
-$A_2 = (Q_2,q_{0,2},F_2,\delta_2)$ tels que $L_1 = L_{A_1}$ et $L_2 =
+Traitons le cas de l'intersection.  Par hypothèse, il existe des DFA
+(complets !) $A_1 = (Q_1,q_{0,1},F_1,\delta_1)$ et $A_2 =
+(Q_2,q_{0,2},F_2,\delta_2)$ tels que $L_1 = L_{A_1}$ et $L_2 =
 L_{A_2}$.  Considérons le DFA $A'$ défini par l'ensemble d'états $Q' =
-Q_1 \times Q_2$, l'état initial $q'_0 = (q_{0,1},q_{0,2})$, la
-fonction de transition $\delta' \colon ((p_1,p_2),x) \mapsto
-(\delta_1(p_1,x), \delta_2(p_2,x))$ et pour ensemble d'états finaux
-$F' = (F_1\times Q_2) \cup (Q_1 \times F_2)$ (si on cherche à
-reconnaître $L_1\cup L_2$) respectivement $F' = F_1\times F_2$ (si on
-cherche à reconnaître $L_1\cap L_2$).  Remarquons que $(p_1,p_2) \in
-Q'$ appartient à $F' = (F_1\times Q_2) \cup (Q_1 \times F_2)$
-respectivement $F' = F_1\times F_2$ si et seulement si $p_1 \in F_1$
-ou $p_2 \in F_2$ respectivement $p_1 \in F_1$ et $p_2 \in F_2$.  Par
-ailleurs, si $w\in \Sigma^*$, on a $\delta'(q_0',w) =
-(\delta_1(q_{0,1},w), \delta_2(q_{0,2},w))$.  On voit donc qu'un mot
-$w$ appartient à $L_{A'}$ si et seulement il appartient à $L_1 \cup
-L_2$ respectivement $L_1 \cap L_2$, ce qu'il fallait démontrer.
+Q_1 \times Q_2$ (c'est-à-dire l'ensemble des couples formés d'un état
+de $A_1$ et d'un état de $A_2$), l'état initial $q'_0 =
+(q_{0,1},q_{0,2})$, la fonction de transition $\delta' \colon
+((p_1,p_2),x) \mapsto (\delta_1(p_1,x), \delta_2(p_2,x))$ et pour
+ensemble d'états finaux $F' = F_1\times F_2$.  Remarquons que
+$(p_1,p_2) \in Q'$ appartient à $F' = F_1\times F_2$ si et seulement
+si $p_1 \in F_1$ \emph{et} $p_2 \in F_2$ (i.e., $F' \subseteq Q'$ est
+l'ensemble des couples dont les deux composantes sont finales).  Par
+ailleurs, si $w\in \Sigma^*$, on a $\delta^{\prime*}(q_0',w) =
+(\delta_1^*(q_{0,1},w), \delta_2^*(q_{0,2},w))$, et par ce qui vient
+d'être dit, ceci appartient à $F'$ si et seulement
+$\delta_1^*(q_{0,1},w) \in F_1$ et $\delta_2^*(q_{0,2},w) \in F_2$.
+On voit donc qu'un mot $w$ appartient à $L_{A'}$ si et seulement il
+appartient à la fois à $L_1$ et à $L_2$, ce qu'il fallait démontrer.
+
+Pour la réunion, on peut invoquer le fait que la réunion est le
+complémentaire de l'intersection des complémentaires, et
+utiliser \ref{dfa-complement} ; si on déroule cette démonstration, on
+voit qu'on construit un DFA $A''$ exactement égal à $A'$ construit
+ci-dessus, à la seule différence près que son ensemble d'états finaux
+est $F'' = (F_1\times Q_2) \cup (Q_1\times F_2)$, qui est le
+sous-ensemble de $Q'' = Q_1\times Q_2$ formé des couples dont
+\emph{l'une au moins} des deux composantes est finale.
 \end{proof}
 
-\thingy On pouvait aussi traiter uniquement l'une des deux opérations
-booléennes et déduire l'autre par complémentaire, mais le gain de
-place est faible (et la construction est exactement la même).
+\thingy La construction $A'$ ci-dessus est parfois appelée
+\emph{produit} des DFA $A_1$ et $A_2$.
 
-La construction ci-dessus est un \emph{produit} de DFA (que ce soit
-pour prendre la réunion ou l'intersection).  La construction produit
-fonctionnerait encore avec les NFA \emph{pour la réunion de langages
-  mais pas pour l'intersection} : il est intéressant de réfléchir à
-pourquoi (essentiellement, ce qui casse la symétrie est que dans un
-NFA, un mot est accepté dès qu'\emph{il existe} un chemin qui
-l'accepte, or le quantificateur $\exists$ distribue sur les
-disjonctions mais pas sur les conjonctions).
+La construction de l'automate produit pour fabriquer le langage
+intersection utilise la caractérisation des langages reconnaissables
+par les DFA : elle aurait aussi fonctionné pour les DFAI mais pas pour
+les NFA ; il est intéressant de réfléchir à pourquoi.  (Une
+construction du type produit pourrait fonctionner sur les NFA pour le
+langage réunion, mais elle n'a aucun intérêt par rapport à la
+construction présentée en \ref{nfa-union}.)
 
 \begin{prop}\label{nfa-mirror}
 Si $L$ est un langage reconnaissable sur un alphabet $\Sigma$, alors
@@ -2259,12 +2279,12 @@ factorisation $t = uvw$ en trois facteurs $u,v,w$ où :
 \end{itemize}
 \end{prop}
 \begin{proof}
-Soit $A$ un DFA qui reconnaît $L$, et soit $k$ son nombre d'états : on
-va montrer que $k$ vérifie les propriétés énoncées.  Pour cela, soit
-$t = x_1 \cdots x_n$ un mot de $L$ de longueur $n \geq k$, et soient
-$q_0,\ldots,q_n$ les états traversés par $A$ pendant la consommation
-de $t$, autrement dit, $q_0$ est l'état initial, et $q_j =
-\delta(q_{j-1}, x_j)$ pour chaque $1\leq j\leq n$ ; l'état $q_n =
+Soit $A$ un DFA (complet) qui reconnaît $L$, et soit $k$ son nombre
+d'états : on va montrer que $k$ vérifie les propriétés énoncées.  Pour
+cela, soit $t = x_1 \cdots x_n$ un mot de $L$ de longueur $n \geq k$,
+et soient $q_0,\ldots,q_n$ les états traversés par $A$ pendant la
+consommation de $t$, autrement dit, $q_0$ est l'état initial, et $q_j
+= \delta(q_{j-1}, x_j)$ pour chaque $1\leq j\leq n$ ; l'état $q_n =
 \delta^*(q_0, t)$ est final puisque $t \in L$.  Comme $n+1 > k$ et
 comme l'automate $A$ a $k$ états, par le principe des tiroirs, il
 existe $j_1\neq j_2$ tels que $q_{j_1} = q_{j_2}$ : pour être plus
@@ -2384,11 +2404,11 @@ Alors :
 \item le langage $L$ est rationnel si et seulement si la relation
   d'équivalence $\equiv$ possède un nombre \emph{fini} $k$ de classes
   d'équivalence,
-\item lorsque c'est le cas, il existe un DFA ayant $k$ états qui
-  reconnaît $L$, il est unique à renommage des
+\item lorsque c'est le cas, il existe un DFA (complet) ayant $k$ états
+  qui reconnaît $L$, il est unique à renommage des
   états\footnote{C'est-à-dire, si on préfère ce terme, isomorphisme
-    d'automates.} près, et il n'existe pas de DFA ayant $<k$ états qui
-  reconnaisse $L$.
+    d'automates.} près, et il n'existe pas de DFA (complet) ayant $<k$
+  états qui reconnaisse $L$.
 \end{itemize}
 \end{thm}
 \begin{proof}
@@ -2456,12 +2476,12 @@ isomorphisme d'automates (un renommage des états).
 \end{proof}
 
 \thingy Ce théorème affirme donc qu'il existe (à renommage des états
-près) un unique DFA ayant un nombre minimal d'états parmi ceux qui
-reconnaissent le langage rationnel $L$ : on l'appelle \textbf{automate
-  canonique} ou \textbf{automate minimal} du langage $L$.  La
-démonstration ci-dessus en donne une construction à partir d'une
-relation d'équivalence, mais cette démonstration n'est pas
-algorithmique : on va voir comment on peut le construire de fącon
+près) un unique DFA (complet) ayant un nombre minimal d'états parmi
+ceux qui reconnaissent le langage rationnel $L$ : on l'appelle
+\textbf{automate canonique} ou \textbf{automate minimal} du
+langage $L$.  La démonstration ci-dessus en donne une construction à
+partir d'une relation d'équivalence, mais cette démonstration n'est
+pas algorithmique : on va voir comment on peut le construire de fącon
 algorithmique à partir d'un DFA quelconque qui reconnaît $L$.
 
 \begin{prop}