diff options
| -rw-r--r-- | notes-inf105.tex | 269 |
1 files changed, 151 insertions, 118 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 68e1c65..b72b754 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -820,8 +820,9 @@ caractères \emph{n'appartenant pas} à l'alphabet $\Sigma$, appelés \defin[métacaractère]{métacaractères}, et qui servent à marquer la manière dont est formée l'expression rationnelle. On définit simultanément la notion d'expression rationnelle $r$ et de -\defin[dénoté (langage)]{langage dénoté} (ou \textbf{désigné}) $L_r$ -par l'expression $r$, de la manière suivante : +\defin[dénoté (langage)]{langage dénoté} (ou \textbf{désigné} ou +simplement \textbf{défini}) $L_r$ par l'expression $r$, de la manière +suivante : \begin{itemize} \item $\bot$ est une expression rationnelle et son langage dénoté est $L_\bot := \varnothing$, @@ -995,34 +996,40 @@ sens mathématique défini ci-dessus : différentes extensions permettent de désigner des langages qui ne sont pas rationnels au sens mathématique. L'extension la plus fréquente est celle des \emph{références arrière} (ou \emph{backreferences} en anglais) qui -permettent de demander qu'un facteur du mot se retrouve à un autre -emplacement. Par exemple, pour beaucoup de moteurs (notamment -\texttt{egrep}), l'expression régulière \texttt{(a*)b\char"5C\relax 1} +permettent de demander qu'un facteur du mot se retrouve aussi à un +autre emplacement. Par exemple, pour beaucoup de moteurs (notamment +\texttt{egrep}), l'expression régulière « \texttt{(a*)b\char"5C\relax 1} » désigne le langage $\{a^nba^n : a\in\mathbb{N}\} = \{b,aba, aabaa,\ldots\}$ des mots formés d'un nombre quelconque de $a$ puis d'un $b$ puis de la \emph{même suite de $a$}, et ce langage \emph{n'est pas rationnel} au sens mathématique (ce sera une conséquence du « lemme de pompage » \ref{pumping-lemma}). -\thingy\label{remarks-egrep-plus-etc} Il existe aussi un certain nombre de constructions qui, sans -dépasser la puissance des expressions rationnelles au sens -mathématique, apportent des commodités d'écriture dans un contexte -informatique. On a déjà mentionné les symboles \texttt{+} (pour « au -moins une répétition » : $r{\scriptstyle +}$ est équivalent à $rr{*}$) -et \texttt{?} (pour « au plus une répétition » : $r{?}$ est équivalent -à $(\underline{\varepsilon}|r)$). Parmi d'autres constructions du -genre, mentionnons encore le point \texttt{.} qui désigne un caractère -quelconque de l'alphabet (on peut le voir comme une abréviation pour -$(x_1|x_2|\ldots|x_N)$ où $x_1,x_2,\ldots,x_N$ sont tous les éléments -de $\Sigma$ — ce qui serait très fastidieux à écrire si on devait -énumérer tout Unicode), ou bien \texttt{[$xyz$]} qui désigne un -caractère quelconque parmi ceux listés (c'est donc la même chose que -$(x|y|z)$ mais cela ne fonctionne qu'avec des caractères individuels ; -en contrepartie, on peut écrire des intervalles comme \texttt{[a-z]} -qui désigne un caractère quelconque entre \texttt{a} et \texttt{z} -dans l'ordre ASCII/Unicode, ou bien des négations d'intervalles comme -\texttt{[\char"5Ea-z]} qui désigne un caractère qui \emph{n'est pas} -entre \texttt{a} et \texttt{z}). +\thingy\label{remarks-egrep-plus-etc} Il existe aussi un certain +nombre de constructions qui, sans dépasser la puissance des +expressions rationnelles au sens mathématique, apportent des +commodités d'écriture dans un contexte informatique. On a déjà +mentionné les symboles \texttt{+} (pour « au moins une répétition » : +« $r{\scriptstyle +}$ » est équivalent à $rr{*}$) et \texttt{?} (pour +« au plus une répétition » : « $r{?}$ » est équivalent à +$(\underline{\varepsilon}|r)$). Parmi d'autres constructions du +genre, mentionnons encore le point « \texttt{.} » qui désigne un +caractère quelconque de l'alphabet (on peut le voir comme une +abréviation pour $(x_1|x_2|\ldots|x_N)$ où $x_1,x_2,\ldots,x_N$ sont +tous les éléments de $\Sigma$ — ce qui serait très fastidieux à écrire +si on devait énumérer tout Unicode), ou bien « \texttt{[$xyz$]} » qui +désigne un caractère quelconque parmi ceux listés (c'est donc la même +chose que $(x|y|z)$ mais cela ne fonctionne qu'avec des caractères +individuels ; en contrepartie, on peut écrire des intervalles comme +« \texttt{[a-z]} » qui désigne un caractère quelconque entre +\texttt{a} et \texttt{z} dans l'ordre ASCII/Unicode\footnote{...ou + parfois l'ordre de tri défini par la locale en cours : c'est + malheureusement une source supplémentaire de confusion et de bugs.}, +ou bien des négations, comme « \texttt{[\char"5Ea-z]} » qui désigne un +caractère qui \emph{n'est pas} entre \texttt{a} et \texttt{z}) ou +« \texttt{[\char"5Eaeio-z]} » qui désigne un caractère qui \emph{n'est + ni} \texttt{a} ni \texttt{e} ni\texttt{i} ni entre \texttt{o} +et \texttt{z}). Toutes sortes d'autres racourcis ou commodités de notation peuvent exister, par exemple \texttt{\char"5C<} et \texttt{\char"5C>} pour @@ -1033,40 +1040,42 @@ entre $n_1$ et $n_2$ répétitions de $r$. \thingy Une autre subtilité est que la plupart des moteurs d'expressions régulières en informatique vont, par défaut, \emph{rechercher un facteur} (appelé « sous-chaîne » en informatique) -vérifiant l'expression à l'intérieur de la chaîne donnée, plutôt que -tester si la chaîne elle-même vérifie l'expression. Pour éviter ce -comportement, on peut utiliser des \emph{ancres}, typiquement -commandées par les caractères \texttt{\char"5E} et \texttt{\char"24} -qui servent à ancrer l'expression au début et à la fin de la chaîne -respectivement : c'est-à-dire que rechercher \texttt{a} recherche un -\texttt{a} quelconque à l'intérieur de la chaîne donnée, rechercher -\texttt{\char"5E\relax a} demande que le \texttt{a} soit au début de -la chaîne donnée rechercher \texttt{a\char"24} demande que le +vérifiant l'expression \emph{à l'intérieur} de la chaîne donnée, +plutôt que tester si la chaîne tout entière vérifie l'expression. +Pour éviter ce comportement, on peut utiliser des \index{ancre + (métacaractère)}\emph{ancres}, typiquement commandées par les +(méta)caractères « \texttt{\char"5E} » et « \texttt{\char"24} » qui +servent à ancrer l'expression au début et à la fin de la chaîne +respectivement : c'est-à-dire que rechercher « \texttt{a} » recherche +un \texttt{a} quelconque à l'intérieur de la chaîne donnée, rechercher +« \texttt{\char"5E\relax a} » demande que le \texttt{a} soit au début +de la chaîne donnée rechercher « \texttt{a\char"24} » demande que le \texttt{a} soit à la fin de la chaîne donnée, et rechercher -\texttt{\char"5E\relax a\char"24} demande que la chaîne donnée soit -exactement \texttt{a} (cet exemple n'est donc pas très utile, mais de -façon générale, trouver si une chaîne vérifie une expression -rationnelle $r$, revient à y chercher \texttt{\char"5E\relax - $r$\char"24}). +« \texttt{\char"5E\relax a\char"24} » demande que la chaîne donnée +soit exactement \texttt{a} (cet exemple n'est donc pas très utile, +mais de façon générale, trouver si une chaîne vérifie une expression +rationnelle $r$, revient à y chercher « \texttt{\char"5E\relax + $r$\char"24} »). \thingy Comme les expressions régulières en informatique sont représentées par des chaînes de caractères qui appartiennent au même alphabet (ASCII ou Unicode) que les chaînes sur lesquelles on effectue la recherche, le problème se pose de distinguer les métacaractères (l'étoile de Kleene \texttt{*}, par exemple) des caractères eux-mêmes -(comment rechercher les chaînes contenant le caractère \texttt{*} si -\texttt{*} est utilisé par l'étoile de Kleene ?). La solution est -d'introduire un mécanisme d'\emph{échappement} : ainsi, -\texttt{x\char"5C*} recherche un \texttt{x} suivi d'un -astérisque \texttt{*}, tandis que \texttt{x*} recherche un nombre -quelconque de répétitions de la lettre \texttt{x}. +(comment rechercher les chaînes contenant le caractère « \texttt{*} » +si \texttt{*} est utilisé par l'étoile de Kleene ?). La solution est +d'introduire un mécanisme d'\emph{échappement}, normalement par le +caractère \emph{backslash} : ainsi, « \texttt{x\char"5C*} » recherche +un \texttt{x} suivi d'un astérisque \texttt{*}, tandis que +« \texttt{x*} » recherche un nombre quelconque de répétitions de la +lettre \texttt{x}. \thingy Il existe malheureusement de nombreuses différences, parfois très subtiles, entre moteurs, ne serait-ce que dans les notations : un -moteur pourra par exemple noter \texttt{(?)} ce qu'un autre note -\texttt{\char"5C(\char"5C?\char"5C)} et vice versa. La seule solution -est de consulter attentivement la documentation de chaque moteur -d'expressions régulières pour connaître la syntaxe utilisée. +moteur pourra par exemple noter « \texttt{(?)} » ce qu'un autre note +« \texttt{\char"5C(\char"5C?\char"5C)} » et vice versa. La seule +solution est de consulter attentivement la documentation de chaque +moteur d'expressions régulières pour connaître la syntaxe utilisée. Signalons tout de même qu'il existe deux principales familles de syntaxes d'expressions régulières en informatique : les expressions @@ -1106,8 +1115,9 @@ 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}. +va voir en \ref{kleenes-theorem} 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 @@ -1146,15 +1156,16 @@ définir sont informellement décrits ainsi : \end{itemize} \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). +graphes orientés (admettant des boucles et arêtes multiples ; +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 @@ -1235,10 +1246,10 @@ va lui présenter un mot $w \in \Sigma^*$, lettre par lettre, de la gauche vers la droite : i.e., si $w = x_1\cdots x_n$ on va faire consommer à l'automate les lettres $x_1,x_2,\ldots,x_n$ dans cet ordre. Le fait de consommer une lettre $x$ fait passer l'automate de -l'état $q$ à l'état $\delta(q,x)$ (autrement dit, l'automate passe +l'état $q$ à l'état $\delta(q,x)$ ; autrement dit, l'automate passe successivement dans les états $q_0$ puis $q_1 := \delta(q_0,x_1)$ puis $q_2 := \delta(q_1,x_2)$, et ainsi de suite jusqu'à $q_n := -\delta(q_{n-1},x_n)$) ; on dit que l'automate effectue les transitions +\delta(q_{n-1},x_n)$ : on dit que l'automate effectue les transitions $q_0\to q_1$ (en consommant $x_1$) puis $q_1\to q_2$ (en consommant $x_2$) et ainsi de suite. Si $q_n$ est l'état dans lequel se trouve l'automate une fois qu'il a consommé le mot $w$, on dira que @@ -1308,13 +1319,13 @@ On dit que deux DFA $A,A'$ sont \defin[équivalents (automates)]{équivalents} lorsqu'ils reconnaissent le même langage, i.e., $L_A = L_{A'}$. -\thingy\label{discussion-example2} L'automate fini ci-dessous sur -$\Sigma := \{a,b,c\}$ a trois états, $Q = \{0,1,2\}$. On peut en -faire la description informelle suivante : l'automate commence dans -l'état $0$, où il reste jusqu'à rencontrer un $a$ qui le fait passer -dans l'état $1$, où il reste ensuite jusqu'à rencontrer un $b$ qui le -fait passer dans l'état $2$, où il reste définitivement et qui -constitue le seul état acceptant. +\thingy\label{discussion-example2} Donnons un exemple : l'automate +fini ci-dessous sur $\Sigma := \{a,b,c\}$ a trois états, $Q = +\{0,1,2\}$. On peut en faire la description informelle suivante : +l'automate commence dans l'état $0$, où il reste jusqu'à rencontrer +un $a$ qui le fait passer dans l'état $1$, où il reste ensuite jusqu'à +rencontrer un $b$ qui le fait passer dans l'état $2$, où il reste +définitivement et qui constitue le seul état acceptant. \begin{center} %%% begin example2 %%% @@ -1352,7 +1363,7 @@ l'automate arrive (en partant de l'état initial et en consommant un certain mot). Dans le cas contraire, l'état est dit \textbf{inaccessible}. Il est évident qu'ajouter ou supprimer (ou modifier) les états inaccessibles dans un DFA ne change rien au -langage reconnu au sens où on obtient des langages équivalents. +langage reconnu (on obtient des langages équivalents). Par exemple, dans le DFA qui suit, l'état $2$ est inaccessible (l'automate est donc équivalent à celui représenté @@ -1398,9 +1409,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.}, 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$, @@ -1418,8 +1429,8 @@ 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 -transition $\delta$ se trouve être définie partout.) +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 différence près que pour chaque $q\in Q$ et chaque $x\in \Sigma$, il y @@ -1427,7 +1438,7 @@ 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 +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 @@ -1663,15 +1674,16 @@ donnée 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 $\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 NFA particulier en définissant l'ensemble des états initiaux du NFA 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 +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'$). +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 @@ -1702,7 +1714,10 @@ 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. +plusieurs caractères. On a $(q,w,q') \in \delta^*$ lorsqu'il existe +un chemin orienté conduisant de $q$ à $q'$ et tel que le mot $w$ soit +obtenu en lisant dans l'ordre les étiquettes des différentes arêtes de +ce chemin. Formellement : si $A = (Q,I,F,\delta)$ est un NFA sur l'alphabet $\Sigma$, on définit une relation $\delta^* \subseteq Q @@ -1758,6 +1773,12 @@ l'état $0$ et qu'on lui fait consommer un $a$, si ce $a$ sera l'avant-dernière lettre, et, dans ce cas, passe dans l'état $1$ pour pouvoir accepter le mot. +\medbreak + +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 : + \begin{prop}\label{determinization-of-nfa} Soit $A = (Q,I,F,\delta)$ un NFA sur un alphabet $\Sigma$. Alors il existe un DFA $A' = (Q',q'_0,F',\delta')$ (sur le même @@ -1771,12 +1792,14 @@ On définit $Q' = \mathscr{P}(Q) = \{\mathbf{q} \subseteq Q\}$ l'\emph{ensemble des parties} de $Q$ : c'est ce qui servira d'ensemble d'états du DFA $A'$ qu'on construit (i.e., un état de $A'$ est un ensemble d'états de $A$ — intuitivement, c'est l'ensemble des états -dans lesquels on se trouve simultanément). On pose $q'_0 = I$ et $F' -= \{\mathbf{q}\subseteq Q :\penalty-100 \mathbf{q}\cap F -\neq\varnothing\}$ l'ensemble des états de $A'$ qui, vus comme des -ensembles d'états de $A$, contiennent \emph{au moins un} état final. -Enfin, pour $\mathbf{q}\subseteq Q$ et $x \in \Sigma$, on définit -$\delta'(\mathbf{q},x) = \{q_1\in Q : \exists q_0\in\mathbf{q} +dans lesquels on se trouve simultanément). On pose $q'_0 = I$ (l'état +initial de $A'$ sera l'ensemble de tous les états initiaux de $A$, vu +comme un élément de $Q'$) ; et on pose $F' = \{\mathbf{q}\subseteq Q +:\penalty-100 \mathbf{q}\cap F \neq\varnothing\}$ : les états finaux +de $A'$ sont les états $\mathbf{q}$ qui, vus comme des ensembles +d'états de $A$, contiennent \emph{au moins un} état final. Enfin, +pour $\mathbf{q}\subseteq Q$ et $x \in \Sigma$, on définit +$\delta'(\mathbf{q},x) = \{q_1\in Q : \exists q_0\in\mathbf{q}\; ((q_0,x,q_1) \in \delta)\}$ comme l'ensemble de tous les états $q_1$ de $A$ auxquels on peut accéder depuis un état $q_0$ dans $\mathbf{q}$ par une transition $(q_0,x,q_1)$ (étiquetée par $x$) de $A$. @@ -1794,7 +1817,7 @@ de $F$, ce qui par définition de $F'$ signifie exactement $\delta^{\prime*}(I,w) \in F'$. On a bien prouvé $L_{A'} = L_A$. Enfin, $\#Q' = \#\mathscr{P}(Q) = 2^{\#Q}$ (car une partie de $Q$ peut -se voir comme sa fonction indicatrice, qui est une fonction $Q \to +se voir à travers sa fonction indicatrice, qui est une fonction $Q \to \{0,1\}$). \end{proof} @@ -1815,9 +1838,9 @@ procéduire suivante : $\mathbf{q}$, et, pour chaque lettre $x\in\Sigma$, \begin{itemize} \item calculer l'ensemble $\mathbf{q}' = \{q_1\in Q : \exists - q_0\in\mathbf{q} ((q_0,x,q_1) \in \delta)\}$ (en listant tous les - triplets $(q_0,x,q_1)$ dont le premier élément est dans $\mathbf{q}$ - et le second élément est $x$), + q_0\in\mathbf{q}\; ((q_0,x,q_1) \in \delta)\}$ (en listant tous les + triplets $(q_0,x,q_1) \in\delta$ dont le premier élément est + dans $\mathbf{q}$ et le second élément est $x$), \item si $\mathbf{q}'$ n'existe pas déjà comme état de $A'$, l'y ajouter, et dans ce cas, l'ajouter à la file/pile, et de plus, si $\mathbf{q}'$ contient un état final de $A$, marquer cet état comme @@ -1886,15 +1909,15 @@ procédant ainsi, on construit l'automate à $4$ états qui suit : On remarquera qu'on a construit moins que les $2^3 = 8$ états qu'on pouvait craindre. -Il est par ailleurs instructif de regarder comment fonctionne -l'automate $A'$ ci-dessus pour déterminer si l'avant-dernière lettre -d'un mot est un $a$ : intuitivement, l'état $\{0\}$ mémorise -l'information « la dernière lettre n'était pas un $a$, et la - précédente ne l'était pas », l'état $\{0,1\}$ mémorise « la dernière - lettre était un $a$, mais la précédente ne l'état pas », l'état -$\{0,1,2\}$ mémorise « les deux dernières lettres étaient des $a$ », -et l'état $\{0,2\}$ mémorise « la dernière lettre était un $b$, mais - la précédente était un $a$ ». +{\footnotesize Il est par ailleurs instructif de regarder comment + fonctionne l'automate $A'$ ci-dessus pour déterminer si + l'avant-dernière lettre d'un mot est un $a$ : essentiellement, il + retient deux bits d'information, à savoir « est-ce que la dernière + lettre consommée était un $a$ ? » et « est-ce que l'avant-dernière + lettre consommée était un $a$ ? » ; chacune des quatre combinaisons + de ces deux bits correspond à un état de $A'$ : non/non est l'état + $\{0\}$, oui/non est l'état $\{0,1\}$, non/oui est l'état $\{0,2\}$, + et oui/oui est l'état $\{0,1,2\}$.\par} \thingy On vient donc de voir que les NFA sont équivalents aux DFA en ce sens qu'ils permettent de définir les mêmes langages. Il est @@ -1953,7 +1976,7 @@ non-déterministe : ces transitions spontanées ne sont qu'une De façon plus précise, un εNFA accepte un mot $w$ lorsqu'\emph{il existe} un chemin orienté conduisant d'un état initial $q_0$ à un état final $q_n$ et tel que $w$ coïncide avec le mot obtenu en lisant -dans l'ordre les étiquettes $x_i$ des différentes arêtes $q_{i-1} \to +dans l'ordre les étiquettes $t_i$ des différentes arêtes $q_{i-1} \to q_i$ de ce chemin, quitte à ignorer les $\varepsilon$. Autrement dit, $w$ est accepté lorsqu'\emph{il existe} $q_0,\ldots,q_n @@ -1964,7 +1987,12 @@ cette écriture, $t_1,\ldots,t_n$ ne sont pas forcément les lettres de $w$, certains des $t_i$ peuvent être le symbole $\varepsilon$, les lettres de $w$ sont obtenues en ignorant ces symboles). -\thingy Voici une formalisation possible : si $A = (Q,I,F,\delta)$ est +\thingy On veut de nouveau définir une relation $\delta^*$ telle que +$(q,w,q') \in \delta^*$ lorsqu'il existe un chemin orienté conduisant +de $q$ à $q'$ et tel que le mot $w$ soit obtenu en lisant dans l'ordre +les étiquettes des différentes arêtes de ce chemin. + +Voici une formalisation possible : 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^*$ lorsqu'il existe $q_0,\ldots,q_n \in Q$ et $t_1,\ldots,t_n \in @@ -2046,8 +2074,8 @@ C(q)$, et on crée une transition $q\to q'$ étiquetée par $x$ dans $A^\S$ lorsqu'il existe une transition $q^\sharp\to q'$ étiquetée par ce $x$ dans $A$. De même, on définit $F^\S \subseteq Q$ comme l'ensemble des $q\in Q$ tels que $C(q) \cap F \neq \varnothing$, -c'est-à-dire, qu'on peut atteindre un état final par une succession de -ε-transitions. +c'est-à-dire, depuis lesquels peut atteindre un état final par une +succession de ε-transitions. Si on a un chemin $q_0 \to q_1 \to \cdots \to q_n$ dans $A$ menant d'un état initial $q_0 \in I$ à un état final $q_n \in F$ et @@ -2055,11 +2083,11 @@ d'un état initial $q_0 \in I$ à un état final $q_n \in F$ et (c'est-à-dire $(q_{i-1},t_i,q_i) \in \delta$), appelons $j_1<\ldots<j_m$ les indices tels que $t_j \in\Sigma$, autrement dit, tels que la transition $q_{j-1} \to q_j$ ne soit pas spontanée, et -posons $j_0 = 0$. Alors on passe de $q_{j_{i-1}}$ à $q_{j_i}$ par une -succession de ε-transitions (de $q_{j_{i-1}}$ à $q_{(j_i)-1}$) suivie +posons $j_0 = 0$. Alors on passe de $q_{j_{(i-1)}}$ à $q_{j_i}$ par une +succession de ε-transitions (de $q_{j_{(i-1)}}$ à $q_{(j_i)-1}$) suivie par une unique transition non spontanée : on a $q_{(j_i)-1} \in -C(q_{j_{i-1}})$ et $(q_{(j_i)-1},t_{j_i},q_{j_i}) \in \delta$, -autrement dit $(q_{j_{i-1}},t_{j_i},q_{j_i}) \in \delta^\S$ ; et comme +C(q_{j_{(i-1)}})$ et $(q_{(j_i)-1},t_{j_i},q_{j_i}) \in \delta$, +autrement dit $(q_{j_{(i-1)}},t_{j_i},q_{j_i}) \in \delta^\S$ ; et comme le mot $w = t_1\cdots t_n$ s'écrit aussi $t_{j_1}\cdots t_{j_m}$, on a un chemin reliant $q_{j_0} = q_0 \in I$ à $q_{j_m} \in F^\S$ (puisque $q_n \in C(q_{j_m}) \cap F$). Le mot $w$ supposé accepté par $A$ est @@ -2126,16 +2154,16 @@ définit $(q,x,q') \in \delta^\S$ lorsqu'il existe $q^\sharp \in C(q)$ tel que $(q^\sharp,x,q') \in \delta$, et $I^\S=I$ et $F^\S$ comme l'ensemble des états $q$ tels que $C(q) \cap F \neq \varnothing$ ; la construction « duale » $A \mapsto A^\P$ consiste à poser $(q,x,q') \in -\delta^\P$ lorsqu'il existe $q^{\flat\prime} \in C(q)$ tel que -$(q,x,q^{\flat\prime}) \in \delta$, et $F^\P=F$ et $I^\P$ comme la -réunion des $C(q)$ pour tout $q\in I$. +\delta^\P$ lorsqu'il existe $q^{\flat\prime}$ tel que +$(q,x,q^{\flat\prime}) \in \delta$ et $q' \in C(q^{\flat\prime})$, et +$F^\P=F$ et $I^\P$ comme la réunion des $C(q)$ pour tout $q\in I$. Ces deux manières d'éliminer les ε-transitions donnent des NFA -équivalents. En fait, on peut passer de l'une à l'autre en utilisant -la définition de l'automate transposé $A^{\mathsf{R}}$ présentée -en \ref{nfa-mirror} plus bas (et qui consiste simplement à inverser le -sens de toutes les flèches de l'automate) : si on inverse les flèches, -qu'on élimine les ε-transitions à la manière décrite +équivalents. En fait, on peut définir l'une en termes de l'autre en +utilisant la définition de l'automate transposé $A^{\mathsf{R}}$ +présentée en \ref{nfa-mirror} plus bas (et qui consiste simplement à +inverser le sens de toutes les flèches de l'automate) : si on inverse +les flèches, qu'on élimine les ε-transitions à la manière décrite en \ref{removal-of-epsilon-transitions}, et qu'on inverse de nouveau les flèches, on obtient l'élimination « duale », autrement dit, $A^\P = ((A^{\mathsf{R}})^\S)^{\mathsf{R}}$. @@ -2197,7 +2225,7 @@ $Q' = Q$, l'état initial $q'_0 = q_0$, la fonction de transition $\delta' = \delta$ et pour seul changement l'ensemble d'états finaux $F' = Q \setminus F$ complémentaire de $F$. -Si $w \in \Sigma^*$, on a $w \in L_{A'}$ si et seulement si +Pour $w \in \Sigma^*$, on a $w \in L_{A'}$ si et seulement si $\delta^{\prime*}(q_0,w) \in F'$, c'est-à-dire $\delta^*(q_0,w) \in F'$ (puisque $\delta' = \delta$), c'est-à-dire $\delta^*(q_0,w) \not\in F$ (par définition du complémentaire), c'est-à-dire $w \not\in @@ -2252,6 +2280,10 @@ sous-ensemble de $Q'' = Q_1\times Q_2$ formé des couples dont \thingy La construction $A'$ ci-dessus est parfois appelée automate \index{produit (d'automates)}\emph{produit} des DFA $A_1$ et $A_2$. +Intuitivement, il faut comprendre que faire fonctionner l'automate +$A'$ revient à faire fonctionner les automates $A_1$ et $A_2$ +simultanément (en parallèle), en leur donnant à consommer les mêmes +symboles. La construction de l'automate produit pour fabriquer le langage intersection utilise la caractérisation des langages reconnaissables @@ -2283,7 +2315,7 @@ que $L = L_A$. Considérons l'automate $A^{\mathsf{R}}$ de même type défini par l'ensemble d'états $Q^{\mathsf{R}} = Q$ et inversant toutes les flèches de $A$, c'est-à-dire $I^{\mathsf{R}} = F$ et $F^{\mathsf{R}} = I$ et $(q,t,q') \in \delta^{\mathsf{R}}$ si et -seulement si $(q^{\mathsf{R}},t,q) \in \delta$. Un chemin existe dans +seulement si $(q',t,q) \in \delta$. Un chemin existe dans $A^{\mathsf{R}}$ si et seulement si le même chemin inversé existe dans $A$, ce qui montre qu'un mot appartient à $L_{A^{\mathsf{R}}}$ si et seulement si son miroir appartient à $L_A$. On a donc bien @@ -2310,8 +2342,9 @@ cf. \ref{stable-under-rational-operations} ; on l'a déjà vu sur les DFA en \ref{dfa-union-and-intersection} pour la réunion, mais on va en donner une nouvelle démonstration, cette fois basée sur les NFA, qui a un contenu algorithmique utile dans des circonstances différentes). -Cela permettra de conclure que les langages rationnels sont -reconnaissables (la réciproque faisant l'objet de la +Cela permettra de conclure +en \ref{rational-languages-are-recognizable} que les langages +rationnels sont reconnaissables (la réciproque faisant l'objet de la section \ref{subsection-rnfa-and-kleenes-algorithm}). Pour établir ces stabilités, on va travailler sur les NFA et utiliser |