1 files changed, 259 insertions, 0 deletions
diff --git a/errata-notes-inf105.tex b/errata-notes-inf105.tex
new file mode 100644
index 0000000..cb2e0d6
--- /dev/null
+++ b/errata-notes-inf105.tex
@@ -0,0 +1,259 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[a4paper,twoside,inner=2.75cm,outer=2.25cm,vmargin=3cm]{geometry}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+%\usepackage{tikz}
+%\usetikzlibrary{arrows,automata,positioning,calc}
+%
+\newcommand{\limp}{\mathrel{\Longrightarrow}\relax}
+\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
+\DeclareUnicodeCharacter{0101}{\=a}
+\DeclareUnicodeCharacter{1E47}{\d{n}}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+%
+\DeclareFontFamily{U}{manual}{} 
+\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
+\newcommand{\manfntsymbol}[1]{%
+    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
+\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
+\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
+  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
+%
+\newcommand{\defin}[2][]{\def\latexsucks{#1}\ifx\latexsucks\empty\index{#2}\else\index{\latexsucks}\fi\textbf{#2}}
+%
+%
+%
+\begin{document}
+\title{THL (Théorie des langages)\\Notes de cours : errata}
+\author{David A. Madore}
+\maketitle
+
+\centerline{\textbf{INF105}}
+
+{\footnotesize
+\immediate\write18{sh ./vc > vcline.tex}
+\begin{center}
+Git: \input{vcline.tex}
+\end{center}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pretolerance=8000
+\tolerance=50000
+\linepenalty=5  % Default is supposedly 10
+
+\vskip1cm
+
+
+%
+%
+%
+
+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)$ ».
+
+\medskip
+
+{\footnotesize
+
+¶1.5.3, dernier paragraphe, (page 14), au lieu de « racourcis », lire
+« raccourcis ».
+
+\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
+
+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).
+
+\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}
+
+\medskip
+
+¶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}
+
+\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é ».
+
+\smallskip
+
+¶4.7.6, premier paragraphe, (page 66), au lieu de « meme », lire
+« même ».
+
+\par}
+
+\medskip
+
+Définition 5.1.5, premier paragraphe, (page 70), retirer la parenthèse
+« (fonction) » après « calculable » (qui était destinée à l'index
+uniquement).
+
+\medskip
+
+{\footnotesize
+
+Définiiton 5.1.5, deuxième paragraphe, (page 66), pour éclaircir la
+syntaxe, ajouter « et » devant « « non » ($0$) ».
+
+\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 ».
+
+\medskip
+
+¶5.2.1, note en bas de page 28, (page 73), retirer la virgule après
+« Java ».
+
+\medskip
+
+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 ».
+
+\medskip
+
+Démonstration du théorème 5.2.4, deuxième paragraphe, (page 74), pour
+éclaircir la syntaxe, ajouter « et ensuite » devant « (2º) ».
+
+\par}
+
+%
+%
+%
+\end{document}