More on DFAs.

2 files changed, 131 insertions, 28 deletions

diff --git a/figs/example2.dot b/figs/example2.dot
new file mode 100644
index 0000000..982c3bc
--- /dev/null
+++ b/figs/example2.dot
@@ -0,0 +1,13 @@
+digraph example2 {
+	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="b,c"];
+	q0 -> q1 [label="a"];
+	q1 -> q1 [label="a,c"];
+	q1 -> q2 [label="b"];
+	q2 -> q2 [label="a,b,c"];
+}
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 1efcf60..76e2189 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -181,15 +181,15 @@ des mots \emph{non vides} sur l'alphabet $\Sigma$ (par opposition à
 $\Sigma^*$ qui désigne l'ensemble de tous les mots, y compris le mot
 vide).
 
-\thingy Les mots d'une seule lettre sont naturellement en
-correspondance avec les lettres elles-mêmes : on identifiera souvent
-tacitement, quoique un peu abusivement, une lettre $x\in\Sigma$ et le
-mot de longueur $1$ formé de la seule lettre $x$.  (En informatique,
-cette identification entre \emph{caractères} et \emph{chaînes de
-  caractères de longueur $1$} est faite par certains langages de
-programmation, mais pas par tous : \textit{caveat programmator}.)
-Ceci permet d'écrire par exemple $\Sigma \subseteq \Sigma^*$ ou bien
-$|x|=1 \liff x\in\Sigma$.
+\thingy\label{convention-on-words-of-length-one} Les mots d'une seule
+lettre sont naturellement en correspondance avec les lettres
+elles-mêmes : on identifiera souvent tacitement, quoique un peu
+abusivement, une lettre $x\in\Sigma$ et le mot de longueur $1$ formé
+de la seule lettre $x$.  (En informatique, cette identification entre
+\emph{caractères} et \emph{chaînes de caractères de longueur $1$} est
+faite par certains langages de programmation, mais pas par tous :
+\textit{caveat programmator}.)  Ceci permet d'écrire par exemple
+$\Sigma \subseteq \Sigma^*$ ou bien $|x|=1 \liff x\in\Sigma$.
 
 \thingy\label{number-of-words-of-length-n} Si le cardinal de
 l'alphabet $\Sigma$ vaut $\#\Sigma = N$, alors, pour chaque $n$, le
@@ -326,14 +326,14 @@ est souvent appelé « sous-chaîne [de caractères] ».  Il ne faut
 cependant pas confondre ce concept avec celui de sous-mot défini
 ci-dessous.
 
-\thingy Si $u_0,\ldots,u_r$ et $v_1,\ldots,v_r$ sont des mots sur un
-même alphabet $\Sigma$, on dira que $v := v_1\cdots v_r$ est un
-\textbf{sous-mot} du mot $w := u_0 v_1 u_1 v_2 \cdots u_{r-1} v_r
-u_r$.  En plus clair, cela signifie que $v$ est obtenu en ne gardant
-que certaines lettres du mot $w$ (celles des $v_i$), dans le même
-ordre, mais en en effaçant d'autres (celles des $u_i$) ; à la
-différence du concept de facteur, celui de sous-mot n'exige pas que
-les lettres gardées soient consécutives.
+\thingy\label{definition-subword} Si $u_0,\ldots,u_r$ et
+$v_1,\ldots,v_r$ sont des mots sur un même alphabet $\Sigma$, on dira
+que $v := v_1\cdots v_r$ est un \textbf{sous-mot} du mot $w := u_0 v_1
+u_1 v_2 \cdots u_{r-1} v_r u_r$.  En plus clair, cela signifie que $v$
+est obtenu en ne gardant que certaines lettres du mot $w$ (celles
+des $v_i$), dans le même ordre, mais en en effaçant d'autres (celles
+des $u_i$) ; à la différence du concept de facteur, celui de sous-mot
+n'exige pas que les lettres gardées soient consécutives.
 
 À titre d'exemple, le mot $acb$ est un sous-mot du mot $abbcab$
 (obtenu en gardant les lettres soulignées ici :
@@ -713,17 +713,23 @@ alphabet $\Sigma$ est la donnée
   \textbf{fonction de transition}.
 \end{itemize}
 
-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 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 part\footnote{Certains auteurs
-  préfèrent d'autres conventions, par exemple celle consistant à
-  entourer deux fois les états finaux.}.
+\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
+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
+part\footnote{Certains auteurs préfèrent d'autres conventions, par
+  exemple celle consistant à entourer deux fois les états finaux.}.
+
+Lorsque plusieurs arêtes étiquetées par des symboles $x,y$ différents
+relient les mêmes sommets $q,q'$ (i.e., lorsqu'on a à la fois
+$\delta(q,x) = q'$ et $\delta(q,y) = q'$), on pourra écrire « $x,y$ »
+ou « $x|y$ » sur l'arête en question (et ne la tracer qu'une seule
+fois).  Voir \ref{discussion-example2} ci-dessous pour un exemple.
 
 \thingy Pour donner un exemple simple, l'automate sur $\Sigma =
 \{a,b\}$ représenté ci-dessous a $Q = \{0,1\}$ et $q_0 = 0$ et $F =
@@ -749,6 +755,90 @@ automate accepte les mots dont le nombre de $b$ est pair.
 %%% end example1 %%%
 \end{center}
 
+\thingy Il faut comprendre le fonctionnement d'un DFA de la manière
+suivante : initialement, l'automate est dans l'état initial $q_0$.  On
+va lui présenter un mot $w \in \Sigma^*$, lettre par lettre, de la
+gauche vers la droite : i.e., si $w = x_1\cdots x_n$ on va faire
+consommer à l'automate les lettres $x_1,x_2,\ldots,x_n$ dans cet
+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
+l'automate \emph{acepte} ou \emph{rejette} le mot selon que $q_n \in
+F$ ou que $q_n \not\in F$.
+
+Graphiquement, on peut présenter la procédure de la manière suivante :
+on part de l'état $q_0$ (sommet du graphe représentant l'automate)
+indiqué par la flèche entrante (pointant de nulle part), et pour
+chaque lettre du mot $w = x_1\cdots x_n$ considéré, on suit l'arête
+portant ce symbole (et partant de l'état où on se trouve
+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) =
+\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}
+\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)$ quels que soient
+  $q\in Q$, $w\in\Sigma^*$ et $x\in\Sigma$,
+\end{itemize}
+(en particulier, $\delta^*(q,x) = \delta(q,x)$ si $x\in\Sigma$, donc
+avec la convention faite en \ref{convention-on-words-of-length-one},
+on peut dire que $\delta^*$ prolonge $\delta$).
+
+Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$
+\textbf{accepte} un mot $w$ lorsque $\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$.
+
+\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).
+
+\thingy\label{discussion-example2} L'automate fini ci-dessous sur
+$\Sigma := \{a,b,c\}$ a trois états, $Q = \{0,1,2\}$.  On peut en
+faire la description informelle suivante : l'automate commence dans
+l'état $0$, où il reste jusqu'à rencontrer un $a$ qui le fait passer
+dans l'état $1$, où il reste ensuite jusqu'à rencontrer un $b$ qui le
+fait passer dans l'état $2$, où il reste définitivement et qui
+constitue un état acceptant.
+
+\begin{center}
+%%% begin example2 %%%
+
+\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) ..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) ..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);
+%
+\end{tikzpicture}
+
+%%% end example2 %%%
+\end{center}
+
+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.
+
 
 %
 %