summaryrefslogtreecommitdiffstats
path: root/errata-notes-inf105.tex
blob: cb2e0d6472087044a4d605aa2300d8d743556787 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
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}