diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 144 |
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, |