Write a list of errata (relative to version 28531fcd).

1 files changed, 65 insertions, 147 deletions

diff --git a/errata-notes-inf105.tex b/errata-notes-inf105.tex
index 4afd008..f233a55 100644
--- a/errata-notes-inf105.tex
+++ b/errata-notes-inf105.tex
@@ -71,187 +71,105 @@ Git: \input{vcline.tex}
 %
 %
 
+\newlength{\oldparindent}
+\oldparindent=\parindent
+\renewcommand{\narrower}{\advance\leftskip\oldparindent\advance\rightskip\oldparindent}
+\parindent=0pt
+\parskip=6ptplus6pt
+
 Les errata suivants sur le document « THL (Théorie des langages) /
 Notes de cours » sont relatifs à la version étiquetée
-\verb=f1826f0 Tue Nov 14 13:05:17 2017 +0100=
-et distribuée pour l'année universitaire 2017–2018.
-
-\medskip
-
-¶1.2.6, dernier paragraphe, (page 5), l'affirmation « Le suffixe
-correspondant au préfixe $abb$ est $bcab$ puisque $abbcab =
-(abb)(bcab)$ » est incorrecte, il faut remplacer $bcab$ par $cab$ et
-lire : « Le suffixe correspondant au préfixe $abb$ est $cab$ puisque
-$abbcab = (abb)(cab)$ ».
+\verb=28531fc Thu Jan 23 14:37:46 2020 +0100=
+et distribuée pour l'année universitaire 2020–2021.
 
 \medskip
 
-{\footnotesize
+Dans la démonstration de la proposition 3.2.4, qui constitue la
+construction de l'automate de Glushkov d'une concaténation, la
+construction donnée affirme à tort que les états finaux de l'automate
+construit sont uniquement ceux du second automate ($A_2$) concaténé.
+Or il faut aussi marquer comme finaux les états finaux de $A_1$
+\emph{lorsque (et seulement lorsque)} l'état initial $q_2$ de $A_2$
+était final.
 
-¶1.5.3, dernier paragraphe, (page 14), au lieu de « racourcis », lire
-« raccourcis ».
+Pour corriger cette erreur, ajouter à la fin de la phrase (page 32,
+lignes 11–13)
 
-\medskip
-
-Démonstration de la proposition 2.4.6, deuxième paragraphe, (page 27),
-dans la phrase « on crée une transition $q\to q'$ étiquetée par $x$ »,
-la précision que $x \in \Sigma$ peut être utile : remplacer par « on
-crée une transition $q\to q'$ étiquetée par $x \in \Sigma$ ».
-
-\par}
-
-\medskip
+{\narrower
 
-Démonstration du lemme 3.2.2, deuxième paragraphe, (page 30), le
-traitement des états finaux de l'automate $A'$ construit n'est pas
-correct, il faut marquer le nouvel état $q_0$ créé comme final
-lorsqu'il existait un état initial qui était aussi final.  En
-conséquence, remplacer les $F$ de ce paragraphe par $F'$, retirer le
-mot « et » devant « $\delta'$ est la réunion », et ajouter à la fin du
-paragraphe : « et enfin $F' = F$ ou $F' = F\cup\{q_0\}$ selon que
-$I\cap F = \varnothing$ ou $I\cap F \neq \varnothing$ respectivement
-(i.e., $q_0$ est final lorsqu'il existait déjà un état à la fois
-initial et final) ».  Le paragraphe ainsi modifié est le suivant :
-
-{\smallskip
-
-Formellement : soit $A = (Q,I,F,\delta)$.  On définit alors $A' =
-(Q',\{q_0\},F',\delta')$ de la manière suivante : $Q' = Q \uplus
-\{q_0\}$ (où $\uplus$ désigne une réunion disjointe), $\delta'$ est la
-réunion de l'ensemble des transitions $(q,x,q')$ qui étaient déjà
-dans $\delta$ et de l'ensemble des $(q_0,x,q')$ telles qu'il existe
-une transition $(q,x,q') \in \delta$ avec $q\in I$, et enfin $F' = F$
-ou $F' = F\cup\{q_0\}$ selon que $I\cap F = \varnothing$ ou $I\cap F
-\neq \varnothing$ respectivement (i.e., $q_0$ est final lorsqu'il
-existait déjà un état à la fois initial et final).
+L'automate $A'$ s'obtient en réunissant $A_1$ et $A_2$, en ne gardant
+que les états finaux de $A_2$, en supprimant $q_2$ et en remplaçant
+chaque transition sortant de $q_2$ par une transition identiquement
+étiquetée, et de même cible, partant de \emph{chaque} état final
+de $A_1$.
 
 \par}
 
-\medskip
-
-{\footnotesize
-
-¶3.6.3 (page 56), au lieu de « fącon », lire « façon ».
-
-\medskip
-
-¶4.0.1 (page 50), au lieu de « démarré », lire « démarrée ».
-
-\medskip
-
-¶4.1.7, second paragraphe, (page 53), pour alléger la syntaxe,
-déplacer la parenthèse commençant par « plus le numéro du type » à la
-fin du paragraphe : « 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 4.2.2 ci-dessous, forment une hiérarchie
-appelée 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. ».
-
-\medskip
-
-¶4.2.4, deuxième paragraphe, (page 55), au lieu de « racourci », lire
-« raccourci ».
-
-\par}
+la parenthèse suivante
 
-\medskip
+{\narrower
 
-¶4.4.1 (page 58), la rédaction ne rend pas suffisamment explicite le
-fait que tout nœud qui n'est pas une feuille doit être étiqueté par un
-nonterminal.  Pour rendre ce fait plus explicite, remplacer dans le
-deuxième tiret « si un nœud de l'arbre est étiqueté par $T$ et n'est
-pas une feuille (i.e., s'il a des fils) » par « si un nœud de l'arbre
-n'est pas une feuille (i.e., s'il a des fils) et si on appelle $T$ son
-étiquette », et ajouter après les deux sous-cas de ce tiret
-(c'est-à-dire après « dans $G$ », en passant à la ligne) la
-parenthèse : « 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$ ».
-Le passage ainsi modifié est le suivant :
-
-{\smallskip
-
-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é)
-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 n'est pas une feuille (i.e., s'il a des
-  fils) et si on appelle $T$ son étiquette, alors
-\begin{itemize}
-\item soit ce nœud a un unique fils étiqueté $\varepsilon$ et il
-  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$,
-\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}
+(ces derniers seront marqués finaux si $q_2$ était final dans $A_2$)
 
 \par}
 
-\medskip
-
-¶4.5.2, avant-dernier paragraphe (en-dessous des arbres, page 61),
-l'affirmation « Cette grammaire n'est donc pas ambiguë » est
-incorrecte.  Lire à la place : « Cette grammaire est donc ambiguë ».
-
-\medskip
-
-{\footnotesize
-
-¶4.7.5, dernier paragraphe, (page 66), au lieu de « complexitée »,
-lire « complexité ».
+et remplacer la phrase (page 32, lignes 15–18)
 
-\smallskip
+{\narrower
 
-¶4.7.6, premier paragraphe, (page 66), au lieu de « meme », lire
-« même ».
+On définit alors l'automate $A'$ dont l'ensemble d'états est $Q'$,
+l'état initial est $q_1$, les états finaux $F' = F_2$, et la relation
+de transition $\delta$ est la réunion de $\delta_1$, de l'ensemble des
+triplets $(q,x,q') \in \delta_2$ tels que $q\neq q_2$, et enfin de
+l'ensemble des triplets $(q,x,q')$ tels que $(q_2,x,q') \in \delta_2$
+et que $q\in F_1$.
 
 \par}
 
-\medskip
+par
 
-Définition 5.1.5, premier paragraphe, (page 70), retirer la parenthèse
-« (fonction) » après « calculable » (qui était destinée à l'index
-uniquement).
+{\narrower
 
-\medskip
+On définit alors l'automate $A'$ dont l'ensemble d'états est $Q'$,
+l'état initial est $q_1$, l'ensemble $F'$ des états finaux est $F_2$
+si $q_2$ n'était pas final dans $A_2$ et $F_1 \cup F_2$ si $q_2$ était
+final dans $A_2$, la relation de transition $\delta'$ est la réunion
+de $\delta_1$, de l'ensemble des triplets $(q,x,q') \in \delta_2$ tels
+que $q\neq q_2$, et enfin de l'ensemble des triplets $(q,x,q')$ tels
+que $(q_2,x,q') \in \delta_2$ et que $q\in F_1$.
 
-{\footnotesize
+\par}
 
-Définition 5.1.5, deuxième paragraphe, (page 66), pour éclaircir la
-syntaxe, ajouter « et » devant « « non » ($0$) ».
+On notera que, en revanche, la remarque qui suit la démonstration, et
+qui décrit une façon de voir la construction en passant par l'ajout
+temporaire de transitions spontanées, est correcte (l'élimination des
+transitions spontanées en question conduira à rendre finaux les états
+de $A_1$ lorsque $q_2$ l'état), et est probablement la façon la plus
+simple de mémoriser cette construction sans se tromper.
 
-\medskip
-
-¶5.1.10 (page 72), il manque « comme » avant le dernier mot :
-remplacer « donne bien le résultat final de $T$ résultat » par « donne
-bien le résultat final de $T$ comme résultat ».
+\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill}
 
 \medskip
 
-¶5.2.1, note en bas de page 28, (page 73), retirer la virgule après
-« Java ».
+Dans la démonstration de la proposition 3.4.7, qui constitue la
+procédure d'élimination des états, il n'est pas suffisamment clair
+quelles sont les paires d'états concernées par l'élimination de
+l'état $q$.  Pour remédier à ce manque de clarté, ajouter une note en
+bas de page après « simultanément pour toute paire » (page 40,
+ligne 14 en partant du bas) :
 
-\medskip
+{\narrower
 
-Démonstration du théorème 5.2.4, premier paragraphe, (page 74),
-remplacer « on n'a pas de choix que de ne pas terminer » par « la
-seule possibilité est de ne pas terminer ».
+Plutôt qu'examiner toutes les paires, on peut se contenter d'examiner
+les cas où \emph{soit} il existe une transition de $q_1$ vers $q_2$
+\emph{soit} il existe à la fois une transition de $q_1$ vers $q$ et
+une transition de $q$ vers $q_2$.  En revanche, insistons bien sur le
+fait que le cas où $q_1$ et $q_2$ coïncide doit être traité comme les
+autres.
 
-\medskip
+\par}
 
-Démonstration du théorème 5.2.4, deuxième paragraphe, (page 74), pour
-éclaircir la syntaxe, ajouter « et ensuite » devant « (2º) ».
 
-\par}
 
 %
 %