Errata de la première édition
Merci à Jean-Paul Allouche, Anne Bouillard, Thomas Capricelli, Stéphane
Caron, Christian Delhommé, Isabelle Fagnot, Arthur Milchior, Yves Mocquard
et Marc Zeitoun.
Pour chaque erreur est indiqué le numéro de la page et le numéro de
ligne. Les lignes sont comptées à partir du bas de la page quand le nombre
est négatif. Toutes les lignes y compris celles des formules et des titres
sont prises en compte.
- p. 9 l. -1 : contrairement à ce qui est indiqué, la couverture du
livre n'est pas de Michèle.
Premier chapitre : langages rationnels
- p. 17 l. 22 : changer Par contre, gn n'admet
pas Fn ∧ Fn+2 = 1 pour période si n ≥ 4
en Par contre, gn+2 n'admet pas Fn ∧
Fn+1 = 1 pour période si n ≥ 2
- p. 19 l. -9 : changer q < u' en
q < |u'|
- p. 20 l. 23 : changer si x'y'2 n'est pas un
préfixe de xy2 en si x'y'2 est un
préfixe de xy2
- p. 22 l. 2 : changer s'il ne contient pas de facteur
qui ne soit un chevauchement en aucun de ses facteurs n'est
un chevauchement
- p. 26 l. -7 : changer v = uu' pour un certain mot v' en
v = uu' pour un certain mot u'
- p. 28 l. -21 : changer Soir en Soit
- p. 28 l. -13 : supprimer la phrase Si uv = vu
alors u et v sont puissance d'un même mot.
- p. 36 l. 14 et l.15 : changer qui est en
qui n'est
- p. 41 l. 21 : changer pas ε en
par ε
- p. 41 l. 21 : changer la relation -- a* -> en
la relation -- ε* ->
- p. 43 l. 2 : changer donne en donnent
- p. 46 l. -11 et -9 : changer q⋅a en
p⋅a
- p. 46 l. -8 : changer q⋅w en p⋅w
- p. 46 l. -6 : changer q⋅(uv) = (q⋅u)⋅v
en p⋅(uv) = (p⋅u)⋅v
- p. 53 l. 13 : changer et particulier le présentation
en et en particulier la présentation
- p. 54 l. 19 : changer K = { uu | u ∈ A* }
en K = { uu | u ∈ A+ }
- p. 54 l. 2 : changer rationnel en rationnels
- p. 58 l. 9 : changer une problème en
un problème
- p. 61 l. 12 : changer M est inclus dans M' en
M' est inclus dans M
- p. 62 l. 18 : changer π(π'((M2)) =
π(M1) = M en
π(π'(M2)) = π(M1) = M
(parenthèse ouvrante en trop)
- p. 64 l. -3 : changer vérifie en vérifient
- p. 65 l. -9 : changer et est donc en est
- p. 68 l. 7 : changer i({a}) = 1 en i({a}) = 2
- p. 68 l. 11 : changer la relation i(K + L) ≤
max(i(K),i(L)) en la relation i(KL) ≤ i(K) + i(L) + 1
- p. 71 l. 7 : changer quelque en quel que
- p. 71 l. 18 : changer invariant en invariants
- p. 71 l. 20 : dans la définition des transitions pour la
lettre b, changer q < n en q < n - 1 et q = n
en q = n - 1
Deuxième chapitre : langages algébriques
- p. 77 l. 7 : changer s'il est égal LG(S) en
s'il est à égal LG(S)
- p. 78 l. -11 : changer Lab et Lab
en Lab et Lba
- p. 78 l. -5 : changer T → Ta + Tb + ε en
T → Ta + Tb + #
- p. 83 l. -5 : changer voir qu'on l'on procède bel
est bien en voir que l'on procède bel et bien
- p. 91 Fig 2.2 : Les deux arbres de dérivation donnés pour
aaa sont erronés. Il faut ajouter une dérivation
S → a pour chaque a.
- p. 91 l. -8 : changer (cf. figure 2.2), Par contre en
(cf. figure 2.2). Par contre
- p. 92 l. -5 : changer soit α, u, β,
soit β, v, γ en soit α, u et β,
soit β, v et γ
- p. 95 l. -6 : changer sont pas en ne sont pas
- p. 106 l. 16 : changer exemple 2.8 p. 77 en
exercice 2.9 p. 78
- p. 111 l. 9, 10 et 11 : changer p, ∈ Qp,z en
p ∈ Q p,z
Troisième chapitre : calculabilité
- p. 124 l. -8 : changer tout sommets différents en
tous sommets distincts
- p. 126 l. -7 : changer tout formule en
toute formule
- p. 127 l. -15 : changer Il peu être en
Il peut être
- p. 127 l. -10 : changer problème en problèmes
- p. 128 l. 1 : changer formés en formé
- p. 128 l. 16 : changer bandes en bande
- p. 128 l. -5 : changer Turing se en Turing ne se
- p. 129 l. -2 : changer écrit en écrite
- p. 129 l. -1 : changer avec le symbole blanc en
par des symboles blancs
- p. 134 l. 18 : changer hérite beaucoup en
hérite de beaucoup
- p. 135 l. 6 : changer ajouter les transitions en
ajouter des transitions
- p. 135 l. 12 : changer chaque symbole de bande a en
chaque symbole de bande a (fonte mathématique)
- p. 138 l. 13 : changer sont identiques en
soient identiques
- p. 138 l. 16 : changer machine à une seule bande en
machine a une seule bande
- p. 140 l. -17 : changer Par contre en
En revanche,
- p. 140 l. -15 : changer que les celles en
que celles
- p. 140 l. -3 : changer Si de plus M en
Si, de plus, M
- p. 143 l. 3 : changer machines en machine
- p. 143 l. -12 : changer la bande sortie en
la bande de sortie
- p. 147 l. -14 : changer close par de en
close pour de
- p. 148 l. 1 : changer Si le problème en Le problème
- p. 148 l. -9 : changer Il suffit par exemple de en
Il suffit, par exemple, de
- p. 148 l. -7 : changer De plus on a en
De plus, on a
- p. 152 l. -8 : changer (q0w$, ε) en
(ε, q0w$)
- p. 153 l. -4,-3 et -2 : l'indice i des sommes
varie de 1 à m et non pas de 1 à n
- p. 157 l. 23 : changer M et t(M') en
M et t(M)
- p. 167 l. -10 : changer
g(f1,…,fn) en
g(f1,…,fp)
Quatrième chapitre : complexité
- p. 181 l. 8 : changer n = O(tM(n)) en
n = o(tM(n))
- p. 185 l. -10 : changer Algorithme de de Cocke, en
Algorithme de Cocke,
- p. 188 l. 10 : changer Par contre, elles inadaptées en
En revanche, elles sont inadaptées
- p. 191 l. 10 : changer se dans la case en
se trouve dans la case
- p. 191 l. 11 : changer de la configuration de la
configuration en de la configuration
- p. 195 l. 4 et 5 : changer sommet s en
sommet t
- p. 200 l. 7 : changer Le fait de prendre de choisir en
Le fait de choisir
- p. 205 l. 6 : ajouter une ligne 6: i ←
0 entre les lignes 5 et 6 de l'algorithme de calcul de m
- p. 209 l. -1 : changer complexités en
complexité
- p. 216 l. -8 : changer l'expression est l'expression en
l'expression
- p. 217 l. -13 : changer complexités en
complexité
- p. 227 l. 3 : changer p,a → q,b,R en
p,a → q,b,⊳
- p. 227 l. 4 : changer p,a → q,b,L en
p,a → q,b,⊲
- p. 228 l. -11 : changer On dit qu'une relation en
Une relation
- p. 229 l. 1 : changer
q+,a → q+,a,R en
q+,a → q+,a,⊳