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
|
%% 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
%
%
%
\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=28531fc Thu Jan 23 14:37:46 2020 +0100=
et distribuée pour l'année universitaire 2020–2021.
\medskip
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.
Pour corriger cette erreur, ajouter à la fin de la phrase (page 32,
lignes 11–13)
{\narrower
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}
la parenthèse suivante
{\narrower
(ces derniers seront marqués finaux si $q_2$ était final dans $A_2$)
\par}
et remplacer la phrase (page 32, lignes 15–18)
{\narrower
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}
par
{\narrower
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$.
\par}
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.
\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill}
\medskip
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) :
{\narrower
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.
\par}
\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill}
\medskip
Paragraphe 2.1.7, l'expression rationnelle donnée entre parenthèses
comporte une faute de frappe : page 18, ligne 9 en partant du bas,
remplacer $(b|c){*}a(b|c){*}b(a|b|c){*}$ par
$(b|c){*}a(a|c){*}b(a|b|c){*}$.
\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill}
\medskip
Paragraphe 4.3.2, la grammaire ne devrait pas avoir de
production $\varepsilon$ compte tenu de ce qui en est dit
en-dessous : page 56, ligne 18, remplacer $S \rightarrow U \;|\; V
\;|\; \varepsilon$ par $S \rightarrow U \;|\; V$.
\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill}
\medskip
Paragraphe 4.3.5, il manque à la grammaire $G'$ des productions $U
\rightarrow \varepsilon$ et $V \rightarrow \varepsilon$ : page 58,
lignes 4–5, remplacer
\[
\begin{aligned}
U &\rightarrow aUbU\\
V &\rightarrow bVaV\\
\end{aligned}
\]
par
\[
\begin{aligned}
U &\rightarrow aUbU \;|\; \varepsilon\\
V &\rightarrow bVaV \;|\; \varepsilon\\
\end{aligned}
\]
%
%
%
\end{document}
|
