From ad71bee741eccfe686b642e7a46101efa80a9e71 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 8 Jan 2018 14:34:05 +0100
Subject: Take into account Antoine's remarks.

---
 notes-inf105.tex | 23 +++++++++++++----------
 1 file changed, 13 insertions(+), 10 deletions(-)

(limited to 'notes-inf105.tex')

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 852c98a..0cf4d2a 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1199,7 +1199,7 @@ ASCII/Unicode\footnote{...ou parfois l'ordre de tri défini par la
   ni} \texttt{a} ni \texttt{e} ni\texttt{i} ni entre \texttt{o}
 et \texttt{z}).
 
-Toutes sortes d'autres racourcis ou commodités de notation peuvent
+Toutes sortes d'autres raccourcis ou commodités de notation peuvent
 exister, par exemple \texttt{\char"5C<} et \texttt{\char"5C>} pour
 désigner un début et une fin de mot (la définition précise de « mot »
 pouvant varier), ou encore \texttt{$r$\{$n_1$,$n_2$\}} qui cherche
@@ -4487,7 +4487,7 @@ principal intérêt de définir des \emph{syntaxes structurées}, par
 exemple la syntaxe d'un langage informatique (typiquement un langage
 de programmation).  En fait, l'étude des grammaires formelles en
 général, et des grammaires hors contexte en particulier, a été
-démarré\footnote{Certains font remonter leur origine bien plus loin :
+démarrée\footnote{Certains font remonter leur origine bien plus loin :
   on peut trouver une forme de grammaire hors contexte dans la manière
   dont l'Indien Pāṇini (probablement au IV\textsuperscript{e} siècle
   av. notre ère) décrit la grammaire du sanskrit.} en 1956 par le
@@ -4779,10 +4779,10 @@ remplacement à partir de l'axiome.
 
 Les grammaires de types 0 et 1, avec celles de type 2 c'est-à-dire
 hors contexte, et celles de type 3 (= régulières) qui seront définies
-en \ref{regular-grammar} ci-dessous, forment une hiérarchie (plus le
+en \ref{regular-grammar} ci-dessous, forment une hiérarchie appelée
+\defin[Chomsky (hiérarchie de)]{hiérarchie de Chomsky} : plus le
 numéro du type est élevé plus la grammaire est contrainte et plus la
-classe de langages définie est petite) appelée \defin[Chomsky
-  (hiérarchie de)]{hiérarchie de Chomsky}.
+classe de langages définie est petite.
 
 
 \subsection{Langages rationnels et algébriques, stabilité}
@@ -4903,7 +4903,7 @@ des règles d'une grammaire, d'écrire $T \rightarrow \alpha_1 | \cdots
 \rightarrow \alpha_1$ jusqu'à $T \rightarrow \alpha_n$.  Par exemple,
 la grammaire présentée en \ref{basic-example-context-free-grammar}
 peut s'écrire $S \rightarrow aSb | \varepsilon$.  Il s'agit d'un
-simple racourci d'écriture (comparer avec une convention semblable
+simple raccourci d'écriture (comparer avec une convention semblable
 faite pour les automates en \ref{graphical-representation-of-dfa}).
 
 {\footnotesize
@@ -5179,8 +5179,11 @@ suivantes :
   existe une règle $T \rightarrow \varepsilon$ dans $G$,
 \item soit ce nœud a des fils étiquetés par des éléments $x_1\cdots
   x_n$ (où $n\geq 1$) de $\Sigma \cup N$ et il existe une règle $T
-  \rightarrow x_1\cdots x_n$ dans $G$.
+  \rightarrow x_1\cdots x_n$ dans $G$,
 \end{itemize}
+(dans ces deux sous-cas, il résulte de l'existence d'une règle
+$T\rightarrow\cdots$ que $T$ est un nonterminal : seules les feuilles
+peuvent être étiquetées par un terminal ou $\varepsilon$).
 \end{itemize}
 
 \smallskip
@@ -5447,7 +5450,7 @@ mais aussi
 %%% end parsetree2b %%%
 \end{center}
 
-Cette grammaire n'est donc pas ambiguë.  Remarquons que le langage
+Cette grammaire est donc ambiguë.  Remarquons que le langage
 qu'elle engendre est $\{a\}^+ = \{a^n : n\geq 1\}$ (car il est évident
 que tout mot engendré par la grammaire est dans $\{a\}^+$, et
 réciproquement il est facile de fabriquer une dérivation de $a^n$ pour
@@ -5865,7 +5868,7 @@ L'algorithme qu'on vient de décrire (pour tester si $w \in L(G')$ une
 fois $G'$ sous forme normale de Chomsky) porte le nom
 d'\defin[Cocke-Younger-Kasami (algorithme de)]{algorithme de
   Cocke–Younger–Kasami} ou algorithme \index{CYK (algorithme
-  de)|see{Cocke-Younger-Kasami}}\textbf{CYK}.  Sa complexitée est
+  de)|see{Cocke-Younger-Kasami}}\textbf{CYK}.  Sa complexité est
 cubique en la longueur de $w$.
 
 \par}
@@ -6420,7 +6423,7 @@ d'un tel $k$).
   étapes de $T$ termine toujours (c'est bien l'intérêt), et (B) si
   l'algorithme $T$ termine effectivement, alors pour $m$ suffisamment
   grand, exécuter au plus $m$ étapes donne bien le résultat final
-  de $T$ résultat.\par}
+  de $T$ comme résultat.\par}
 
 {\footnotesize\thingy\textbf{Complément/exercice :} Un ensemble $A
   \subseteq \mathbb{N}$ infini est décidable si et seulement si il
-- 
cgit v1.2.3