diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 72 |
1 files changed, 36 insertions, 36 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 4533160..60881fb 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -1497,7 +1497,7 @@ automates déterministes finis incomplets et on va donc commencer par eux. -\subsection{Automates finis déterministes à spécification incomplète (=DFAI)} +\subsection{Automates finis déterministes à spécification incomplète (=DFAi)} \thingy\label{definition-dfai} Un \textbf{automate fini déterministe à spécification incomplète} ou \textbf{...partielle}, ou simplement @@ -1505,9 +1505,9 @@ eux. incomplet}\footnote{\label{footnote-on-word-incomplete}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 (un DFA est un DFAI particulier, pas le - contraire).}, en abrégé \index{DFAI|see{automate fini déterministe - incomplet}}\textbf{DFAI}, sur un alphabet $\Sigma$ est la donnée + bien être complet (un DFA est un DFAi particulier, pas le + contraire).}, 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$, @@ -1525,24 +1525,24 @@ en \ref{definition-dfa} est que la fonction $\delta$ est partielle, ce qui signifie qu'elle n'est pas obligatoirement définie sur tout couple $(q,x) \in Q\times\Sigma$. -Un DFA est considéré comme un DFAI particulier où la fonction de +Un DFA est considéré comme un DFAi particulier où la fonction de transition $\delta$ se trouve être définie partout. -\thingy Graphiquement, on représente un DFAI comme un DFA, à la +\thingy Graphiquement, on représente un DFAi comme un DFA, à la 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 +L'intérêt informatique des DFAi est de ne pas s'obliger à stocker inutilement des transitions et des états inutiles au sens où ils 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. +souvent algorithmiquement plus judicieux de travailler sur des DFAi. -\thingy Le fonctionnement d'un DFAI est le même que celui d'un DFA, à +\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 rencontre un $x$ pendant qu'il se trouve dans un état $q$ pour lequel @@ -1556,12 +1556,12 @@ 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 +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 +\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) = \delta(\cdots\delta(\delta(q,x_1),x_2)\cdots,x_n)$ avec la convention @@ -1586,7 +1586,7 @@ Le langage accepté $L_A$ et l'équivalence de deux automates sont définis de façon analogue aux DFA (cf. \ref{definition-recognizable-language}). -\thingy\label{discussion-example2b} Voici un exemple de DFAI sur +\thingy\label{discussion-example2b} Voici un exemple de DFAi sur l'alphabet $\Sigma = \{a,b,c\}$. Cet automate reconnaît exactement les mots formés d'un nombre quelconque de $c$, suivis d'un $a$, suivis d'un nombre quelconque de $c$, suivis d'un $b$, suivis d'un nombre @@ -1615,7 +1615,7 @@ quelconque de $c$. $c{*}ac{*}bc{*}$.) \begin{prop}\label{completion-of-dfai} -Soit $A = (Q,q_0,F,\delta)$ un DFAI sur un alphabet $\Sigma$. Alors +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 @@ -1639,7 +1639,7 @@ définit $\delta'(q,x)$ pour $q\in Q'$ et $x\in\Sigma$ par Il est alors facile de voir que $A'$ a le même comportement que $A$ au sens où $\delta^{\prime*}(q,w) = \delta^*(q,w)$ lorsque le terme de droite est défini et $\delta^{\prime*}(q,w) = q_\bot$ sinon (le DFA -$A'$ « tombe dans le puits » lorsque le DFAI $A$ cesse de +$A'$ « tombe dans le puits » lorsque le DFAi $A$ cesse de fonctionner). En particulier, ils reconnaissent les mêmes langages. \end{proof} @@ -1648,7 +1648,7 @@ 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 + 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 vers lequel on fait pointer toutes les transitions manquantes (sauf si $A$ est déjà complet, auquel cas on @@ -1656,7 +1656,7 @@ 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} : +DFAi représenté en \ref{discussion-example2b} : \begin{center} %%% begin example2c %%% @@ -1691,10 +1691,10 @@ DFAI représenté en \ref{discussion-example2b} : \end{center} \thingy\label{coaccessible-and-useful-states} On définit un état -accessible d'un DFAI comme pour un DFA +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 +On dira en outre d'un état $q$ d'un DFAi qu'il est \defin[co-accessible (état)]{co-accessible} lorsqu'il existe un mot $w \in \Sigma^*$ tel que $\delta(q,w)$ soit défini et soit final, autrement dit, graphiquement, lorsqu'il existe un chemin orienté @@ -1703,15 +1703,15 @@ finaux eux-mêmes sont co-accessibles : prendre $w=\varepsilon$ dans ce qu'on vient de dire). Un état non co-accessible est donc un état à partir duquel il est impossible de faire accepter le mot. Cette définition pourrait également être faite pour les DFA, mais pour les -DFAI elle présente l'intérêt qu'on peut supprimer les états -non co-accessibles dans un DFAI (ainsi, bien sûr, que toutes les +DFAi elle présente l'intérêt qu'on peut supprimer les états +non co-accessibles dans un DFAi (ainsi, bien sûr, que toutes les transitions qui y conduisent). -Un DFAI dont tous les états sont à la fois accessibles et +Un DFAi dont tous les états sont à la fois accessibles et co-accessibles (on les dit aussi \defin[utile (état)]{utiles}) est parfois appelé \defin[émondé (automate)]{émondé}. On peut émonder un -DFAI en ne conservant que ses états utiles : ainsi, tout DFAI est -équivalent à un DFAI émondé. +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 » (sans précision supplémentaire) @@ -1773,12 +1773,12 @@ déterminent un unique état $q' = \delta(q,x)$, on a maintenant affaire à un ensemble $\delta$ quelconque de triplets $(q,x,q')$ pour les transitions possibles. -\thingy Un DFAI (ou \textit{a fortiori} un DFA) est considéré comme un +\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 un singleton, $I_{\mathrm{NFA}} = \{q_{0,\mathrm{DFAI}}\}$, et +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 +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 @@ -1798,14 +1798,14 @@ 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 +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 +\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 @@ -1871,7 +1871,7 @@ pouvoir accepter le mot. \medbreak -Comme les DFAI avant eux, les NFA sont en fait équivalents aux DFA ; +Comme les DFAi avant eux, les NFA sont en fait équivalents aux DFA ; mais cette fois-ci, le coût algorithmique de la transformation peut être bien plus important : @@ -2298,7 +2298,7 @@ simplifie la description). (langage)}reconnaissable comme un langage $L$ pour lequel il existe un DFA $A$ tel que $L = L_A$. D'après \ref{completion-of-dfai}, \ref{determinization-of-nfa} et \ref{removal-of-epsilon-transitions}, -on peut remplacer « DFA » dans cette définition par « DFAI », « NFA » +on peut remplacer « DFA » dans cette définition par « DFAi », « NFA » ou « εNFA » sans changer la définition. Nous allons maintenant montrer que les langages reconnaissables sont @@ -2383,7 +2383,7 @@ symboles. La construction de l'automate produit pour fabriquer le langage intersection utilise la caractérisation des langages reconnaissables -par les DFA : elle aurait aussi fonctionné pour les DFAI mais pas pour +par les DFA : elle aurait aussi fonctionné pour les DFAi mais pas pour les NFA ; il est intéressant de réfléchir à pourquoi. (Une construction du type produit pourrait fonctionner sur les NFA pour le langage réunion, mais elle n'a aucun intérêt par rapport à la @@ -3307,7 +3307,7 @@ langage accepté $L_A$ et l'équivalence de deux automates sont définis de façon analogue aux DFA (cf. \ref{definition-recognizable-language}). -\thingy Un εNFA (ou \textit{a fortiori} un NFA, DFAI ou DFA) est +\thingy Un εNFA (ou \textit{a fortiori} un NFA, DFAi ou DFA) est considéré comme un RNFA particulier dont les transitions sont étiquetées soit par une unique lettre (considérée comme expression rationnelle) soit par le symbole $\underline{\varepsilon}$ (dénotant @@ -3335,7 +3335,7 @@ S'il n'y a \emph{aucune} transition de $q$ vers $q'$, on peut toujours choisir d'en ajouter une $(q,\bot,q')$ (qui ne peut pas être empruntée !) si c'est commode. -Comme les εNFA, les NFA et les DFAI avant eux, les RNFA peuvent se +Comme les εNFA, les NFA et les DFAi avant eux, les RNFA peuvent se ramener aux automates précédemment définis : \begin{prop} @@ -3394,7 +3394,7 @@ expressions rationnelles ! \begin{prop}\label{recognizable-languages-are-rational} Soit $A = (Q,I,F,\delta)$ un RNFA (ou, en particulier, un NFA ou -DFA(I)) sur un alphabet $\Sigma$. Alors il existe une expression +DFA(i)) sur un alphabet $\Sigma$. Alors il existe une expression rationnelle $r$ sur $\Sigma$ qui dénote le langage reconnu par $A$, soit $L_r = L_A$. De plus, $r$ se déduit algorithmiquement de $A$. \end{prop} @@ -3585,7 +3585,7 @@ $(0|11|10(1|00){*}01){*}$, qui est équivalente à la précédente. \medbreak -\thingy Donnons encore l'exemple du DFAI suivant : +\thingy Donnons encore l'exemple du DFAi suivant : \begin{center} %%% begin example10 %%% |