diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 162 |
1 files changed, 83 insertions, 79 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 806e3b4..af7df7e 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -367,7 +367,7 @@ signifie exactement ce qui vient d'être dit). \thingy\label{powers-of-a-word} Lorsque $w \in \Sigma^*$ et $r \in \mathbb{N}$, on définit un mot $w^r$ comme la concaténation de $r$ -facteurs tous égaux au mot $w$, autrement dit, comme la répétition $r$ +mots tous égaux à $w$, autrement dit, comme la répétition $r$ fois du mot $w$. Formellement, on définit par récurrence : \begin{itemize} \item $w^0 = \varepsilon$ (le mot vide), @@ -473,8 +473,9 @@ définition ci-dessus, on pourra prendre $(i_1,i_2,i_3) = (1,4,6)$). facteurs (car un facteur est déterminé par sa longueur $k$ et son point de départ qui peut être choisi parmi $n+1-k$ possibilités, le $+1$ final étant mis pour le facteur vide), -\item au plus $2^n$ sous-mots (car un sous-mot est déterminé par - l'ensemble $\{i_1,\ldots,i_k\}$ des indices de ses lettres). +\item au plus $2^n$ sous-mots (car un sous-mot est déterminé en + choisissant, pour chacune des $n$ lettres, si on l'efface ou la + conserve). \end{itemize} Le nombre exact peut être plus petit en cas de coïncidences entre certains choix (par exemple, $aaa$ n'a que $4$ facteurs, $\varepsilon, @@ -512,7 +513,7 @@ 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 cardinal de l'ensemble $\{i : x_i = z\}$. On peut remarquer qu'on a : $|w| = \sum_{z\in\Sigma} |w|_z$ (i.e., la longueur de $w$ est la somme -des nombres d'occurrences dedans des différentes lettres de +des nombres d'occurrences dans celui-ci des différentes lettres de l'alphabet).\par} @@ -851,7 +852,7 @@ considérer les langages de base triviaux suivants : \begin{itemize} \item le langage vide $\varnothing$, \item le langage constitué du seul mot vide, $\{\varepsilon\}$, et -\item les langages constitué d'un seul mot lui-même formé d'une seule +\item les langages constitués d'un seul mot lui-même formé d'une seule lettre, $\{x\}$ pour chaque $x\in\Sigma$, \end{itemize} et on va les combiner par les opérations dites « rationnelles » @@ -886,11 +887,11 @@ cccc,\ldots\}$, est rationnel, et comme $\{d\}$ l'est aussi, la concaténation $\{d\}(\{c\}^*) = \{d, dc, dcc, dccc, \ldots\}$ est encore un langage rationnel. -\thingy\label{stable-under-rational-operations} -Formellement, la définition des langages rationnelles est la -suivante : un ensemble $\mathscr{C} \subseteq \mathscr{P}(\Sigma^*)$ -de langages (où $\mathscr{P}(\Sigma^*)$ est l'ensemble des parties de -$\Sigma^*$, i.e., l'ensemble de tous les langages sur $\Sigma$, +\thingy\label{stable-under-rational-operations} Formellement, la +définition des langages rationnelles est la suivante : un ensemble +$\mathscr{C} \subseteq \mathscr{P}(\Sigma^*)$ de langages (où +$\mathscr{P}(\Sigma^*)$ est l'ensemble des parties de $\Sigma^*$, +i.e., l'ensemble de tous les langages sur $\Sigma$, cf. \ref{set-of-languages}) est dit \emph{stable par opérations rationnelles} lorsqu'il est stable par les opérations de réunion, concaténation et étoile de Kleene, i.e., si $L_1,L_2 \in \mathscr{C}$ @@ -901,8 +902,8 @@ si $L \in \mathscr{C}$ alors $L^* \in \mathscr{C}$ ; le \emph{plus opérations rationnelles : l'ensemble $\mathscr{P}(\Sigma^*)$ de tous les langages est aussi évidemment stable par opérations rationnelles ; on s'intéresse au plus petit $\mathscr{C}$ possible - pour n'avoir que ce qui est nécessairement construit à partir des - langages de base triviaux par les opérations rationnelles.} (pour + pour n'avoir que ce qu'on peut construire à partir des langages de + base triviaux par un nombre fini d'opérations rationnelles.} (pour l'inclusion) ensemble de langages stable par opérations rationnelles et contenant les langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ pour $x \in \Sigma$ (i.e. $\varnothing\in\mathscr{C}$, @@ -1013,7 +1014,7 @@ $\Sigma = \{a,b,c,d\}$ : \item l'expression rationnelle $(a|(bc){*})$ dénote le langage $\{a\} \cup \{bc\}^* = \{a,\penalty0 \varepsilon,\penalty1000 bc,\penalty1000 bcbc,\penalty1000 bcbcbc, \ldots\}$ ; -\item l'expression rationnelle $(a|(bc){*})d$ dénote le langage $\{a, d, +\item l'expression rationnelle $(a|(bc){*})d$ dénote le langage $\{ad, d, bcd, bcbcd, bcbcbcd, \ldots\}$ ; \item l'expression rationnelle $\bot d$ dénote le langage vide $\varnothing$ (car il n'y a pas de mot dans le langage vide, @@ -1129,7 +1130,7 @@ que ce double sens existe (soit comme disjonction, soit comme l'opération de \ref{kleene-plus}). {\footnotesize Les métacaractères $\bot$ et $\underline{\varepsilon}$ - sont introduits ici par souci de complétude mais font rarement + sont introduits ici par souci de complétude mais sont rarement utilisés dans les expressions rationnelles (le métacaractère $\underline{\varepsilon}$ a été souligné parce qu'il s'agit d'une vraie lettre et non pas du mot vide ; on peut ignorer cette @@ -1313,7 +1314,7 @@ définir sont informellement décrits ainsi : défini, suivent à chaque lettre consommée une transition bien définie vers un nouvel état, et leur comportement est donc entièrement déterministe (d'où le nom) ; -\item les automate fini déterministe à spécification incomplète +\item les automates finis déterministes à spécification incomplète (cf. \ref{definition-dfai}) : la différence est qu'ici l'automate n'a pas forcément d'instruction sur quoi faire quand il est dans un certain état et reçoit un certain symbole, il peut manquer des @@ -1376,9 +1377,10 @@ des éléments de $\Sigma$ : plus exactement, on trace un nœud pour chaque élément $q \in Q$, et lorsque $\delta(q,x) = q'$ on introduit une flèche $q \to q'$ étiquetée par la lettre $x$. -La condition sur $\delta$ (pour être un DFA) est alors que, pour -chaque état $q \in Q$ et chaque lettre $x \in \Sigma$, \emph{il existe - une unique} arête partant de $q$ et étiquetée par $x$. +La condition cruciale (pour être un DFA) est que, pour chaque état $q +\in Q$ et chaque lettre $x \in \Sigma$, \emph{il existe une unique} +arête partant de $q$ et étiquetée par $x$ (c'est essentiellement une +reformulation du fait que $\delta$ est une fonction). En outre, on introduit une flèche pointant de nulle part vers $q_0$ (pour marquer celui-ci comme l'état initial), et pour chaque $q\in F$ @@ -1484,7 +1486,7 @@ utile de remarquer que $\delta^*(q,ww') = Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$ \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 +$\delta^*(q_0,w) \in F$ ; dans le cas contraire, on dira qu'il \textbf{rejette} le mot $w$. \thingy\label{definition-recognizable-language} L'ensemble $L(A)$ @@ -1596,8 +1598,8 @@ eux. \defin{automate fini déterministe incomplet}\footnote{\label{footnote-on-word-incomplete}Le mot « incomplet » signifie en fait « non nécessairement complet », i.e., - l'automate a le droit de manquer certaines transitions, il peut très - bien être complet (un DFA est un DFAi particulier, pas le + l'automate a le droit de manquer certaines transitions, mais il peut + très bien être complet (un DFA est un DFAi particulier, pas le contraire).}, en abrégé \index{DFAi|see{automate fini déterministe incomplet}}\textbf{DFAi}, sur un alphabet $\Sigma$ est la donnée \begin{itemize} @@ -1798,7 +1800,7 @@ accessible d'un DFAi comme pour un DFA On dira en outre d'un état $q$ d'un DFAi qu'il est \defin[co-accessible (état)]{co-accessible} lorsqu'il existe un mot $w -\in \Sigma^*$ tel que $\delta(q,w)$ soit défini et soit final, +\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 @@ -1806,8 +1808,8 @@ 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). +non co-accessibles (ainsi, bien sûr, que toutes les transitions qui y +conduisent) et obtenir de nouveau un DFAi. \smallskip @@ -2207,7 +2209,7 @@ Autrement dit, $w$ est accepté lorsqu'\emph{il existe} $q_0,\ldots,q_n $q_0 \in I$ et $q_n\in F$ et $(q_{i-1},t_i,q_i) \in \delta$ pour chaque $1\leq i\leq n$ et $w = t_1\cdots t_n$ (\emph{attention} : dans 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 +de $w$, certains des $t_i$ peuvent être le mot vide $\varepsilon$, les lettres de $w$ sont obtenues en ignorant ces symboles). \thingy On veut de nouveau définir une relation $\delta^*$ telle que @@ -2441,7 +2443,7 @@ stables par différentes opérations. Dans cette section, nous traitons le cas des opérations booléennes (complémentaire, union, intersection) et l'opération « miroir » ; la section \ref{subsection-recognizable-languages-under-rational-operations} -traite des opérations booléennes. +traite des opérations rationnelles. \begin{prop}\label{dfa-complement} Si $L$ est un langage reconnaissable sur un alphabet $\Sigma$, alors @@ -2516,12 +2518,11 @@ $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 -par les DFA : elle aurait aussi fonctionné pour les DFAi mais pas pour -les NFA ; il est intéressant de réfléchir à pourquoi. (Une -construction du type produit pourrait fonctionner sur les NFA pour le -langage réunion, mais elle n'a aucun intérêt par rapport à la +La construction de l'automate produit pour fabriquer le langage union +ou intersection utilise la caractérisation des langages +reconnaissables par les DFA ; une construction du même type pourrait +être définie pour les NFA, mais uniquement pour le langage +intersection. (Pour la réunion effectuée sur les NFA, on renvoie à la construction présentée en \ref{nfa-union}.) \begin{prop}\label{nfa-mirror} @@ -2668,7 +2669,7 @@ des NFA standards tels que $L_1 = L(A_1)$ et $L_2 = L(A_2)$. L'automate $A'$ s'obtient réunissant $A_1$ et $A_2$ mais en « fusionnant » les états initiaux $q_1$ et $q_2$ de $A_1$ et $A_2$ en un unique état initial $q'_0$, d'où partent les mêmes transitions -(avec les mêmes étiquettes) que depuis l'un ou de l'autre de +(avec les mêmes étiquettes) que depuis l'un ou l'autre de $q_1$ ou $q_2$. Graphiquement : \begin{center} @@ -2739,8 +2740,8 @@ $\varphi_2\colon Q_2 \to Q'$ de façon analogue. On définit alors l'automate $A'$ dont l'ensemble d'états est $Q'$, l'état initial est $q'_0$, les états finaux $F' = \varphi_1(F_1) \cup \varphi_2(F_2)$, et la relation de transition $\delta'$ est formée des -triplets $(\varphi_1(q),x,q')$ où $q,q'\in Q_1$ et des -$(\varphi_2(q),x,q')$ où $q,q'\in Q_2$. +triplets $(\varphi_1(q),x,q')$ où $(q,x,q') \in \delta_1$ et des +$(\varphi_2(q),x,q')$ où $(q,x,q') \in \delta_2$. (\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en ajoutant d'abord un unique état initial $q'_0$ à la réunion disjointe @@ -2915,9 +2916,9 @@ devient De façon plus formelle, on considère l'automate $A'$ dont l'ensemble d'états est $Q' := Q$, l'état initial est $q_0$, les états finaux $F' -:= F$, et la relation de transition $\delta'$ est la réunion de -$\delta$ et de l'ensemble des triplets $(q,x,q')$ tels que $(q_0,x,q') -\in \delta$ et que $q \in F$. +:= F \cup \{q_0\}$, et la relation de transition $\delta'$ est la +réunion de $\delta$ et de l'ensemble des triplets $(q,x,q')$ tels que +$(q_0,x,q') \in \delta$ et que $q \in F$. (\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en ajoutant d'abord à $A$ une ε-transition de chaque état final de $A$ @@ -2972,7 +2973,7 @@ le dénotant. En particulier, il existe un algorithme qui, donnée une expression rationnelle $r$ (sur un alphabet $\Sigma$) et un mot $w \in \Sigma^*$, décide si $w\in L(r)$, c'est-à-dire si $w$ vérifie $r$. (Autrement -dit, les langages algébriques sont \emph{décidables} au sens +dit, les langages rationnels sont \emph{décidables} au sens de \ref{definition-computable-function-or-set}.) \end{cor} \begin{proof} @@ -2989,7 +2990,7 @@ algorithmique plus précise. Pour décider si un mot $w$ vérifie une expression rationnelle $r$, on commence par transformer cette expression rationnelle en NFA comme on -vient de l'expliquer (c'est-à-dire à construire un NFA $A(r)$ +vient de l'expliquer (c'est-à-dire construire un NFA $A(r)$ reconnaissant le langage $L(r)$ dénoté par $r$), puis on déterminise cet automate (cf. \ref{determinization-of-nfa}), après quoi il est facile de tester si le DFA résultant de la déterministaion accepte le @@ -3032,7 +3033,7 @@ définie en \ref{regular-expressions}) : \smallskip -Cette automate de Glushkov $A_{\textrm{Glushkov}}(r)$ possède les +Cet automate de Glushkov $A_{\textrm{Glushkov}}(r)$ possède les propriétés suivantes : \begin{itemize} \item c'est un NFA reconnaissant le langage $L(r)$ dénoté par @@ -3358,7 +3359,7 @@ l'expression rationnelle $(a|b){*}b$ : } \end{center} -(Il a $10$ états puisqu'il y a $5$ autres que les parenthèses +(Il a $10$ états puisqu'il y a $5$ symboles autres que les parenthèses dans $(a|b){*}b$.) Pour comparaison, voici son automate de Glushkov : @@ -3408,8 +3409,8 @@ rationnelle conduit à l'automate de Glushkov de cette même expression. \end{prop} Sans que cela constitue une démonstration, on peut comprendre l'idée -en considérant les « remarques » qui ont été faites dans la -démonstration de \ref{nfa-union}, \ref{nfa-concatenation} +en considérant les « remarques » qui ont été faites dans les +démonstrations de \ref{nfa-union}, \ref{nfa-concatenation} et \ref{nfa-star}. @@ -3577,9 +3578,9 @@ soit $L(r) = L(A)$. De plus, $r$ se déduit algorithmiquement de $A$. On a expliqué qu'on pouvait considérer une expression rationnelle comme un RNFA ayant un unique état initial, un unique état final, et une unique transition de l'un vers l'autre (étiquetée par l'expression -rationnelle en question). On va construire montrer que $A$ est -équivalent à un RNFA de cette nature, ce qui montrera bien qu'il est -équivalent à une expression rationnelle. +rationnelle en question). On va montrer que $A$ est équivalent à un +RNFA de cette nature, ce qui montrera bien qu'il est équivalent à une +expression rationnelle. Remarquons tout d'abord qu'on peut supposer que $A$ a un unique état initial $q_0$, qui ne soit pas final, et qui n'ait aucune transition @@ -3631,7 +3632,7 @@ telle paire, on remplace l'étiquette de la transition $r_{12}$ entre eux par $(r_{12}|r_1(s){*}r_2)$. Ceci ne change pas le fonctionnement de l'automate, car tout chemin dans $A$ peut être remplacé par un chemin dans $A'$ en effaçant simplement les $q$ (si on considère -$q_1$ et $q_2$ les états avant un bloc de de $q$ dans le chemin, on +$q_1$ et $q_2$ les états avant un bloc de $q$ dans le chemin, on voit que le chemin $q_1 \to q \to q \to \cdots \to q \to q_2$ peut se transformer en $q_1 \to q_2$ en consommant un mot qui vérifie l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$). @@ -3652,7 +3653,7 @@ proposition s'appelle l'algorithme d'\defin{élimination des états} ou et McCluskey.}. 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$ +transition de $q_1$ vers $q$ ou qu'il n'y en a pas de $q$ vers $q_2$ (c'est-à-dire que soit $r_1$ soit $r_2$ doit être considéré comme valant $\bot$), on ne touche simplement pas à $r_{12}$ (et si la transition de $q_1$ vers $q_2$ n'existait pas non plus, il n'y a pas @@ -4269,11 +4270,12 @@ Voici comment on peut le mettre en œuvre de façon plus concrète : sont aussi dans la même classe) ; \item si $\Pi$ est la (dernière) partition ainsi obtenue, l'ensemble des états de l'automate construit est l'ensemble des classes - de $\Pi$, les états finaux sont les classes qui contiennent un état - final (ils sont alors forcément tous finaux), et la fonction de - transition est obtenue en prenant la fonction de transition sur un - représentant quelconque de la classe (la classe ne doit pas dépendre - du représentant). + de $\Pi$, l'état initial est la classe de l'état initial, les états + finaux sont les classes qui contiennent un état final (ils sont + alors forcément tous finaux), et la fonction de transition est + obtenue en prenant la fonction de transition sur un représentant + quelconque de la classe (la classe ne doit pas dépendre du + représentant). \end{itemize} \smallskip @@ -4519,11 +4521,11 @@ Il faut comprendre ces règles de la manière suivante : « pour définir une instruction ($\mathit{Statement}$), on peut mettre un $\mathtt{begin}$ suivi d'un bloc ($\mathit{Block}$) suivi d'un $\mathtt{end}$, ou bien un $\mathtt{if}$ suivi d'une expression -($\mathit{Expression}$) suivi d'un $\mathtt{then}$ suivi d'une -instruction, éventuellement suivie encore d'un $\mathtt{else}$ et -d'une nouvelle instruction, et enfin un $\mathtt{fi}$ ; pour définir -un bloc ($\mathit{Block}$), on peut soit ne rien mettre du tout, soit -mettre une instruction suivi d'un nouveau bloc ». +($\mathit{Expression}$) suivi d'un $\mathtt{then}$ suivi d'un bloc, +éventuellement suivie encore d'un $\mathtt{else}$ et d'un nouveau +bloc, et enfin un $\mathtt{fi}$ ; pour définir un bloc +($\mathit{Block}$), on peut soit ne rien mettre du tout, soit mettre +une instruction suivi d'un nouveau bloc ». \smallskip @@ -4608,14 +4610,14 @@ contient que des terminaux. \thingy Intuitivement, il faut comprendre la grammaire de la manière suivante. Les règles $(T,\alpha)$, où on rappelle que $T$ est un -symbole nonterminal et $\alpha$ un pseudo-mot doivent se comprendre -intuitivement comme « le symbole $T$ peut être remplacé par $\alpha$ » -(et on notera $T \rightarrow \alpha$, cf. ci-dessous). On part de -l'axiome $S$, et on peut effectuer librement des substitutions $T -\rightarrow \alpha$ (consistant à remplacer un nonterminal $T$ par un -pseudo-mot $\alpha$) autorisées par les règles : le langage défini par -la grammaire est l'ensemble de tous les mots (ne comportant plus aucun -nonterminal) qu'on peut obtenir de la sorte. +symbole nonterminal et $\alpha$ un pseudo-mot, doivent se comprendre +comme « le symbole $T$ peut être remplacé par $\alpha$ » (et on notera +$T \rightarrow \alpha$, cf. ci-dessous). On part de l'axiome $S$, et +on peut effectuer librement des substitutions $T \rightarrow \alpha$ +(consistant à remplacer un nonterminal $T$ par un pseudo-mot $\alpha$) +autorisées par les règles : le langage défini par la grammaire est +l'ensemble de tous les mots (ne comportant plus aucun nonterminal) +qu'on peut obtenir de la sorte. Rendons maintenant cette définition précise : @@ -4646,7 +4648,7 @@ et $\gamma'$ sont respectivement le \index{contexte}\textbf{contexte 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, + se déduire de la seule donnée de $\lambda$ et $\xi$ (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 @@ -4793,7 +4795,7 @@ façon à avoir $L(G) = L(A)$. \begin{proof} Soit $A$ un εNFA : on sait qu'on peut supposer sans perte de généralité qu'il a un unique état initial $q_0$ (quitte à en créer un -et à remplacer tout état $q$ anciennement initial par une ε-transition +et à ajouter pour tout état $q$ anciennement initial une ε-transition $q_0 \to q$). Soit $Q$ son ensemble des états et $\delta \subseteq Q \times (\Sigma\cup\{\varepsilon\}) \times Q$ sa fonction de transition. On construit une grammaire hors contexte $G$ dont @@ -4839,7 +4841,7 @@ grammaires régulières sont donc exactement les langages rationnels. reste vrai que les langages définis par des grammaires régulières sont exactement les langages rationnels.\par} -Les grammaires régulière sont également appelées grammaires de +Les grammaires régulières sont également appelées grammaires de \textbf{type 3}. \begin{prop}\label{cfg-union-concatenation-and-star} @@ -5187,7 +5189,7 @@ On dit de plus que l'arbre est \textbf{complet}, ou simplement qu'il s'agit d'un arbre d'analyse, lorsqu'il vérifie la propriété supplémentaire suivante : \begin{itemize} -\item foute feuille de l'arbre est étiquetée soit par un terminal +\item toute feuille de l'arbre est étiquetée soit par un terminal (= élément de $\Sigma$) soit par $\varepsilon$. \end{itemize} @@ -5754,10 +5756,10 @@ considère l'ensemble (fini !) $(\Sigma\cup N)^{\leq|w|}$ de tous les pseudo-mots de longueur $\leq |w|$. On construit et on explore progressivement (par exemple par un algorithme de Dijkstra / parcours en largeur), à partir de $S$, le graphe sur cet ensemble de sommets -dont les arêtes sont les dérivations immédiates de $G'$ à condition -que le membre de droite soit de longueur $\leq |w|$ : comme la -grammaire $G'$ est monotone, toute dérivation de $w$ sera un chemin -dans le graphe qu'on vient de dire (elle ne peut pas passer par des +dont les arêtes sont les dérivations immédiates de $G'$ (dont le +membre de droite soit de longueur $\leq |w|$) : comme la grammaire +$G'$ est monotone, toute dérivation de $w$ sera un chemin dans le +graphe qu'on vient de dire (elle ne peut pas passer par des pseudo-mots de longueur $>|w|$), donc on peut détecter sur ce graphe fini si une telle dérivation existe. \end{proof} @@ -5812,7 +5814,7 @@ normale de Chomsky, on effectue les transformations suivantes : point de \ref{algebraic-languages-are-decidable}. À ce stade-là, le membre de droite de chaque règle est de longueur exactement $1$ ou $2$ (et dans le second cas, constitué de deux nonterminaux). -\item Pour chaque règle $U \rightarrow \alpha$ où $\alpha$ n'est pas +\item Pour chaque règle $V \rightarrow \alpha$ où $\alpha$ n'est pas un unique nonterminal, et chaque terminal tel qu'il existe une suite $T \rightarrow \cdots \rightarrow V$ de règles produisant à chaque fois un unique nonterminal, et réécrivant $T$ en $V$, introduire une @@ -5912,7 +5914,7 @@ les deux cas. De façon très simplifiée : depuis la gauche (« L ») et génèrent la dérivation droite (« R ») de l'arbre d'analyse fabriqué, en partant des feuilles et en remontant jusqu'aux racines. La pile de l'analyseur LR sert, intuitivement, à - mémoriser les fragments d'arbre déjà construit, en partant des + mémoriser les fragments d'arbre déjà construits, en partant des feuilles, et qui restent encore à regrouper. \end{itemize} @@ -6311,7 +6313,8 @@ affaire à un seul paramètre entier. calculables, ainsi que la fonction qui à $(m,n,p,q)$ associe $p$ si $m=n$ et $q$ sinon ; toute composée de fonctions calculables (partielle ou totale) est calculable idem ; si $\underline{m} - \mapsto g(\underline{m})$ est calculable (partielle ou totale) et + \mapsto g(\underline{m})$ est calculable (partielle ou totale, + où $\underline{m}$ désigne une liste d'entiers) et que $(\underline{m}, n, v) \mapsto h(\underline{m}, n, v)$ l'est, alors la fonction $f$ définie par récurrence par $f(\underline{m},0) = g(\underline{m})$ et $f(\underline{m},n+1) = h(\underline{m}, n, @@ -6492,7 +6495,8 @@ On ne peut pas démontrer ce résultat ici faute d'une description rigoureuse d'un modèle de calcul précis, mais il n'a rien de conceptuellement difficile (même s'il peut être fastidieux à écrire dans les détails : écrire un interpréteur d'un langage de -programmation demande un minimum d'efforts). +programmation demande un minimum d'efforts). La machine universelle +dépend, bien sûr, du codage des algorithmes par des entiers naturels. {\footnotesize\thingy\textbf{Compléments :} Les deux résultats classiques suivants sont pertinents en lien avec la numérotation des |