diff options
| -rw-r--r-- | errata-notes-inf105.tex | 212 |
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} % % |