diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 699 |
1 files changed, 389 insertions, 310 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 8847dd2..24e9fc3 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -15,6 +15,10 @@ \usepackage{wasysym} \usepackage{url} % +\usepackage{makeidx} +%% Self-note: compile index with: +%% xindy -M texindy -C utf8 -L french notes-inf105.idx +% \usepackage{graphics} \usepackage[usenames,dvipsnames]{xcolor} \usepackage{tikz} @@ -52,6 +56,8 @@ \newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% \hbox to0pt{\hskip-\hangindent\dbend\hfill}} % +\newcommand{\defin}[2][]{\def\latexsucks{#1}\ifx\latexsucks\empty\index{#2}\else\index{\latexsucks}\fi\textbf{#2}} +% % % NOTE: compile dot files with % dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot > file.tex @@ -61,6 +67,7 @@ % % % +\makeindex \begin{document} \title{THL (Théorie des langages)\\Notes de cours \textcolor{red}{provisoires}} \author{David A. Madore} @@ -114,16 +121,17 @@ par définir ces différents termes avant de décrire plus précisément l'objet de l'étude. \thingy Le point de départ est donc ce que les mathématiciens -appelleront un \textbf{alphabet}, et qui correspond pour les +appelleront un \defin{alphabet}, et qui correspond pour les informaticiens à un \textbf{jeu de caractères}. Il s'agit d'un ensemble \emph{fini}, sans structure particulière, dont les éléments -s'appellent \textbf{lettres}, ou encore \textbf{caractères} dans une -terminologie plus informatique, ou parfois aussi \textbf{symboles}. +s'appellent \defin[lettre]{lettres}, ou encore +\index{caractère|see{lettre}}\textbf{caractères} dans une terminologie +plus informatique, ou parfois aussi \defin[symbole]{symboles}. Les exemples mathématiques seront souvent donnés sur un alphabet tel que l'alphabet à deux lettres $\{a,b\}$ ou à trois lettres $\{a,b,c\}$. On pourra aussi considérer l'alphabet $\{0,1\}$ appelé -\textbf{binaire} (puisque l'alphabet n'a pas de structure +\defin{binaire} (puisque l'alphabet n'a pas de structure particulière, cela ne fait guère de différence par rapport à n'importe quel autre alphabet à deux lettres). Dans un contexte informatique, des jeux de caractères (=alphabets) souvent importants sont ASCII, @@ -137,9 +145,9 @@ théorie que l'alphabet soit \emph{fini}. L'alphabet sera généralement fixé une fois pour toutes dans la discussion, et désigné par la lettre $\Sigma$ (sigma majuscule). -\thingy Un \textbf{mot} sur l'alphabet $\Sigma$ est une suite finie de +\thingy Un \defin{mot} sur l'alphabet $\Sigma$ est une suite finie de lettres (éléments de $\Sigma$) ; dans la terminologie informatique, on -parle plutôt de \textbf{chaîne de caractères}, qui est une suite finie +parle plutôt de \index{caractères (chaîne de)|see{chaîne de caractères}}\defin{chaîne de caractères}, qui est une suite finie (=liste) de caractères. Le mot est désigné en écrivant les lettres les unes à la suite des autres : autrement dit, si $x_1,\ldots,x_n \in \Sigma$ sont des lettres, le mot formé par la suite finie @@ -165,13 +173,14 @@ binaires (=suites finies de $0$ et de $1$). Ainsi, écrire « $w \in possible de désigner des mots par des variables mathématiques telles que $u,v,w$, tandis que $x,y,z$ désigneront plutôt des lettres quelconques dans un alphabet (quant à $a,b,c$, ils serviront de - lettres dans les exemples). Ce n'est malheureusement pas possible - d'être systématique (il arrivera que $x$ désigne un mot) : on - cherchera donc à toujours rappeler le type de toute variable en - écrivant, par exemple, $t \in\Sigma$ ou $t \in\Sigma^*$.\par} + lettres dans les exemples). Il n'est malheureusement pas possible + d'être complètement systématique (il arrivera que $x$ désigne un + mot) : on cherchera donc à toujours rappeler le type de toute + variable en écrivant, par exemple, $t \in\Sigma$ ou $t + \in\Sigma^*$.\par} \thingy\label{length-of-word} Le nombre $n$ de lettres dans un mot $w -\in \Sigma^*$ est appelé la \textbf{longueur} du mot, et généralement +\in \Sigma^*$ est appelé la \defin{longueur} du mot, et généralement notée $|w|$ ou bien $\ell(w)$ : autrement dit, si $x_1,\ldots,x_n \in \Sigma$, alors la longueur $|x_1\cdots x_n|$ du mot $x_1\cdots x_n$, vaut $n$. Ceci coïncide bien avec la notion usuelle de longueur d'une @@ -181,7 +190,7 @@ l'alphabet $\Sigma=\{a,b,c,d\}$, la longueur du mot $abbcab$ vaut $6$ \thingy Quel que soit l'alphabet, il existe un unique mot de longueur $0$, c'est-à-dire un unique mot n'ayant aucune lettre, appelé -le \textbf{mot vide} (ou la \textbf{chaîne [de caractères] vide}). +le \defin{mot vide} (ou la \textbf{chaîne [de caractères] vide}). Étant donné qu'il n'est pas commode de désigner un objet par une absence de symbole, on introduit un symbole spécial, généralement $\varepsilon$, pour désigner ce mot vide : on a donc @@ -233,8 +242,8 @@ mots, de longueurs respectives $m$ et $n$, sur un même alphabet $\Sigma$, alors on définit un mot $uv := x_1\cdots x_m y_1\cdots y_n$ de longueur $m+n$, dont les lettres sont obtenues en mettant bout à bout celles de $u$ puis celles de $v$ (dans cet ordre), -et on l'appelle \textbf{concaténation} (ou, si cela ne prête pas à -confusion, simplement \textbf{produit}) des mots $u$ et $v$. (Dans un +et on l'appelle \defin{concaténation} (ou, si cela ne prête pas à +confusion, simplement \index{produit (de mots)|see{concaténation}}\textbf{produit}) des mots $u$ et $v$. (Dans un contexte informatique, on parle de concaténation de chaînes de caractères.) @@ -250,7 +259,7 @@ suivants : \end{itemize} On peut traduire de façon savante ces deux propriétés en une phrase : -l'ensemble $\Sigma^*$ est un \textbf{monoïde}, d'élément +l'ensemble $\Sigma^*$ est un \defin{monoïde}, d'élément neutre $\varepsilon$, pour la concaténation (cela signifie exactement ce qui vient d'être dit). @@ -303,8 +312,8 @@ que ces exposants \emph{ne font pas partie} de l'alphabet.) lorsque le mot $w$ est la concaténation des deux mots $u$ et $v$, on dira également : \begin{itemize} -\item que $u$ est un \textbf{préfixe} de $w$, ou -\item que $v$ est un \textbf{suffixe} de $w$. +\item que $u$ est un \defin{préfixe} de $w$, ou +\item que $v$ est un \defin{suffixe} de $w$. \end{itemize} De façon équivalente, si $w = x_1\cdots x_n$ (où $x_1,\ldots,x_n \in @@ -317,8 +326,9 @@ lettres de $w$, dans le même ordre) est le \textbf{suffixe de longueur $n-k$} de $w$. Il est clair qu'il s'agit bien là de l'unique façon d'écrire $w = uv$ avec $|u|=k$ et $|v|=n-k$, ce qui fait le lien avec la définition donnée au paragraphe précédent ; -parfois on dira que $v$ est le suffixe \textbf{correspondant} à $u$ ou -que $u$ est le préfixe correspondant à $v$ (dans le mot $w$). +parfois on dira que $v$ est le suffixe \defin[correspondant (préfixe + ou suffixe)]{correspondant} à $u$ ou que $u$ est le préfixe +correspondant à $v$ (dans le mot $w$). Le mot vide est préfixe et suffixe de n'importe quel mot. Le mot $w$ lui-même est aussi un préfixe et un suffixe de lui-même. Entre les @@ -340,7 +350,7 @@ préfixe $abb$ est $bcab$ puisque $abbcab = (abb)(bcab)$. celle de suffixe, on a la notion de facteur : si $u_0,v,u_1 \in \Sigma^*$ sont trois mots quelconques sur un même alphabet $\Sigma$, et si $w = u_0 v u_1$ est leur concaténation, on dira que $v$ est un -\textbf{facteur} de $w$. Alors qu'un préfixe ou suffixe du mot $w$ +\defin{facteur} de $w$. Alors qu'un préfixe ou suffixe du mot $w$ est déterminé simplement par sa longueur, un facteur est déterminé par sa longueur et l'emplacement à partir duquel il commence. @@ -355,7 +365,7 @@ cependant pas confondre ce concept avec celui de sous-mot défini ci-dessous. \thingy\label{definition-subword} Si $w = x_1\cdots x_n$ est un mot de -longueur $n$, on appelle \textbf{sous-mot} de $w$ un mot de la forme +longueur $n$, on appelle \defin{sous-mot} de $w$ un mot de la forme $x_{i_1} \cdots x_{i_k}$ où $1\leq i_1 < \cdots < i_k \leq n$. En plus clair, cela signifie que $v$ est obtenu en ne gardant que certaines lettres du mot $w$, dans le même ordre, mais en en effaçant @@ -389,24 +399,27 @@ mots.\par} \thingy\label{definition-mirror-word} Si $w = x_1\cdots x_n$, où $x_1,\ldots,x_n \in \Sigma$, est un mot de longueur $n$ sur un -alphabet $\Sigma$, alors on définit son mot \textbf{miroir} ou -\textbf{transposé}, parfois noté $w^{\textsf{R}}$ ou $w^{\textsf{T}}$ -(parfois les exposants sont écrits à gauche), comme le mot $x_n\cdots -x_1$ dont les lettres sont les mêmes que celles de $w$ mais dans -l'ordre inverse. À titre d'exemple, $(ababb)^{\textsf{R}} = bbaba$. -On remarquera que $(w_1 w_2)^{\textsf{R}} = w_2^{\textsf{R}} -w_1^{\textsf{R}}$ si $w_1,w_2$ sont deux mots quelconques. - -Un mot $w$ est dit \textbf{palindrome} lorsque $w = w^{\textsf{R}}$. +alphabet $\Sigma$, alors on définit son mot \defin{miroir} ou +\index{transposé (mot)|see{miroir}}\textbf{transposé}, parfois noté +$w^{\textsf{R}}$ ou $w^{\textsf{T}}$ (parfois les exposants sont +écrits à gauche), comme le mot $x_n\cdots x_1$ dont les lettres sont +les mêmes que celles de $w$ mais dans l'ordre inverse. À titre +d'exemple, $(ababb)^{\textsf{R}} = bbaba$. On remarquera que $(w_1 +w_2)^{\textsf{R}} = w_2^{\textsf{R}} w_1^{\textsf{R}}$ si $w_1,w_2$ +sont deux mots quelconques. + +Un mot $w$ est dit \defin{palindrome} lorsque $w = w^{\textsf{R}}$. +Par exemple, $abba$ est un palindrome sur $\{a,b,c,d\}$ (ou bien le +mot « ressasser » sur l'alphabet du français). {\footnotesize\thingy\label{number-of-occurrences-of-letter} La notation suivante est souvent utile : si $w$ est un mot sur un alphabet $\Sigma$ et si $z$ est une lettre (= élément de $\Sigma$), - on note $|w|_z$ le nombre total d'occurrences de la lettre $z$ - dans $w$. À titre d'exemple, sur l'alphabet $\Sigma=\{a,b,c,d\}$, - le nombre d'occurrences des différentes lettres dans le mot $abbcab$ - sont : $|abbcab|_a=2$, $|abbcab|_b=3$, $|abbcab|_c=1$ et - $|abbcab|_d=0$. + on note $|w|_z$ le \index{occurrences (nombre d')}nombre total + d'occurrences de la lettre $z$ dans $w$. À titre d'exemple, sur + l'alphabet $\Sigma=\{a,b,c,d\}$, le nombre d'occurrences des + différentes lettres dans le mot $abbcab$ sont : $|abbcab|_a=2$, + $|abbcab|_b=3$, $|abbcab|_c=1$ et $|abbcab|_d=0$. Formellement, on peut définir $|w|_z$ de la façon suivante : si $w = x_1 \cdots x_n$ où $x_1,\ldots,x_n \in \Sigma$, alors $|w|_z$ est le @@ -418,7 +431,7 @@ l'alphabet).\par} \subsection{Langages et opérations sur les langages} -\thingy Un \textbf{langage} $L$ sur l'alphabet $\Sigma$ est simplement +\thingy Un \defin{langage} $L$ sur l'alphabet $\Sigma$ est simplement un ensemble de mots sur $\Sigma$. Autrement dit, il s'agit d'un sous-ensemble (=une partie) de l'ensemble $\Sigma^*$ (de tous les mots sur $\Sigma$) : en symboles, $L \subseteq \Sigma^*$. @@ -497,9 +510,10 @@ une chaîne de caractères et renvoyant un booléen. \thingy Si $L_1$ et $L_2$ sont deux langages sur un même alphabet $\Sigma$ (autrement dit, $L_1,L_2 \subseteq \Sigma^*$), on -peut former les langages \textbf{union} $L_1\cup L_2$ et -\textbf{intersection} $L_1\cap L_2$ qui sont simplement les opérations -ensemblistes usuelles (entre parties de $\Sigma^*$). +peut former les langages \defin[union (de langages)]{union} $L_1\cup +L_2$ et \defin[intersection (de langages)]{intersection} $L_1\cap L_2$ +qui sont simplement les opérations ensemblistes usuelles (entre +parties de $\Sigma^*$). Les opérations correspondantes sur les propriétés de mots sont respectivement le « ou logique » (=disjonction) et le « et logique » @@ -513,9 +527,10 @@ finissant par $b$. \thingy Si $L$ est un langage sur l'alphabet $\Sigma$, autrement dit $L \subseteq \Sigma^*$, on peut former le langage $\Sigma^*\setminus L$, parfois noté simplement $\overline L$ si ce n'est pas ambigu, dit -\textbf{complémentaire} de $L$, et qui est simplement l'ensemble des -mots sur $\Sigma$ \emph{n'appartenant pas} à $L$. L'opération -correspondante sur les propriétés de mots est la négation logique. +\defin[complémentaire (langage)]{complémentaire} de $L$, et qui est +simplement l'ensemble des mots sur $\Sigma$ \emph{n'appartenant pas} +à $L$. L'opération correspondante sur les propriétés de mots est la +négation logique. À titre d'exemple, sur $\Sigma=\{a,b\}$, si $L$ est le langage des mots commençant par $a$, alors $\overline{L}$ est le langage des mots @@ -526,9 +541,10 @@ commence par $b$). \thingy Si $L_1$ et $L_2$ sont deux langages sur un même alphabet $\Sigma$ (autrement dit, $L_1,L_2 \subseteq \Sigma^*$), on -peut former le langage \textbf{concaténation} $L_1 L_2$ : il est -défini comme l'ensemble des mots $w$ qui peuvent s'écrire comme -concaténation d'un mot $w_1$ de $L_1$ et d'un mot $w_2$ de $L_2$, soit +peut former le langage \defin[concaténation (de + langages)]{concaténation} $L_1 L_2$ : il est défini comme l'ensemble +des mots $w$ qui peuvent s'écrire comme concaténation d'un mot $w_1$ +de $L_1$ et d'un mot $w_2$ de $L_2$, soit \[ \begin{aligned} L_1 L_2 &:= \{w_1 w_2 : w_1 \in L_1,\, w_2 \in L_2\}\\ @@ -565,8 +581,9 @@ longueur exactement $r$ sur $\{a,b\}$, ce n'est pas l'ensemble à deux a$ et $b^r = bbb\cdots b$. \thingy\label{kleene-star} Si $L$ est un langage sur -l'alphabet $\Sigma$, on définit enfin l'\textbf{étoile de Kleene} -$L^*$ de $L$ comme le langage constitué des concaténations d'un nombre +l'alphabet $\Sigma$, on définit enfin l'\index{Kleene (étoile + de)|see{étoile de Kleene}}\defin{étoile de Kleene} $L^*$ de $L$ +comme le langage constitué des concaténations d'un nombre \emph{quelconque} de mots appartenant à $L$, c'est-à-dire la réunion de tous les langages $L^r$ mentionnés ci-dessus : \[ @@ -661,14 +678,15 @@ suivantes : \end{itemize} On obtient ainsi une certaine famille de langages (cf. ci-dessous pour -une définition plus précise), qu'on appelle \textbf{langages - rationnels} : les langages rationnels sont exactement ceux qui -peuvent s'obtenir à partir des langages de base énumérés ci-dessus par -application (un nombre fini de fois) des opérations qu'on vient de -dire. Autrement dit, la réunion de deux langages rationnels, la -concaténation de deux langages rationnels, et l'étoile de Kleene d'un -langage rationnel, sont rationnels, et les langages rationnels sont -exactement ceux qu'on obtient ainsi à partir des langages de base. +une définition plus précise), qu'on appelle \defin[rationnel + (langage)]{langages rationnels} : les langages rationnels sont +exactement ceux qui peuvent s'obtenir à partir des langages de base +énumérés ci-dessus par application (un nombre fini de fois) des +opérations qu'on vient de dire. Autrement dit, la réunion de deux +langages rationnels, la concaténation de deux langages rationnels, et +l'étoile de Kleene d'un langage rationnel, sont rationnels, et les +langages rationnels sont exactement ceux qu'on obtient ainsi à partir +des langages de base. À titre d'exemple, sur l'alphabet $\{a,b,c,d\}$, comme le langage $\{c\}$ (constitué du seul mot $c$) est rationnel, son étoile de @@ -704,21 +722,24 @@ est un langage tel que si $w_1,w_2\in L$ alors $w_1 w_2 \in L$). \thingy Pour décrire la manière dont un langage rationnel est fabriqué (à partir des langages de base par les opérations rationnelles), comme il est malcommode d'écrire quelque chose comme $\{d\}(\{c\}^*)$, on -introduit un nouvel objet, les \textbf{expressions rationnelles} -(certains préfèrent le terme d'\textbf{expressions régulières}), qui -sont des expressions servant à désigner un langage rationnel. Par -exemple, plutôt que d'écrire « $\{d\}(\{c\}^*)$ », on parlera du -langage « désigné par l'expression rationnelle $dc{*}$ ». +introduit un nouvel objet, les \index{expression + rationnelle|see{rationnelle (expression)}}\defin[rationnelle + (expression)]{expressions rationnelles} (certains préfèrent le terme +d'\index{régulière (expression)|see{rationnelle}}\textbf{expressions + régulières}), qui sont des expressions servant à désigner un langage +rationnel. Par exemple, plutôt que d'écrire « $\{d\}(\{c\}^*)$ », on +parlera du langage « désigné par l'expression rationnelle $dc{*}$ ». Plus exactement, une expression rationnelle (sur un alphabet $\Sigma$) est un mot sur l'alphabet $\Sigma \cup \{\bot, \underline{\varepsilon}, {(}, {)}, {|}, {*}\}$, où $\bot, \underline{\varepsilon}, {(}, {)}, {|}, {*}$ sont de nouveaux caractères \emph{n'appartenant pas} à l'alphabet $\Sigma$, appelés -\textbf{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 \textbf{langage dénoté} (ou -\textbf{désigné}) $L_r$ par l'expression $r$, de la manière suivante : +\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 : \begin{itemize} \item $\bot$ est une expression rationnelle et son langage dénoté est $L_\bot := \varnothing$, @@ -774,18 +795,19 @@ $\Sigma = \{a,b,c,d\}$ : Un langage rationnel est par construction la même chose qu'un langage pour lequel il existe une expression rationnelle qui le dénote. -\thingy On dira qu'un mot $w$ \textbf{vérifie} une expression -rationnelle $r$ lorsque ce mot appartient au langage qu'elle dénote -(i.e., $w \in L_r$). Par exemple, $dccc$ vérifie l'expression -rationnelle $d(c){*}$. +\thingy On dira qu'un mot $w$ \defin[vérifier (une expression + rationnelle)]{vérifie} une expression rationnelle $r$ lorsque ce mot +appartient au langage qu'elle dénote (i.e., $w \in L_r$). Par +exemple, $dccc$ vérifie l'expression rationnelle $d(c){*}$. \thingy Deux expressions rationnelles $r_1,r_2$ sont dites -\textbf{équivalentes} lorsqu'elles dénotent le même langage. À titre -d'exemple, sur l'alphabet $\{a,b\}$, les deux expressions rationnelles -$(ab){*}a$ et $a(ba){*}$ sont équivalentes (toutes les deux dénotent -le langage $\{a, aba, ababa, \ldots\}$ constitué des mots commençant -et finissant par un $a$ et dans lesquels chaque paire de $a$ est -séparée par un unique $b$). +\defin[équivalentes (expressions rationnelles)]{équivalentes} +lorsqu'elles dénotent le même langage. À titre d'exemple, sur +l'alphabet $\{a,b\}$, les deux expressions rationnelles $(ab){*}a$ et +$a(ba){*}$ sont équivalentes (toutes les deux dénotent le langage +$\{a, aba, ababa, \ldots\}$ constitué des mots commençant et finissant +par un $a$ et dans lesquels chaque paire de $a$ est séparée par un +unique $b$). \thingy La convention de parenthésage introduite ci-dessus est inambiguë mais parfois inutilement lourde : on se permettra parfois de @@ -949,18 +971,21 @@ consommer. \subsection{Automates finis déterministes complets (=DFA)} -\thingy\label{definition-dfa} Un \textbf{automate fini déterministe} -(complet), ou en abrégé \textbf{DFA} (pour \textit{deterministic - finite automaton}), sur un alphabet $\Sigma$ est la donnée +\thingy\label{definition-dfa} Un \defin{automate fini déterministe} +(complet), ou en abrégé \index{DFA|see{automate fini + déterministe}}\textbf{DFA} (pour \textit{deterministic finite + automaton}), sur un alphabet $\Sigma$ est la donnée \begin{itemize} \item d'un ensemble fini $Q$ dont les éléments sont appelés - \textbf{états}, -\item d'un état $q_0 \in Q$ appelé \textbf{état initial}, -\item d'un ensemble $F \subseteq Q$ d'états appelés états - \textbf{finaux}\footnote{Le pluriel de « final » est indifféremment - « finaux » ou « finals ».} ou \textbf{acceptants}, + \defin[état]{états}, +\item d'un état $q_0 \in Q$ appelé \defin[initial (état)]{é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 + (état)|see{final}}\textbf{acceptants}, \item d'une fonction $\delta \colon Q\times\Sigma \to Q$ appelée - \textbf{fonction de transition}. + \defin[transition (fonction de)]{fonction de transition}. \end{itemize} \thingy\label{graphical-representation-of-dfa} Graphiquement, on @@ -1054,7 +1079,8 @@ utile de remarquer que $\delta^*(q,ww') = \delta^*(\delta^*(q,w),w')$). Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$ -\textbf{accepte} ou \textbf{reconnaît} un mot $w$ lorsque +\defin[accepter]{accepte} ou +\index{reconnaître|see{accepter}}\textbf{reconnaît} un mot $w$ lorsque $\delta^*(q_0,w) =: q_n \in F$ ; dans le cas contraire, on dira qu'il \textbf{rejette} le mot $w$. @@ -1065,11 +1091,13 @@ mots acceptés par l'automate $A$ s'appelle \textbf{langage accepté}, ou \textbf{reconnu}, ou \textbf{défini}, par l'automate $A$. Un langage $L \subseteq \Sigma^*$ qui peut s'écrire sous la forme du -langage $L_A$ accepté par un DFA $A$ s'appelle \textbf{reconnaissable} -(sous-entendu : par automate déterministe fini). +langage $L_A$ accepté par un DFA $A$ s'appelle \defin[reconnaissable + (langage)]{reconnaissable} (sous-entendu : par automate déterministe +fini). -On dit que deux DFA $A,A'$ sont \textbf{équivalents} lorsqu'ils -reconnaissent le même langage, i.e., $L_A = L_{A'}$. +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 @@ -1106,16 +1134,16 @@ reconnaissable. (Il est aussi rationnel puisque dénoté par l'expression rationnelle $(b|c){*}a(b|c){*}b(a|b|c){*}$.) \thingy\label{definition-dfa-accessible-state} Un état $q$ d'un DFA -est dit \textbf{accessible} lorsqu'il existe un mot $w \in \Sigma^*$ -tel que $q = \delta(q_0,w)$, autrement dit, graphiquement, lorsqu'il -existe un chemin orienté $q_0,q_1,\ldots,q_n=q$ reliant l'état -initial $q_0$ à l'état $q$ considéré : bref, cela correspond à un état -auquel il est possible que 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. +est dit \defin[accessible (état)]{accessible} lorsqu'il existe un mot +$w \in \Sigma^*$ tel que $q = \delta(q_0,w)$, autrement dit, +graphiquement, lorsqu'il existe un chemin orienté +$q_0,q_1,\ldots,q_n=q$ reliant l'état initial $q_0$ à l'état $q$ +considéré : bref, cela correspond à un état auquel il est possible que +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. Par exemple, dans le DFA qui suit, l'état $2$ est inaccessible (l'automate est donc équivalent à celui représenté @@ -1156,11 +1184,12 @@ 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 \textbf{automate + 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é \textbf{DFAI}, sur un alphabet $\Sigma$ est la donnée +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$, @@ -1253,8 +1282,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 \textbf{puits} -à $A$ : on a $\#Q' \leq \#Q + 1$. +algorithmiquement de $A$ en ajoutant au plus un état \defin[puits + (é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 @@ -1277,12 +1306,12 @@ $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 \textbf{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). +\thingy 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). \thingy À titre d'exemple, le DFA suivant représente la complétion du DFAI représenté en \ref{discussion-example2b} : @@ -1323,21 +1352,23 @@ DFAI représenté en \ref{discussion-example2b} : (cf. \ref{definition-dfa-accessible-state}). On dira en outre d'un état $q$ d'un DFAI qu'il est -\textbf{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é reliant l'état $q$ -considéré à un état final (remarquer que les états 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 transitions qui y conduisent). +\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é +reliant l'état $q$ considéré à un état final (remarquer que les états +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 +transitions qui y conduisent). Un DFAI dont tous les états sont à la fois accessibles et -co-accessibles (on les dit aussi \textbf{utiles}) est parfois appelé -\textbf{émondé}. On peut émonder un DFAI en ne conservant que ses -états utiles : ainsi, tout DFAI est équivalent à un DFAI émondé. +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é. \thingy Il faut prendre garde au fait que certains auteurs définissent les automates finis déterministes comme étant complets, d'autres comme @@ -1346,16 +1377,18 @@ les automates finis déterministes comme étant complets, d'autres comme \subsection{Automates finis non-déterministes (=NFA)} -\thingy Un \textbf{automate fini non-déterministe}, en abrégé -\textbf{NFA}, sur un alphabet $\Sigma$ est la donnée +\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 \begin{itemize} \item d'un ensemble fini $Q$ d'états, \item d'un ensemble $I \subseteq Q$ d'états dits initiaux, \item d'un ensemble $F \subseteq Q$ d'états dits finaux, -\item d'une \emph{relation} 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$). +\item d'une \emph{relation} de \index{transition (relation + 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$). \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$ @@ -1496,10 +1529,10 @@ se voir comme sa fonction indicatrice, qui est une fonction $Q \to \{0,1\}$). \end{proof} -\thingy On dit que le DFA $A'$ est obtenu en \textbf{déterminisant} le -NFA $A$ lorsqu'il est obtenu par la procédure décrite dans la -démonstration de cette proposition en ne gardant que les états -accessibles. +\thingy On dit que le DFA $A'$ est obtenu en \defin[déterminiser (un + NFA)]{déterminisant} le NFA $A$ lorsqu'il est obtenu par la +procédure décrite dans la démonstration de cette proposition en ne +gardant que les états accessibles. Algorithmiquement, la déterminisation de $A$ s'obtient par la procéduire suivante : @@ -1597,9 +1630,11 @@ 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 \textbf{automate fini non-déterministe à transitions +\thingy Un \defin{automate fini non-déterministe à transitions spontanées} ou \textbf{...à $\varepsilon$-transitions}, en abrégé -\textbf{εNFA}, sur un alphabet $\Sigma$ est la donnée +\index{epsilon-NFA@$\varepsilon$NFA|see{automate fini non-déterministe + à transitions spontanées}}\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, @@ -1609,12 +1644,14 @@ et l'état $\{0,2\}$ mémorise « la dernière lettre était un $b$, mais \end{itemize} Autrement dit, on autorise maintenant des transitions étiquetées par le mot vide $\varepsilon$ plutôt que par une lettre $x \in\Sigma$ : -ces transitions sont dites spontanées, ou $\varepsilon$-transitions. +ces transitions sont dites \defin[spontanée (transition)]{spontanées}, +ou +\index{epsilon-transition@$\varepsilon$-transition|see{spontanée}}\textbf{ε-transitions}. -Soulignons qu'on ne définit les $\varepsilon$-transitions \emph{que} -pour les automates non-déterministes : ou, pour dire les choses -autrement, \emph{un automate qui possède des $\varepsilon$-transitions - est par nature même non-déterministe}. +Soulignons qu'on ne définit les ε-transitions \emph{que} pour les +automates non-déterministes : ou, pour dire les choses autrement, +\emph{un automate qui possède des ε-transitions est par nature même + non-déterministe}. La représentation graphique des εNFA est évidente (on utilisera le symbole « $\varepsilon$ » pour étiqueter les transitions spontanées). @@ -1709,14 +1746,15 @@ nombre quelconque de $b$ suivi d'un nombre quelconque de $c$, ou, si on préfère, le langage dénoté par l'expression rationnelle $a{*}b{*}c{*}$. -\thingy Si $q$ est un état d'un εNFA, on appelle \textbf{ε-fermeture} -de $q$ l'ensemble des états $q'$ (y compris $q$ lui-même) accessibles -depuis $q$ par une succession quelconque de ε-transitions, -c'est-à-dire, si on veut, $\{q'\in Q :\penalty0 (q,\varepsilon,q') -\in\delta^*\}$. On notera temporairement $C(q)$ cet ensemble. (Par -exemple, dans l'exemple \ref{discussion-example5} ci-dessus, on a -$C(0) = \{0,1,2\}$ et $C(1) = \{1,2\}$ et $C(2) = \{2\}$. Dans tout -NFA sans ε-transitions, on a $C(q) = \{q\}$ pour tout état $q$.) +\thingy Si $q$ est un état d'un εNFA, on appelle +\defin[epsilon-fermeture@$\varepsilon$-fermeture]{ε-fermeture} de $q$ +l'ensemble des états $q'$ (y compris $q$ lui-même) accessibles depuis +$q$ par une succession quelconque de ε-transitions, c'est-à-dire, si +on veut, $\{q'\in Q :\penalty0 (q,\varepsilon,q') \in\delta^*\}$. On +notera temporairement $C(q)$ cet ensemble. (Par exemple, dans +l'exemple \ref{discussion-example5} ci-dessus, on a $C(0) = \{0,1,2\}$ +et $C(1) = \{1,2\}$ et $C(2) = \{2\}$. Dans tout NFA sans +ε-transitions, on a $C(q) = \{q\}$ pour tout état $q$.) Il est clair qu'on peut calculer algorithmiquement $C(q)$ (par exemple par un algorithme de Dijkstra sur le graphe dont l'ensemble des @@ -1767,16 +1805,16 @@ $q_n \in C(q_{j_m}) \cap F$). Le mot $w$ supposé accepté par $A$ est donc accepté par $A^\S$. La réciproque est analogue. \end{proof} -\thingy On dit que le NFA $A^\S$ est obtenu en \textbf{éliminant les - ε-transitions} dans le εNFA $A$ lorsqu'il est obtenu par la -procédure décrite dans la démonstration de cette proposition, et en -supprimant tous les états non-initiaux de $A^\S$ auxquels -n'aboutissent dans $A$ que des ε-transitions (ces états sont devenus -inaccessibles dans $A^\S$). Algorithmiquement, il s'agit donc, pour -chaque état $q\in Q$ et chaque $q^\sharp$ dans la ε-femerture $C(q)$ -de $q$, de créer une transition $q\to q'$ étiquetée par $x$ -dans $A^\S$ pour chaque transition $q^\sharp\to q'$ étiquetée par $x$ -dans $A$. +\thingy On dit que le NFA $A^\S$ est obtenu en \defin[éliminer (les + transitions spontanées)]{éliminant les ε-transitions} dans le +εNFA $A$ lorsqu'il est obtenu par la procédure décrite dans la +démonstration de cette proposition, et en supprimant tous les états +non-initiaux de $A^\S$ auxquels n'aboutissent dans $A$ que des +ε-transitions (ces états sont devenus inaccessibles dans $A^\S$). +Algorithmiquement, il s'agit donc, pour chaque état $q\in Q$ et chaque +$q^\sharp$ dans la ε-femerture $C(q)$ de $q$, de créer une transition +$q\to q'$ étiquetée par $x$ dans $A^\S$ pour chaque transition +$q^\sharp\to q'$ étiquetée par $x$ dans $A$. \thingy À titre d'exemple, éliminons les ε-transitions du εNFA $A$ présenté en \ref{discussion-example5} : comme $C(0) = \{0,1,2\}$, on @@ -2126,9 +2164,12 @@ si l'automate accepte le mot. \subsection{Automates à transitions étiquetées par des expressions rationnelles (=RNFA)} -\thingy Un \textbf{automate fini (non-déterministe) à transitions - étiquetées par des expressions rationnelles}, en abrégé -\textbf{RNFA}, sur un alphabet $\Sigma$ est la donnée +\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 \begin{itemize} \item d'un ensemble fini $Q$ d'états, \item d'un ensemble $I \subseteq Q$ d'états dits initiaux, @@ -2324,8 +2365,9 @@ l'expression rationnelle $r$. \end{proof} \thingy La procédure qu'on a décrite dans la démonstration de cette -proposition s'appelle l'algorithme d'\textbf{élimination des états} ou -\textbf{algorithme de Kleene}. +proposition s'appelle l'algorithme d'\defin{élimination des états} ou +\index{Kleene (algorithme de)|see{élimination des + états}}\textbf{algorithme de Kleene}. Il va de soi qu'on peut la simplifier un petit peu : s'il n'y a pas de transition de de $q_1$ vers $q$ ou qu'il n'y en a pas de $q$ @@ -2569,7 +2611,7 @@ suffit donc de prendre $i=0$ pour avoir une contradiction. \end{proof} -\subsection{L'automate canonique, et la minimisation} +\subsection{L'automate minimal, et la minimisation} \begin{thm}[Myhill-Nerode]\label{myhill-nerode} Soit $L$ un langage. Pour $w\in \Sigma^*$, notons $w^{-1} L := \{t @@ -2658,10 +2700,11 @@ isomorphisme d'automates (un renommage des états). \thingy Ce théorème affirme donc qu'il existe (à renommage des états près) un unique DFA (complet) ayant un nombre minimal d'états parmi ceux qui reconnaissent le langage rationnel $L$ : on l'appelle -\textbf{automate canonique} ou \textbf{automate minimal} du -langage $L$. La démonstration ci-dessus en donne une construction à -partir d'une relation d'équivalence, mais cette démonstration n'est -pas algorithmique : on va voir comment on peut le construire de fącon +\defin[minimal (automate)]{automate minimal} ou \index{canonique + (automate)|see{minimal}}\textbf{automate canonique} du langage $L$. La +démonstration ci-dessus en donne une construction à partir d'une +relation d'équivalence, mais cette démonstration n'est pas +algorithmique : on va voir comment on peut le construire de fącon algorithmique à partir d'un DFA quelconque qui reconnaît $L$. \begin{prop}\label{dfa-minimization} @@ -2742,9 +2785,10 @@ chaque classe d'équivalence pour $\equiv$. \end{proof} \thingy L'algorithme décrit par la proposition \ref{dfa-minimization} -porte le nom d'algorithme \textbf{de Moore} ou \textbf{de - minimisation} ou \textbf{de réduction}. Voici comment on peut le -mettre en œuvre de façon plus concrète : +porte le nom d'algorithme \index{Moore (algorithme + de)|see{minimisation}}\textbf{de Moore} ou \defin[minimisation + (algorithme de)]{de minimisation} ou \textbf{de réduction}. Voici +comment on peut le mettre en œuvre de façon plus concrète : \begin{itemize} \item s'assurer qu'on a affaire à un DFA \underline{\emph{complet sans état inaccessible}} (si nécessaire, déterminiser l'automate s'il @@ -2965,41 +3009,44 @@ représente : pour cela, on va définir la notion d'\emph{arbre \subsection{Définition, notations et premier exemple} -\thingy\label{definition-context-free-grammar} Une \textbf{grammaire - hors contexte} (on dit parfois aussi « sans contexte » ; en -anglais, « context-free grammar » ou « CFG » ; ou encore grammaire de +\thingy\label{definition-context-free-grammar} Une \defin{grammaire + hors contexte} (on dit parfois aussi « sans contexte » ; en anglais, +« context-free grammar » ou « CFG » ; ou encore grammaire de \textbf{type 2}) sur un alphabet $\Sigma$ est la donnée \begin{itemize} \item d'un second alphabet $N$, disjoint de $\Sigma$, appelé ensemble - des \textbf{nonterminaux}, -\item d'un élément $S \in N$ appelé \textbf{axiome} ou \textbf{symbole - initial} de la grammaire, + des \defin[nonterminal]{nonterminaux}, +\item d'un élément $S \in N$ appelé \defin[axiome (d'une + grammaire)]{axiome} ou \index{initial + (symbole)|see{axiome}}\textbf{symbole initial} de la grammaire, \item d'un ensemble \emph{fini} $R \subseteq N \times (\Sigma\cup N)^*$ de couples $(T,\alpha)$ où $T$ est un nonterminal et $\alpha$ un mot sur l'alphabet $\Sigma\cup N$, les éléments $(T,\alpha)$ de - $R$ étant appelés les \textbf{règles} ou \textbf{productions} de la - grammaire. + $R$ étant appelés les \index{règle (d'une + grammaire)|see{production}}\textbf{règles} ou + \defin[production]{productions} de la grammaire. \end{itemize} \thingy Une grammaire hors contexte fait donc intervenir deux alphabets : l'alphabet $\Sigma$ sur lequel sera le langage (encore à définir), et l'alphabet $N$ (disjoint de $\Sigma$) qui intervient dans la définition de la grammaire. Pour fixer la terminologie, on -appellera \textbf{symbole} un élément de $\Sigma \cup N$, ces symboles -étant dits \textbf{terminaux} lorsqu'ils appartiennent à $\Sigma$ (ou -simplement « lettres »), et \textbf{nonterminaux} lorsqu'ils -appartiennent à $N$. Un mot sur $\Sigma\cup N$ (c'est-à-dire, une -suite finie de symboles) sera appelé \textbf{pseudo-mot}, tandis que -le terme « mot » sans précision supplémentaire sera utilisé pour -désigner un mot sur $\Sigma$ (autrement dit, un mot est un pseudo-mot -ne comportant que des symboles terminaux). - -Typographiquement, on aura tendance à utiliser des lettres minuscules -pour désigner les symboles terminaux, et majuscules pour désigner les -symboles nonterminaux ; et on aura tendance à utiliser des lettres -grecques minuscules pour désigner les pseudo-mots. (Mais il n'est pas -possible de suivre cette convention de façon complètement -systématique.) +appellera \defin{symbole} un élément de $\Sigma \cup N$, ces symboles +étant dits \defin[terminal]{terminaux} lorsqu'ils appartiennent +à $\Sigma$ (ou simplement « lettres »), et \textbf{nonterminaux} +lorsqu'ils appartiennent à $N$. Un mot sur $\Sigma\cup N$ +(c'est-à-dire, une suite finie de symboles) sera appelé +\defin{pseudo-mot}, tandis que le terme « \index{mot}mot » sans +précision supplémentaire sera utilisé pour désigner un mot +sur $\Sigma$ (autrement dit, un mot est un pseudo-mot ne comportant +que des symboles terminaux). + +{\footnotesize Typographiquement, on aura tendance à utiliser des + lettres minuscules pour désigner les symboles terminaux, et + majuscules pour désigner les symboles nonterminaux ; et on aura + tendance à utiliser des lettres grecques minuscules pour désigner + les pseudo-mots. Il n'est malheureusement pas possible d'être + complètement systématique.\par} \thingy Intuitivement, il faut comprendre la grammaire de la manière suivante. Les règles $(T,\alpha)$, où on rappelle que $T$ est un @@ -3031,32 +3078,33 @@ Concrètement, $\lambda\Rightarrow\xi$ signifie donc que $\xi$ est obtenu en remplaçant un nonterminal $T$ du pseudo-mot $\lambda$ par la partie droite d'une production $T \rightarrow \alpha$ de la grammaire $G$ : on dit encore que $\lambda \Rightarrow \xi$ est une -\textbf{dérivation immédiate} de $G$. On pourra dire que $T +\defin{dérivation immédiate} de $G$. On pourra dire que $T \rightarrow \alpha$ est la règle \textbf{appliquée} dans cette dérivation immédiate, que $T$ est le \textbf{symbole réécrit} (souvent souligné dans l'écriture de la dérivation immédiate), et que $\gamma$ -et $\gamma'$ sont respectivement le \textbf{contexte gauche} et le -\textbf{contexte droit} de l'application de la règle\footnote{Pour - être extrêmement rigoureux, une dérivation immédiate doit comporter - la donnée du symbole réécrit (ou de façon équivalente, du contexte - gauche et/ou droit), car elle ne peut pas se déduire de la seule - donnée de $\lambda$ et $\mu$ (par exemple, dans $XX \Rightarrow - XXX$, même si on sait que la règle appliquée était $X \rightarrow - XX$, on ne peut pas deviner si c'est le $X$ de gauche ou de droite - qui a été réécrit : il faut donc écrire $\underline{X}X \Rightarrow - XXX$ ou bien $X\underline{X} \Rightarrow XXX$, en soulignant le - symbole réécrit, pour distinguer les deux). De même, dans une - dérivation, on devrait inclure la donnée du symbole réécrit à chaque - étape.}. Bien sûr, si nécessaire, on précisera la grammaire -appliquée en écrivant $\lambda \mathrel{\Rightarrow_G} \xi$ au lieu de -simplement $\lambda\Rightarrow\xi$. +et $\gamma'$ sont respectivement le \index{contexte}\textbf{contexte + gauche} et le \textbf{contexte droit} de l'application de la +règle\footnote{Pour être extrêmement rigoureux, une dérivation + immédiate doit comporter la donnée du symbole réécrit (ou de façon + équivalente, du contexte gauche et/ou droit), car elle ne peut pas + se déduire de la seule donnée de $\lambda$ et $\mu$ (par exemple, + dans $XX \Rightarrow XXX$, même si on sait que la règle appliquée + était $X \rightarrow XX$, on ne peut pas deviner si c'est le $X$ de + gauche ou de droite qui a été réécrit : il faut donc écrire + $\underline{X}X \Rightarrow XXX$ ou bien $X\underline{X} \Rightarrow + XXX$, en soulignant le symbole réécrit, pour distinguer les deux). + De même, dans une dérivation, on devrait inclure la donnée du + symbole réécrit à chaque étape.}. Bien sûr, si nécessaire, on +précisera la grammaire appliquée en écrivant $\lambda +\mathrel{\Rightarrow_G} \xi$ au lieu de simplement +$\lambda\Rightarrow\xi$. Une suite de pseudo-mots $(\lambda_0,\ldots,\lambda_n)$ telle que \[ \lambda_0 \Rightarrow \lambda_1 \Rightarrow \cdots \Rightarrow \lambda_n \] autrement dit $\lambda_{i-1} \Rightarrow \lambda_i$ pour chaque $1\leq -i\leq n$, est appelée \textbf{dérivation} de $\lambda_n$ à partir de +i\leq n$, est appelée \defin{dérivation} de $\lambda_n$ à partir de $\lambda_0$ dans la grammaire $G$, et on note $\lambda_0 \mathrel{\Rightarrow^*} \lambda_n$ pour indiquer son existence (c'est-à-dire, si on préfère, que la relation $\Rightarrow^*$ est la @@ -3079,21 +3127,24 @@ qui est en fait un mot (sur $\Sigma$), ne peut pas être dérivé plus loin. Ceci justifie au moins en partie la terminologie de « terminal ». -\thingy Le \textbf{langage engendré} $L(G)$ par une grammaire -hors contexte $G$ est l'ensemble des mots $w$ (ne comportant plus de -nonterminaux !) qui peuvent s'obtenir par dérivation à partir de -l'axiome $S$ de $G$, autrement dit : +\thingy Le \defin[engendré (langage)]{langage engendré} $L(G)$ par une +grammaire hors contexte $G$ est l'ensemble des mots $w$ (ne comportant +plus de nonterminaux !) qui peuvent s'obtenir par dérivation à partir +de l'axiome $S$ de $G$, autrement dit : \[ L(G) = \{w \in \Sigma^* : S \mathrel{\Rightarrow^*} w\} \] Un langage qui peut s'écrire sous la forme $L(G)$ où $G$ est une -grammaire hors contexte est appelé \textbf{langage hors contexte} ou -\textbf{algébrique}. +grammaire hors contexte est appelé \index{hors contexte + (langage)|see{algébrique}}\textbf{langage hors contexte} ou +\defin[algébrique (langage)]{algébrique}. -Deux grammaires hors contexte $G$ et $G'$ sont dites -\textbf{faiblement équivalentes} ou \textbf{langage-équivalentes} -lorsqu'elles engendrent le même langage ($L(G) = L(G')$). +Deux grammaires hors contexte $G$ et $G'$ sont dites \defin[faiblement + équivalentes (grammaires)]{faiblement équivalentes} ou +\index{langage-équivalentes (grammaires)|see{faiblement + équivalentes}}\textbf{langage-équivalentes} lorsqu'elles +engendrent le même langage ($L(G) = L(G')$). \thingy\label{basic-example-context-free-grammar} À titre d'exemple, considérons la grammaire sur l'alphabet $\Sigma = \{a,b\}$ donnée par @@ -3135,17 +3186,18 @@ rationnels. En revanche, pour ce qui est de la réciproque, on verra dans la section suivante que tout langage rationnel est algébrique. \thingy Mentionnons brièvement qu'il existe des types de grammaires -plus généraux que les grammaires hors contexte. Les -\textbf{grammaires contextuelles} (ou grammaires de \textbf{type 1}) -sont définies par des règles du type $\gamma T \gamma' \rightarrow -\gamma \alpha \gamma'$ où $T$ est un nonterminal, et -$\alpha,\gamma,\gamma'$ des pseudo-mots (=mots sur l'alphabet de tous -les symboles), c'est-à-dire des règles qui autorisent la réécriture -d'un symbole $T$ en $\alpha$ mais uniquement s'il est entouré d'un -certain contexte ($\gamma$ à gauche, $\gamma'$ à droite). Les -\textbf{grammaires syntagmatiques générales} (ou grammaires de -\textbf{type 0}) sont définies par des règles de réécriture $\lambda -\rightarrow \mu$ où $\lambda,\mu$ sont des pseudo-mots quelconques. +plus généraux que les grammaires hors contexte. Les \defin[grammaire + contextuelle]{grammaires contextuelles} (ou grammaires de +\textbf{type 1}) sont définies par des règles du type $\gamma T +\gamma' \rightarrow \gamma \alpha \gamma'$ où $T$ est un nonterminal, +et $\alpha,\gamma,\gamma'$ des pseudo-mots (=mots sur l'alphabet de +tous les symboles), c'est-à-dire des règles qui autorisent la +réécriture d'un symbole $T$ en $\alpha$ mais uniquement s'il est +entouré d'un certain contexte ($\gamma$ à gauche, $\gamma'$ à droite). +Les \defin[grammaire syntagmatique]{grammaires syntagmatiques + générales} (ou grammaires de \textbf{type 0}) sont définies par des +règles de réécriture $\lambda \rightarrow \mu$ où $\lambda,\mu$ sont +des pseudo-mots quelconques. \subsection{Langages rationnels et algébriques, stabilité} @@ -3185,15 +3237,16 @@ t_n$ dérivé est précisément le mot formé en concacténant les \thingy Une grammaire hors contexte telle que construite dans la preuve de \ref{rational-languages-are-algebraic} est dite -\textbf{régulière} : autrement dit, il s'agit d'une grammaire ayant -uniquement des règles de la forme (A) $Q \rightarrow tQ'$ où $t \in -\Sigma\cup\{\varepsilon\}$ (certains auteurs imposent $t \in \Sigma$, -ce qui revient à imposer qu'on part d'un NFA sans ε-transition dans la -construction) et (B) $Q \rightarrow \varepsilon$ (certains auteurs -préfèrent $Q \rightarrow x$ avec $x\in\Sigma$, ce qui impose des -petits changements dans la construction ci-dessus). Les langages -définis par des grammaires régulières sont donc exactement les -langages rationnels. +\index{régulière (grammaire)|see{grammaire régulière}}\defin[grammaire + régulière]{régulière} : autrement dit, il s'agit d'une grammaire +ayant uniquement des règles de la forme (A) $Q \rightarrow tQ'$ où $t +\in \Sigma\cup\{\varepsilon\}$ (certains auteurs imposent $t \in +\Sigma$, ce qui revient à imposer qu'on part d'un NFA sans +ε-transition dans la construction) et (B) $Q \rightarrow \varepsilon$ +(certains auteurs préfèrent $Q \rightarrow x$ avec $x\in\Sigma$, ce +qui impose des petits changements dans la construction ci-dessus). +Les langages définis par des grammaires régulières sont donc +exactement les langages rationnels. \begin{prop}\label{cfg-union-concatenation-and-star} Si $L_1,L_2$ sont des langages algébriques (sur un même @@ -3403,13 +3456,14 @@ T &\rightarrow aSb\\ alors $L(G) = L(G,T)^*$ où $L(G,T) = a\, L(G)\, b$ désigne le langage des mots qui peuvent être dérivés à partir de $T$. -Ce langage $L(G)$ s'appelle langage des \textbf{expressions - bien-parenthésées} où $a$ représente une parenthèse ouvrante et $b$ -une parenthèse fermante (et $L(G,T)$ est le langage des blocs -parenthésés : autrement dit, une expression bien-parenthésée est une -suite de blocs parenthésés, et un bloc parenthésé est une expression -bien-parenthésée entourée par une parenthèse ouvrante et une -parenthèse fermante — c'est ce que traduit la grammaire). +Ce langage $L(G)$ s'appelle langage des \defin[bien-parenthésée + (expression)]{expressions bien-parenthésées} où $a$ représente une +parenthèse ouvrante et $b$ une parenthèse fermante (et $L(G,T)$ est le +langage des blocs parenthésés : autrement dit, une expression +bien-parenthésée est une suite de blocs parenthésés, et un bloc +parenthésé est une expression bien-parenthésée entourée par une +parenthèse ouvrante et une parenthèse fermante — c'est ce que traduit +la grammaire). \thingy\label{example-grammar-equal-a-and-b} Sur l'alphabet $\Sigma = \{a,b\}$, montrons que la grammaire $G$ (d'axiome $S$) donnée par @@ -3478,14 +3532,16 @@ tandis que $G'$ ne l'est pas. \subsection{Arbres d'analyse, dérivations gauche et droite} \thingy Soit $G$ une grammaire hors contexte sur un alphabet $\Sigma$ -et $N$ l'ensemble de ses nonterminaux. Un \textbf{arbre d'analyse} -(ou \textbf{arbre de dérivation} ; en anglais \textbf{parse tree}) -\textbf{incomplet} pour $G$ est un arbre (fini, enraciné et -ordonné\footnote{C'est-à-dire que l'ensemble des fils d'un nœud - quelconque de l'arbre est muni d'un ordre total, ou, ce qui revient - au même, qu'ils sont numérotés (disons de la gauche vers la - droite).}) dont les nœuds sont étiquetés par des éléments de $\Sigma -\cup N \cup \{\varepsilon\}$, vérifiant les propriétés suivantes : +et $N$ l'ensemble de ses nonterminaux. Un \defin{arbre d'analyse} (ou +\index{dérivation (arbre de)|see{arbre d'analyse}}\index{arbre de + dérivation|see{arbre d'analyse}}\textbf{arbre de dérivation} ; en +anglais \textbf{parse tree}) \textbf{incomplet} pour $G$ est un arbre +(fini, enraciné et ordonné\footnote{C'est-à-dire que l'ensemble des + fils d'un nœud quelconque de l'arbre est muni d'un ordre total, ou, + ce qui revient au même, qu'ils sont numérotés (disons de la gauche + vers la droite).}) dont les nœuds sont étiquetés par des éléments de +$\Sigma \cup N \cup \{\varepsilon\}$, vérifiant les propriétés +suivantes : \begin{itemize} \item la racine de l'arbre est étiquetée par l'axiome $S$ de $G$ ; \item si un nœud de l'arbre est étiqueté par $T$ et n'est pas une @@ -3610,7 +3666,8 @@ d'étapes dans la dérivation est égal au nombre de nœuds de l'arbre qui \emph{ne sont pas} des feuilles. Deux dérivations (forcément du même mot ou pseudo-mot) auxquelles sont -associées le même arbre d'analyse sont dites \textbf{équivalentes}. +associées le même arbre d'analyse sont dites \defin[équivalentes + (dérivations)]{équivalentes}. \thingy\label{example-of-derivations} À titre d'exemple, l'arbre illustré en \ref{example-of-parse-tree} est associé à la dérivation @@ -3633,7 +3690,7 @@ Ces deux dérivations sont donc équivalentes. Elles ont toutes les deux $10$ étapes puisque l'arbre considéré a $10$ nœuds qui ne sont pas des feuilles. -\thingy On appelle \textbf{dérivation gauche} une dérivation (pour une +\thingy On appelle \defin{dérivation gauche} une dérivation (pour une grammaire hors contexte donnée) dans laquelle le symbole réécrit est toujours \emph{le nonterminal le plus à gauche} du pseudo-mot courant : autrement dit, une dérivation gauche est une dérivation @@ -3661,10 +3718,11 @@ une et une seule dérivation droite. \subsection{Ambiguïté} -\thingy On dit qu'une grammaire hors contexte est \textbf{ambiguë} -lorsqu'il existe un mot (i.e., un mot sur l'alphabet $\Sigma$ des -terminaux) qui admet deux arbres d'analyse \emph{différents}. Dans le -cas contraire, elle est dite \textbf{inambiguë} : autrement dit, une +\thingy On dit qu'une grammaire hors contexte est \defin[ambiguë + (grammaire)]{ambiguë} lorsqu'il existe un mot (i.e., un mot sur +l'alphabet $\Sigma$ des terminaux) qui admet deux arbres d'analyse +\emph{différents}. Dans le cas contraire, elle est dite +\defin[inambiguë (grammaire)]{inambiguë} : autrement dit, une grammaire inambiguë est une grammaire $G$ pour laquelle tout $w \in L(G)$ a un unique arbre d'analyse ; il revient au même de dire que tout mot de $L(G)$ a une unique dérivation droite, ou encore que tout @@ -3792,15 +3850,16 @@ caractéristique de la \emph{grammaire} hors contexte et non du Cependant, certains langages algébriques ne sont définis \emph{que} par des grammaires hors contexte ambiguës. De tels langages sont dits -\textbf{intrinsèquement ambigus}. C'est le cas du langage $\{a^i b^i -c^j : i,j\in\mathbb{N}\} \cup \{a^i b^j c^j : i,j\in\mathbb{N}\}$ dont -on a vu en \ref{example-for-intrinsic-ambiguity} qu'il était -algébrique : il n'est pas évident (cela dépasse le cadre de ce cours) -de démontrer qu'il est intrinsèquement ambigu, mais on peut au moins -en donner une explication intuitive : quelle que soit la manière dont -on construit une grammaire engendrant ce langage, elle devra forcément -distinguer le cas de $a^i b^i c^j$ et celui de $a^i b^j c^j$, or ces -cas ne sont pas disjoints, il existe des mots $a^i b^i c^i$ qui sont à +\defin[intrinsèquement ambigu (langage algébrique)]{intrinsèquement + ambigus}. C'est le cas du langage $\{a^i b^i c^j : +i,j\in\mathbb{N}\} \cup \{a^i b^j c^j : i,j\in\mathbb{N}\}$ dont on a +vu en \ref{example-for-intrinsic-ambiguity} qu'il était algébrique : +il n'est pas évident (cela dépasse le cadre de ce cours) de démontrer +qu'il est intrinsèquement ambigu, mais on peut au moins en donner une +explication intuitive : quelle que soit la manière dont on construit +une grammaire engendrant ce langage, elle devra forcément distinguer +le cas de $a^i b^i c^j$ et celui de $a^i b^j c^j$, or ces cas ne sont +pas disjoints, il existe des mots $a^i b^i c^i$ qui sont à l'intersection des deux, et ce sont ces mots qui forcent ce langage à être intrinsèquement ambigu. @@ -4106,7 +4165,7 @@ construits (et éventuellement les arbres eux-mêmes). \setcounter{comcnt}{0} \thingy\textbf{Discussion préalable.} On s'intéresse ici à la question -de savoir ce qu'un \textbf{algorithme} peut ou ne peut pas faire. +de savoir ce qu'un \defin{algorithme} peut ou ne peut pas faire. Pour procéder de façon rigoureuse, il faudrait formaliser la notion d'algorithme (par exemple à travers le concept de machine de Turing) : on a préféré rester informel sur cette définition — par exemple « un @@ -4135,12 +4194,13 @@ tous sauf un nombre fini sont des blancs), les machines à registres, le langage « FlooP » de Hofstadter, etc. Toutes ces formalisations sont équivalentes (au sens où, par exemple, elles conduisent à la même notion de fonction calculable ou calculable partielle, définie -ci-dessous). La \textbf{thèse de Church-Turing} affirme, au moins -informellement, que tout ce qui est effectivement calculable par un -algorithme\footnote{Voire, dans certaines variantes, physiquement - calculable dans notre Univers.} est calculable par n'importe -laquelle de ces notions formelles d'algorithmes, qu'on peut rassembler -sous le nom commun de \textbf{calculabilité au sens de Church-Turing}, +ci-dessous). La \defin[Church-Turing (thèse de)]{thèse de + Church-Turing} affirme, au moins informellement, que tout ce qui est +effectivement calculable par un algorithme\footnote{Voire, dans + certaines variantes, physiquement calculable dans notre Univers.} +est calculable par n'importe laquelle de ces notions formelles +d'algorithmes, qu'on peut rassembler sous le nom commun de +\defin[calculable (fonction)]{calculabilité au sens de Church-Turing}, ou « calculabilité » tout court. Notamment, quasiment tous les langages de programmation @@ -4226,15 +4286,18 @@ bien compte que ces notions étaient forcément toujours incomplètes.) \begin{defn} On dit qu'une fonction $f\colon\mathbb{N}\to\mathbb{N}$ est -\textbf{calculable} (ou « récursive ») lorsqu'il existe un algorithme -qui prend en entrée $n\in\mathbb{N}$, termine toujours en temps fini, -et calcule (renvoie) $f(n)$. +\defin{calculable (fonction)} (ou \index{récursive + (fonction)|see{calculable}}« récursive ») lorsqu'il existe un +algorithme qui prend en entrée $n\in\mathbb{N}$, termine toujours en +temps fini, et calcule (renvoie) $f(n)$. On dit qu'un ensemble $A \subseteq \mathbb{N}$ (« langage ») est -\textbf{décidable} (ou « calculable » ou « récursif ») lorsque sa -fonction indicatrice $\mathbf{1}_A \colon \mathbb{N} \to \mathbb{N}$ -(valant $1$ sur $A$ et $0$ sur son complémentaire) est calculable. -Autrement dit : lorsqu'il existe un algorithme qui prend en entrée +\defin{décidable} (ou \index{calculable + (langage)|see{décidable}}« calculable » ou \index{récursif + (langage)|see{décidable}}« récursif ») lorsque sa fonction +indicatrice $\mathbf{1}_A \colon \mathbb{N} \to \mathbb{N}$ (valant +$1$ sur $A$ et $0$ sur son complémentaire) est calculable. Autrement +dit : lorsqu'il existe un algorithme qui prend en entrée $n\in\mathbb{N}$, termine toujours en temps fini, et renvoie « oui » ($1$) si $n\in A$, « non » ($0$) si $n\not\in A$ (on dira que l'algorithme « décide » $A$). @@ -4242,15 +4305,18 @@ l'algorithme « décide » $A$). On dit qu'une fonction partielle $f\colon\mathbb{N}\dasharrow\mathbb{N}$ (c'est-à-dire une fonction définie sur une partie de $\mathbb{N}$, appelé ensemble de définition -de $f$) est \textbf{calculable partielle} (ou « récursive partielle ») -lorsqu'il existe un algorithme qui prend en entrée $n\in\mathbb{N}$, -termine en temps fini ssi $f(n)$ est définie, et dans ce cas calcule -(renvoie) $f(n)$. (Une fonction calculable est donc simplement une -fonction calculable partielle qui est toujours définie : on dira -parfois « calculable totale » pour souligner ce fait.) +de $f$) est \defin[calculable partielle (fonction)]{calculable + partielle} (ou « récursive partielle ») lorsqu'il existe un +algorithme qui prend en entrée $n\in\mathbb{N}$, termine en temps fini +ssi $f(n)$ est définie, et dans ce cas calcule (renvoie) $f(n)$. (Une +fonction calculable est donc simplement une fonction calculable +partielle qui est toujours définie : on dira parfois « calculable +totale » pour souligner ce fait.) On dit qu'un ensemble $A \subseteq \mathbb{N}$ est -\textbf{semi-décidable} (ou « semi-calculable » ou « semi-récursif ») +\defin{semi-décidable} (ou \index{semi-calculable + (langage)|see{semi-décidable}}« semi-calculable » ou +\index{semi-récursif (langage)|see{semi-décidable}}« semi-récursif ») lorsque la fonction partielle $\mathbb{N}\dasharrow\mathbb{N}$ définie exactement sur $A$ et y valant $1$, est calculable partielle. Autrement dit : lorsqu'il existe un algorithme qui prend en entrée @@ -4305,7 +4371,7 @@ parfaits, des nombres premiers, sont décidables, c'est-à-dire qu'il est algorithmique de savoir si un nombre est pair, parfait, ou premier. Quitte éventuellement à coder les mots d'un alphabet fini comme des entiers naturels (cf. plus haut), tout langage rationnel, et -même tout langage défini par une grammaire hors-contexte, est +même tout langage défini par une grammaire hors contexte, est décidable. On verra plus bas des exemples d'ensembles qui ne le sont pas, et qui sont ou ne sont pas semi-décidables. @@ -4404,7 +4470,7 @@ d'un tel $k$). \thingy\textbf{Codage et machine universelle.} Les algorithmes sont eux-mêmes représentables par des mots sur un alphabet fini donc, si on -préfère, par des entiers naturels : on parle aussi de \textbf{codage +préfère, par des entiers naturels : on parle aussi de \defin{codage de Gödel} des algorithmes/programmes par des entiers. On obtient donc une énumération $\varphi_0, \varphi_1, \varphi_2, \varphi_3\ldots$ de toutes les fonctions calculables partielles (la @@ -4416,11 +4482,12 @@ de cette énumération dépendent de la formalisation utilisée pour la calculabilité. Un point crucial dans cette numérotation des algorithmes est -l'existence d'une \textbf{machine universelle}, c'est-à-dire d'un -algorithme $U$ qui prend en entrée un entier $e$ (codant un -algorithme $T$) et un entier $n$, et effectue la même chose que $T$ -sur l'entrée $n$ (i.e., $U$ termine sur les entrées $e$ et $n$ ssi $T$ -termine sur l'entrée $n$, et, dans ce cas, renvoie la même valeur). +l'existence d'une \defin[universelle (machine)]{machine universelle}, +c'est-à-dire d'un algorithme $U$ qui prend en entrée un entier $e$ +(codant un algorithme $T$) et un entier $n$, et effectue la même chose +que $T$ sur l'entrée $n$ (i.e., $U$ termine sur les entrées $e$ et $n$ +ssi $T$ termine sur l'entrée $n$, et, dans ce cas, renvoie la même +valeur). Informatiquement, ceci représente le fait que les programmes informatiques sont eux-mêmes représentables informatiquement : dans un @@ -4486,20 +4553,22 @@ Intuitivement, le « problème de l'arrêt » est la question « l'algorithme suivant termine-t-il sur l'entrée suivante » ? \begin{defn} -On appelle \textbf{problème de l'arrêt} l'ensemble des couples $(e,n)$ -tels que le $e$-ième algorithme termine sur l'entrée $n$, i.e., -$\{(e,n) \in \mathbb{N}^2 : \varphi_e(n)\downarrow\}$ (où la notation -« $\varphi_e(n)\downarrow$ » signifie que $\varphi_e(n)$ est défini, -i.e., l'algorithme termine). Quitte à coder les couples d'entiers -naturels par des entiers naturels (par exemple par $(e,n) \mapsto -2^e(2n+1)$), on peut voir le problème de l'arrêt comme une partie -de $\mathbb{N}$. On peut aussi préférer\footnote{Même si au final - c'est équivalent, c'est \textit{a priori} plus fort de dire que $\{e - \in \mathbb{N} : \varphi_e(e)\downarrow\}$ n'est pas décidable que - de dire que $\{(e,n) \in \mathbb{N}^2 : \varphi_e(n)\downarrow\}$ ne - l'est pas.} définir le problème de l'arrêt comme $\{e \in \mathbb{N} -: \varphi_e(e)\downarrow\}$, on va voir dans la démonstration -ci-dessous que c'est cet ensemble-là qui la fait fonctionner. +On appelle \index{arrêt (problème de l')|see{problème de + l'arrêt}}\defin{problème de l'arrêt} (ou « langage de l'arrêt ») +l'ensemble des couples $(e,n)$ tels que le $e$-ième algorithme termine +sur l'entrée $n$, i.e., $\{(e,n) \in \mathbb{N}^2 : +\varphi_e(n)\downarrow\}$ (où la notation « $\varphi_e(n)\downarrow$ » +signifie que $\varphi_e(n)$ est défini, i.e., l'algorithme termine). +Quitte à coder les couples d'entiers naturels par des entiers naturels +(par exemple par $(e,n) \mapsto 2^e(2n+1)$), on peut voir le problème +de l'arrêt comme une partie de $\mathbb{N}$. On peut aussi +préférer\footnote{Même si au final c'est équivalent, c'est \textit{a + priori} plus fort de dire que $\{e \in \mathbb{N} : + \varphi_e(e)\downarrow\}$ n'est pas décidable que de dire que + $\{(e,n) \in \mathbb{N}^2 : \varphi_e(n)\downarrow\}$ ne l'est pas.} +définir le problème de l'arrêt comme $\{e \in \mathbb{N} : +\varphi_e(e)\downarrow\}$, on va voir dans la démonstration ci-dessous +que c'est cet ensemble-là qui la fait fonctionner. \end{defn} {\footnotesize (On pourrait aussi définir le problème de l'arrêt comme @@ -4670,6 +4739,16 @@ construire un algorithme résolvant le problème de l'arrêt. +% +% +% + +\printindex + + + + + % |