Informal discussion of automata.

1 files changed, 105 insertions, 39 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 82e8241..1dc28e5 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1047,12 +1047,70 @@ langages rationnels.  Il faut imaginer un automate fini comme une
 machine disposant d'une quantité finie (et sous-entendu, très limitée)
 de mémoire : la configuration complète de cette mémoire est décrite
 par un \emph{état}, qui appartient à un ensemble fini d'états
-possibles.  L'automate prendra une décision (passer dans un nouvel
-état) en fonction de son état actuel et de la lettre qu'on lui donne à
-consommer.
+possibles.  On fournit un mot à l'automate en le lui faisant consommer
+lettre par lettre (de la première à la dernière), et à chaque lettre
+qu'il reçoit, l'automate prend une décision (à savoir, passer dans un
+nouvel état) en fonction de son état actuel et de la lettre qu'on lui
+donne à consommer ; l'automate commence par un état dit
+\emph{initial} ; lorsque le mot a été entièrement consommé, l'état
+dans lequel l'automate se trouve a pour conséquence soit que
+l'automate \emph{accepte} le mot (s'il se trouve dans un état
+\emph{final}), soit qu'il le \emph{rejette}.  L'ensemble des mots
+acceptés par l'automate est un langage dit \emph{reconnaissable}.  On
+va voir que ces langages reconnaissables sont en fait les mêmes que
+les langages rationnels définis en \ref{rational-languages}.
+
+\thingy Une subtilité est qu'il existe plusieurs sortes d'automates
+finis.  Nous allons en définir quatre ou cinq, de plus en plus
+généraux, mais nous allons voir qu'ils sont, finalement, tous
+équivalents, c'est-à-dire que leur puissance de calcul, ou les
+langages qu'ils sont capables de reconnaître, sont toujours les mêmes
+(en revanche, cette équivalence peut avoir un coût algorithmique, car
+la conversion d'une sorte d'automate en une autre n'est pas gratuite).
+Du plus particulier au plus général, les automates que nous allons
+définir sont informellement décrits ainsi :
+\begin{itemize}
+\item les automates finis déterministes (complets)
+  (cf. \ref{definition-dfa}) : ceux-ci partent d'un état initial bien
+  défini, suivent à chaque lettre consommée une transition bien
+  définie vers un nouvel état, et leur comportement est donc
+  entièrement déterministe (d'où le nom) ;
+\item les automate fini déterministe à spécification incomplète
+  (cf. \ref{definition-dfai}) : la différence est qu'ici l'automate
+  n'a pas forcément d'instruction sur quoi faire quand il est dans un
+  certain état et reçoit un certain symbole, il peut manquer des
+  transitions, auquel cas l'automate cesse de fonctionner et rejette
+  le mot ;
+\item les automates non-déterministes (cf. \ref{definition-nfa}) :
+  ceux-ci peuvent admettre \emph{plusieurs} possibilités de nouvel
+  état dans lequel transitionner lorsqu'on leur donne une lettre
+  donnée à consommer depuis un état donné, et l'automate accepte le
+  mot s'il y a une manière de faire les transitions qui résulte en ce
+  que le mot soit accepté ;
+\item les automates non-déterministes à transitions spontanées
+  (cf. \ref{definition-enfa}) : ceux-ci ont, en plus des précédents,
+  le pouvoir d'évoluer spontanément, sans consommer de lettre ;
+\item on introduira aussi des automates encore plus généraux, à
+  transitions étiquetées par des expressions rationnelles
+  (cf. \ref{definition-rnfa}) pour montrer que tout langage
+  reconnaissable est rationnel.
+\end{itemize}
 
-\textcolor{red}{TODO: Commencer par une explication informelle et
-  évoquer les différentes sortes d'automates.}
+\thingy Dans tous les cas, les automates se représenteront comme des
+graphes orientés (cf. \ref{discussion-example1} ci-dessous pour un
+exemple simple), dont les sommets sont les états de l'automate (on
+leur donne généralement des noms pour les reconnaître, mais ces noms
+sont arbitraires), dont les arêtes sont étiquetées par des symboles
+(des lettres de l'alphabet, ou éventuellement le mot vide
+$\varepsilon$ ou une expression rationnelle sur l'alphabet), et dont
+certains sommets (=états) sont distingués comme « initiaux » et/ou
+« finaux » (par une flèche pointant depuis nulle part vers l'état en
+question ou depuis l'état en question vers nulle part).
+
+Un mot sera accepté par l'automate toujours selon la même logique :
+s'il y a moyen de relier un état initial à un état final par un chemin
+dans le graphe tel que le mot corresponde à la lecture des étiquettes
+des arêtes du chemin dans l'ordre.
 
 \subsection{Automates finis déterministes complets (=DFA)}
 
@@ -1064,7 +1122,7 @@ consommer.
 \item d'un ensemble fini $Q$ dont les éléments sont appelés
   \defin[état]{états},
 \item d'un état $q_0 \in Q$ appelé \defin[initial (état)]{état
-  initial},
+  initial} (un DFA a un \emph{unique} état initial),
 \item d'un ensemble $F \subseteq Q$ d'états appelés états \defin[final
   (état)]{finaux}\footnote{Le pluriel de « final » est indifféremment
   « finaux » ou « finals ».} ou \index{acceptant
@@ -1077,20 +1135,25 @@ consommer.
 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 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 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.}.
-
-Lorsque plusieurs arêtes étiquetées par des lettres $x,y$ différentes
-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.
+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$, \emph{il existe
+  une unique} arête partant de $q$ et étiquetée par $x$.
+
+En outre, on introduit une flèche pointant de nulle part vers $q_0$
+(pour marquer celui-ci comme l'état initial), 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.} (pour marquer ceux-ci comme
+états finaux).
+
+Pour abréger la représentation graphique, lorsque plusieurs arêtes
+étiquetées par des lettres $x,y$ différentes 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$ », voire « $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\label{discussion-example1} Pour donner un exemple simple,
 l'automate sur $\Sigma = \{a,b\}$ représenté ci-dessous a $Q =
@@ -1098,7 +1161,7 @@ l'automate sur $\Sigma = \{a,b\}$ représenté ci-dessous a $Q =
 $\delta$ donnée par $\delta(0,a) = 0$ et $\delta(0,b) = 1$ et
 $\delta(1,a) = 1$ et $\delta(1,b) = 0$.  On pourra se convaincre (une
 fois lues les définitions plus loin) que cet automate accepte les mots
-dont le nombre de $b$ est pair.
+dont le nombre de $b$ est impair.
 
 \begin{center}
 %%% begin example1 %%%
@@ -1268,13 +1331,14 @@ 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 \defin{automate
-  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é \index{DFAI|see{automate fini déterministe
-    incomplet}}\textbf{DFAI}, sur un alphabet $\Sigma$ est la donnée
+\thingy\label{definition-dfai} Un \textbf{automate fini déterministe à
+  spécification incomplète} ou \textbf{...partielle}, ou simplement
+\defin{automate 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é \index{DFAI|see{automate fini
+    déterministe incomplet}}\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$,
@@ -1462,9 +1526,10 @@ les automates finis déterministes comme étant complets, d'autres comme
 
 \subsection{Automates finis non-déterministes (=NFA)}
 
-\thingy Un \defin{automate fini non-déterministe}, en abrégé
-\index{NFA|see{automate fini non-déterministe}}\textbf{NFA}, sur un
-alphabet $\Sigma$ est la donnée
+\thingy\label{definition-nfa} Un \defin{automate fini
+  non-déterministe}, en abrégé \index{NFA|see{automate fini
+    non-déterministe}}\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,
@@ -1715,8 +1780,9 @@ et l'état $\{0,2\}$ mémorise « la dernière lettre était un $b$, mais
 
 \subsection{Automates finis non-déterministes à transitions spontanées (=εNFA)}
 
-\thingy Un \defin{automate fini non-déterministe à transitions
-  spontanées} ou \textbf{...à $\varepsilon$-transitions}, en abrégé
+\thingy\label{definition-enfa} Un \defin{automate fini
+  non-déterministe à transitions spontanées} ou \textbf{...à
+  $\varepsilon$-transitions}, en abrégé
 \index{epsilon-NFA@$\varepsilon$NFA|see{automate fini non-déterministe
     à transitions spontanées}}\textbf{εNFA}, sur un alphabet $\Sigma$
 est la donnée
@@ -2249,12 +2315,12 @@ si l'automate accepte le mot.
 
 \subsection{Automates à transitions étiquetées par des expressions rationnelles (=RNFA)}
 
-\thingy Un \defin[automate fini à transitions étiquetées par des
-  expressions rationnelles]{automate fini (non-déterministe) à
-  transitions étiquetées par des expressions rationnelles}, en abrégé
-\index{RNFA|see{automate fini à transitions étiquetées par des
-    expressions rationnelles}}\textbf{RNFA}, sur un alphabet $\Sigma$
-est la donnée
+\thingy\label{definition-rnfa} Un \defin[automate fini à transitions
+  étiquetées par des expressions rationnelles]{automate fini
+  (non-déterministe) à transitions étiquetées par des expressions
+  rationnelles}, en abrégé \index{RNFA|see{automate fini à transitions
+    étiquetées par des expressions rationnelles}}\textbf{RNFA}, 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,