summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-inf105.tex162
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