summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex144
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,