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