diff options
| -rw-r--r-- | notes-inf105.tex | 183 |
1 files changed, 124 insertions, 59 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 1dc28e5..5bce718 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -1109,8 +1109,8 @@ 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. +orienté 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)} @@ -1196,9 +1196,6 @@ 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$. -\textcolor{red}{TODO: Redire en termes de suites d'états comme - en \ref{rnfa-multiple-transition-relation}.} - 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 @@ -1208,10 +1205,27 @@ 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\label{definition-multiple-transition-function} 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) = +Cela revient encore à dire que le mot $w$ est accepté lorsqu'il existe +un chemin orienté dans l'automate, reliant l'état $q_0$ initial à un +état $q_n$ final, et tel que le mot $w = x_1 \cdots x_n$ soit obtenu +en lisant dans l'ordre les étiquettes $x_i$ des différentes arêtes +$q_{i-1} \to q_i$ de ce chemin. Cette définition pourra resservir +presque à l'identique pour les autres sortes d'automates, la +spécificité des DFA est que l'état initial $q_0$ est unique et que +connaissant l'étiquette $x_i$ il n'y a qu'une seule transition +$q_{i-1} \to q_i$ possible (il n'y a pas de choix à faire, pas de +non-déterminisme). + +\thingy\label{definition-multiple-transition-function} Pour donner de +façon plus formelle la définition du langage accepté par un automate, +il sera utile d'introduire une fonction $\delta^*$ de transition +multiple (une généralisation de $\delta$), qui définit l'état +$\delta^*(q,w)$ dans lequel aboutit un DFA si à partir de l'état $q$ +on lui fait consommer successivement les lettres d'un mot $w$. + +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} @@ -1224,7 +1238,7 @@ au même (par récurrence sur la longueur du second argument) : avec la convention faite en \ref{convention-on-words-of-length-one}, on peut dire que $\delta^*$ prolonge $\delta$ ; il sera par ailleurs utile de remarquer que $\delta^*(q,ww') = -\delta^*(\delta^*(q,w),w')$). +\delta^*(\delta^*(q,w),w')$, ce qui se démontre par récurrence). Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$ \defin[accepter]{accepte} ou @@ -1232,8 +1246,6 @@ Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$ $\delta^*(q_0,w) =: q_n \in F$ ; dans le cas contraire, on dira qu'il \textbf{rejette} le mot $w$. -\textcolor{red}{TODO: Explication informelle.} - \thingy\label{definition-recognizable-language} 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$. @@ -1364,6 +1376,15 @@ différence près que pour chaque $q\in Q$ et chaque $x\in \Sigma$, il y a maintenant \emph{au plus une} (et non plus exactement une) arête partant de $q$ et étiquetée par $x$. +L'intérêt informatique des DFAI est de ne pas s'obliger à stocker +inutilement des transitions et de états inutiles au sens où elles ne +permettront jamais d'accepter le mot (voir la notion d'automate +« émondé » en \ref{coaccessible-and-useful-states} ci-dessous). C'est +la raison pour laquelle, même si les DFA complets sont théoriquement +plus satisfaisants à manier (pour la même raison qu'une fonction +totale est plus satisfaisante qu'une fonction partielle), il est +souvent algorithmiquement plus judicieux de travailler sur des DFAI. + \thingy Le fonctionnement d'un DFAI est le même que celui d'un DFA, à la modification suivante près : si on donne à consommer à l'automate une lettre pour laquelle la transition n'est pas définie, i.e., s'il @@ -1373,6 +1394,16 @@ fonctionner : l'automate n'a plus d'état, n'effectue plus de transition, et n'acceptera pas le mot quelles que soient les lettres ultérieures. +Cela revient une fois de plus à dire que le mot $w$ est accepté +lorsqu'il existe un chemin orienté dans l'automate, reliant l'état +$q_0$ initial à un état $q_n$ final, et tel que le mot $w = x_1 \cdots +x_n$ soit obtenu en lisant dans l'ordre les étiquettes $x_i$ des +différentes arêtes $q_{i-1} \to q_i$ de ce chemin. La différence des +DFAI par rapport aux DFA est que, cette fois, la tentative de chemin +pourrait s'arrêter prématurément (on ne peut plus consommer un symbole +et passer dans un nouvel état, et à plus forte raison, aboutir à un +état final). + \thingy Formellement : si $A = (Q,q_0,F,\delta)$ est un DFAI sur l'alphabet $\Sigma$, on définit une fonction $\delta^* \colon Q\times\Sigma^* \dasharrow Q$ par $\delta^*(q,x_1\cdots x_n) = @@ -1431,8 +1462,8 @@ Soit $A = (Q,q_0,F,\delta)$ un DFAI sur un alphabet $\Sigma$. Alors il existe un DFA $A' = (Q',q'_0,F',\delta')$ (sur le même alphabet $\Sigma$) qui soit équivalent à $A$ au sens où il reconnaît le même langage $L_{A'} = L_A$. De plus, $A'$ se déduit -algorithmiquement de $A$ en ajoutant au plus un état \defin[puits - (état)]{puits} à $A$ : on a $\#Q' \leq \#Q + 1$. +algorithmiquement de $A$ en ajoutant au plus un état « puits » à $A$ : +on a $\#Q' \leq \#Q + 1$. \end{prop} \begin{proof} On définit $Q' = Q \cup \{q_\bot\}$ où $q_\bot$ est un nouvel état @@ -1455,12 +1486,17 @@ $A'$ « tombe dans le puits » lorsque le DFAI $A$ cesse de fonctionner). En particulier, ils reconnaissent les mêmes langages. \end{proof} -\thingy On dit que le DFA $A'$ est obtenu en \defin[compléter (un +\thingy De façon générale, un état \defin[puits (état)]{puits} dans un +DFA est un état $q_\bot$ tel que $\delta(q_\bot,x)=q_\bot$ pour toute +lettre $x$. + +On dit que le DFA $A'$ est obtenu en \defin[compléter (un DFAI)]{complétant} le DFAI $A$ lorsqu'il est obtenu par la procédure décrite dans la démonstration de cette proposition, c'est-à-dire par -l'addition d'un état puits, sauf si $A$ est déjà complet, auquel cas -on convient qu'il est son propre complété (i.e., on n'ajoute un puits -que quand c'est réellement nécessaire). +l'addition d'un état puits vers lequel on fait pointer toutes les +transitions manquantes (sauf si $A$ est déjà complet, auquel cas on +convient qu'il est son propre complété, i.e., on n'ajoute un puits que +quand c'est réellement nécessaire). \thingy À titre d'exemple, le DFA suivant représente la complétion du DFAI représenté en \ref{discussion-example2b} : @@ -1497,7 +1533,8 @@ DFAI représenté en \ref{discussion-example2b} : %%% end example2c %%% \end{center} -\thingy On définit un état accessible d'un DFAI comme pour un DFA +\thingy\label{coaccessible-and-useful-states} On définit un état +accessible d'un DFAI comme pour un DFA (cf. \ref{definition-dfa-accessible-state}). On dira en outre d'un état $q$ d'un DFAI qu'il est @@ -1520,12 +1557,40 @@ 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. +les « automates finis déterministes » (sans précision supplémentaire) +comme étant complets par défaut, d'autres comme étant incomplets par +défaut. \subsection{Automates finis non-déterministes (=NFA)} +\thingy\textbf{Idée générale :} Le principe directeur général du +non-déterminisme en informatique est, grossièrement parlant, le +suivant : on a un mécanisme de calcul (ici, un automate fini) qui doit +accepter ou rejeter une certaine donnée (ici, un mot qui lui est +présenté), mais plutôt que d'évoluer de façon déterministe d'une +configuration à une autre (ici, d'un état à un autre), il se peut +qu'il existe plusieurs possibilités différentes, autrement dit, une +configuration peut évoluer de plusieurs manières différentes, ce qui +donne lieu à plusieurs chemins de calcul différents. Selon le point +de vue qu'on adopte, et éventuellement la stratégie algorithmique pour +modéliser le non-déterminisme, on peut considérer que ces chemins sont +empruntés tous simultanément (et qu'on est dans tous les états +possibles à la fois\footnote{Certains sont parfois tentés de comparer + avec une superposition quantique : il existe effectivement une + analogie, mais le quantique implique une description bien précise + des états (avec des amplitudes associées) qui n'est pas pertinente + ici, et l'analogie mal appliquée conduirait à des erreurs en + complexité algorithmique ; il vaut donc mieux ne pas y penser.}, +c'est d'ailleurs l'approche qui servira +en \ref{determinization-of-nfa}), ou que tous les chemins possibles +sont testés successivement, ou encore que l'appareil non-déterministe +« devine » quel est le bon ; mais en tout cas la règle fondamentale du +non-déterminisme est toujours la suivante : \emph{la donnée est + acceptée dès lors qu'il existe au moins un chemin de calcul possible + qui conduit à l'accepter} (dans notre cas, cela signifiera au moins +un chemin acceptant le mot). + \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 @@ -1538,19 +1603,21 @@ donnée de)}transition $\delta \subseteq Q \times \Sigma \times Q$ (c'est-à-dire une partie du produit cartésien $Q \times \Sigma \times Q$, i.e., un ensemble de triplets $(q,x,q') \in Q \times - \Sigma \times Q$). + \Sigma \times Q$) ; lorsque $(q,x,q') \in \delta$, on dira qu'il + existe une transition étiquetée par $x$ de $q$ vers $q'$. \end{itemize} Autrement dit, on autorise maintenant un ensemble quelconque d'états initiaux, et de même, au lieu qu'un état $q$ et une lettre $x$ déterminent un unique état $q' = \delta(q,x)$, on a maintenant affaire -à un ensemble quelconque de triplets $(q,x,q')$. +à un ensemble quelconque de triplets $(q,x,q')$. \thingy Un DFAI (ou \textit{a fortiori} un DFA) est considéré comme un NFA particulier en définissant l'ensemble des états initiaux du NFA -comme $I_{\mathrm{NFA}} = \{q_{0,\mathrm{DFAI}}\}$ et en définissant -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'$). +comme un singleton, $I_{\mathrm{NFA}} = \{q_{0,\mathrm{DFAI}}\}$, et +en définissant 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 graphe orienté dont les nœuds sont les éléments de $Q$, et où on place @@ -1560,38 +1627,36 @@ flèche entrante (i.e., pointant de nulle part) et les états finaux par une flèche sortante (i.e., pointant vers nulle part). \thingy Il faut comprendre le fonctionnement d'un NFA de la manière -suivante : un mot $w = x_1\cdots x_n$ est accepté par l'automate -lorsqu'\emph{il existe} un chemin conduisant d'\emph{un} état initial -à un état final et dont les arêtes sont étiquetées par les lettres -$x_1,\ldots,x_n$ de $w$ (dans l'ordre) ; autrement dit, $w$ est -accepté lorsqu'\emph{il existe} $q_0,\ldots,q_n \in Q$ tels que $q_0 -\in I$ et $q_n\in F$ et $(q_{i-1},x_i,q_i) \in \delta$ pour -chaque $1\leq i\leq n$. - -Il existe plusieurs manières de reformuler ce comportement : on peut -par exemple dire que l'automate est dans plusieurs états à la fois, -qu'il commence dans tous les états initiaux à la fois, et qu'à chaque -fois qu'il consomme une lettre $x$, il effectue toutes les transitions -possibles à partir d'un état où et étiquetées par cette lettre, et -qu'au bout du compte l'automate accepte le mot lorsqu'il est dans -\emph{au moins un} état acceptant (même s'il est, par ailleurs, dans -d'autres états). C'est cette façon de voir les choses qui conduira à -l'équivalence entre NFA et DFA (cf. \ref{determinization-of-nfa}). - -Une autre façon de présenter les choses est que l'automate « devine » -par quel état initial commencer, et à chaque lettre consommée, -« devine » quelle transition effectuer, de manière à accepter le mot -si c'est possible. - -En tout état de cause, la définition formelle va être donnée -ci-dessous. - -\thingy Si $A = (Q,I,F,\delta)$ est un NFA sur l'alphabet $\Sigma$, on -définit une relation $\delta^* \subseteq Q \times \Sigma^* \times Q$ -par $(q,w,q') \in \delta^*$ lorsque $w = x_1\cdots x_n$ et qu'il -existe $(q_0,\ldots,q_n)$ tels que $q_0 = q$ et $q_n = q'$ et -$(q_{i-1},x_i,q_i) \in \delta$ pour chaque $1\leq i\leq n$ ; ou, ce -qui revient au même (par récurrence sur la longueur de $w$) : +suivante : un mot $w$ est accepté par l'automate lorsqu'\emph{il + existe} un chemin orienté conduisant d'\emph{un} état initial $q_0$ +à un état final $q_n$ et tel que le mot $w = x_1 \cdots x_n$ soit +obtenu en lisant dans l'ordre les étiquettes $x_i$ des différentes +arêtes $q_{i-1} \to q_i$ de ce chemin ; autrement dit, $w$ est accepté +lorsqu'\emph{il existe} $q_0,\ldots,q_n \in Q$ tels que $q_0 \in I$ et +$q_n\in F$ et $(q_{i-1},x_i,q_i) \in \delta$ pour chaque $1\leq i\leq +n$. + +La différence cruciale avec les DFAI est donc que, maintenant, il +pourrait exister plusieurs chemins possibles partant d'un état initial +dont les transitions sont étiquetées par les lettres du même mot. +Insistons bien sur le fait que le mot est accepté dès lors que +\emph{l'un} au moins de ces chemins relie un état initial à un état +final. + +\thingy De même que dans le cadre des DFA et DFAI on a étendu la +fonction de transition $\delta$ à une fonction $\delta^*$ qui décrit +le comportement de l'automate quand on consomme plusieurs caractères +(cf. \ref{definition-multiple-transition-function}), on va étendre la +relation de transition $\delta$ d'un NFA à la situation où on consomme +plusieurs caractères. + +Formellement : si $A = (Q,I,F,\delta)$ est un NFA sur +l'alphabet $\Sigma$, on définit une relation $\delta^* \subseteq Q +\times \Sigma^* \times Q$ par $(q,w,q') \in \delta^*$ lorsque $w = +x_1\cdots x_n$ et qu'il existe $(q_0,\ldots,q_n)$ tels que $q_0 = q$ +et $q_n = q'$ et $(q_{i-1},x_i,q_i) \in \delta$ pour chaque $1\leq +i\leq n$ ; ou, ce qui revient au même (par récurrence sur la longueur +de $w$) : \begin{itemize} \item $(q,\varepsilon,q') \in \delta^*$ si et seulement si $q'=q$, \item $(q,wx,q') \in \delta^*$ si et seulement si il existe $q^\sharp$ |