1 Exercices sur les automates et les langages

2 formels
3 J. Berstel and L. Boasson
4 6 février 2011 11 h 39

5 Table des matières

6 1 Mots 1

7 2 Langages particuliers 2

8 3 Itération 3

9 4 Décidabilité 4

10 5 Opérations sur les langages 4

11 6 Problèmes 6
12 6.1 Index rationnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
13 6.2 Langages métalinéaires . . . . . . . . . . . . . . . . . . . . . . . . 8
14 6.3 Approximants du langage de Dyck . . . . . . . . . . . . . . . . . 9
15 6.4 Centre d’un langage . . . . . . . . . . . . . . . . . . . . . . . . . 9
16 6.5 Langages très simples . . . . . . . . . . . . . . . . . . . . . . . . 10

17 7 Solution 11

18 1 Mots
19 Exercice 1.1 Soient u et v deux mots non vides. Montrer que les conditions
20 suivantes sont équivalentes :
21 (i) uv = vu ;
22 (ii) il existe des entiers n, m ≥ 1 tels que un = v m ;
23 (iii) il existe des entiers k, ℓ ≥ 1 et un mot w tels que u = wk et v = wℓ .
24 (iv) les mots infinis uω et v ω ont un préfixe commun de longeur |u| + |v|.
25 (v) il existe des entiers r, s ≥ 1 et des mots x1 , x2 , . . . , xr , y1 , y2 , . . . , ys , tous
26 égaux à u ou à v, avec x1 6= y1 , tels que x1 x2 · · · xr = y1 y2 · · · ys .

27 Exercice 1.2 (Application du précédent. Soient u et v deux mots non vides.

28 Montrer que si uk v k = v k uk pour un entier k ≥ 2, alors uv = vu.

29 Exercice 1.3 Soient x, y, z trois mots non vides. Montrer que si xy = zx et

30 yx = xz, alors y = z.

1
31 Exercice 1.4 Soient x, y, u, v des mots non vides.
32 1. Montrer que si xuy = yxu = vyx, alors u = v et ils sont tous les quatres
33 puissances d’un même mot.
34 2. Montrer que si xvy = yxu = vyx, alors u = y et ils sont tous les quatres
35 puissances d’un même mot.

36 Exercice 1.5 Deux mots x et y sont conjugués s’il exist des mots u, v tels que
37 x = uv et y = vu. Pour tout mot w = a0 a1 · · · an−1 , où a1 , a2 , . . . , an−1 sont des
38 lettres, on pose

w[k] = ak ak+1 · · · an−1 a0 a1 · · · ak−1 , (0 ≤ k < n) .

39 Ce sont les conjugués de w. Pour deux mots x, y de longueur n, on définit

D(x, y) = {k | ∃j : y [j] < x[k] } .

40 (L’ordre est l’ordre lexicographique.) Montrer que x, y sont conjugués si et seule-

41 ment si D(x, y) 6= {0, . . . , n − 1} et D(y, x) 6= {0, . . . , n − 1}.

42 Exercice 1.6 (“Factorisation de Catalan”) Soit D le langage de Dyck sur A =

43 {a, b}, solution de l’équation D = ε + aDbD. Montrer que

A∗ = (Db)∗ D(aD)∗ .

44 Exercice 1.7 Soient A et E deux alphabets. On dit qu’un mot e ∈ E + apparaît

45 dans w ∈ A∗ s’il existe un morphisme non effaçant φ de E ∗ dans A∗ tel que
46 φ(e) est facteur de w. Un mot e ∈ E + est inévitable s’il apparaît dans tout mot
47 assez long. Par exemple, le mot xx est inévitable sur 2 lettres, mais évitable sur
48 trois lettres (voir exercice suivant).
49 1. Les mots de Zimin zn sont définis comme suit : z0 est une lettre, et
50 zn+1 = zn azn , où a est une lettre qui ne figure pas dans zn . Par exemple,
51 z1 = aba, z2 = abacaba. Montrer que les mots de Zimin sont inévitables.
52 2. Démontrer que si E a n lettres, tout mot e de E ∗ de longueur ≥ 2n est
53 évitable sur un alphabet de taille assez grande.

54 2 Langages particuliers
55 Exercice 2.1 Un langage L de A∗ est dit local s’il existe deux parties P, S ⊂ A
56 et une partie N ⊂ A2 telles que

L \ {ε} = (P A∗ ∩ A∗ S) \ A∗ N A∗ .

57 La terminologie s’explique ainsi : pour tester si un mot appartient à L, il suffit

58 de vérifier que sa première lettre est dans P , sa dernière lettre est dans S, et
59 que ses facteurs de longueur 2 ne sont pas dans N . Toutes ces vérifications sont
60 “locales".
61 1. Montrer, en donnant les ensembles P, S, N appropriés, que (abc)∗ est un
62 langage local sur A = {a, b, c}.
63 2. Montrer qu’un langage local L sur A est reconnu par un automate fini
64 ayant un ensemble Q d’états vérifiant Card(Q) = 1 + Card(A) et tel que {q · a |
65 q ∈ Q} est un singleton pour tout a ∈ A.

2
 66 3. Montrer que si L est local, alors L∗ est local.
67 4. Montrer que si L1 et L2 sont deux langages locaux sur A1 et A2 respec-
68 tivement, avec A1 ∩ A2 = ∅, alors L1 ∪ L2 et L1 L2 sont des langages locaux.
69 5. Montrer qu’un langage L sur A est local si et seulement si, pour tout
70 a ∈ A, l’ensemble {(ua)−1 L | u ∈ A∗ } contient au plus un élément.
71 6. On appelle automate local un automate fini déterministe (mais pas nés-
72 sairement complet) A = (Q, i, T ) sur A tel que pour toute lettre a, l’ensemble
73 {q·a | q ∈ Q} contient au plus un élément. Montrer qu’un langage reconnaissable
74 est local ssi il est reconnu par un automate local.
75 7. Montrer que pour tout langage reconnaissable X ⊂ A∗ , il existe un
76 alphabet B, un langage local K sur B et un morphisme littéral f : B ∗ → A∗ tel
77 que f (K) = X.

78 Exercice 2.2 1. Donner un exemple d’une transduction rationnelle τ : A∗ →

79 A∗ telle que l’ensemble {u ∈ A∗ | u ∈ τ (u)} n’est pas un langage rationnel.
80 2. Donner un exemple d’une transduction rationnelle τ : A∗ → A∗ telle que
81 l’ensemble {u ∈ A∗ | τ (u) = A∗ } n’est pas un langage rationnel.
82 3. Démontrer que pour toute transduction rationnelle τ : A∗ → A∗ , l’ensem-
83 ble {u ∈ A∗ | τ (u)infini } est un langage rationnel.

84 3 Itération
85 Exercice 3.1 Soient A = {a, b, c, d} et K, L, M ⊂ A∗ définis par

M = A2 \ {ab, ba, bc, cd, dc} , K = A∗ M A∗ , L = {′ ab)n [cd)n | n ≥ 1} .

86 Montrer que le langage K ∪ L vérife le lemme de l’étoile, et qu’il n’est pas

87 rationnel.

88 Exercice 3.2 Un langage K ⊂ A∗ est local s’il existe trois ensembles U, V ⊂ A

89 et W ⊂ A2 tels que

K \ ε = (U A∗ ∩ A∗ V ) \ A∗ W A∗ .

90 Soit K un langage local. Montrer que, su xyz, xy 2 z ∈ K pour trois mots x, y, z,

91 alors xy + z ⊂ K.

92 Exercice 3.3 Soit K ⊂ A∗ un langage rationnel. Montrer qu’il existe deux

93 entiers n, m tels que si xy k z ∈ K pour un entier k ≥ n, alors xy k (y m )∗ z ⊂ K.

94 Exercice 3.4 Soit K ⊂ A∗ un langage rationnel qui vérifie la propriété suiv-

95 ante : pour tout entier n > 0, il existe un mot dans K dont la longueur est un
96 multiple de n. Montrer qu’il existe dex mots non vides x, y, z tels que xy ∗ z ⊂ K
97 et |xz| = |y|.

98 Exercice 3.5 Soit L ⊂ A∗ un langage algébrique vérifiant la même propriété,

99 à savoir : pour tout entier n > 0, il existe un mot dans K dont la longueur est
100 un multiple de n. Montrer qu’il existe dex mots non vides x, u, y, v, z tels que
101 xuk yv k z ∈ L pour tout k ≥ 0 et |xyz| = |uv|.

3
102 Note Les deux derniers exercices sont de (Kobayashi, 1969, Lemme 1, page
103 104).

104 Exercice 3.6 Soit L un langage linéaire (engendré par une grammaire linéaire).
105 1. Montrer qu’il existe un entier N tel que tout mot w de L de longueur au
106 moins N possède une factorization w = xuyvz telle que uv 6= ε, xuk yv k z ∈ L
107 pour k ≥ 0 et |xuvz| ≤ N .
108 2. Montrer que, pour L = {an bn | n > 0}, le langage L2 n’est pas linéaire.

109 4 Décidabilité
110 Exercice 4.1 Soit L un langage rationnel sur A. On se propose de montrer
111 qu’il est décidable s’il existe un mot w ∈ A+ , et des entiers i, j distincts tels que
112 wi ∈ L et wj ∈ L.
113 1. Montrer qu’il existe un mot w ∈ A+ , et des entiers i, j distincts tels que
114 w ∈ L et wj ∈ L si et seulement s’il existe un mot infini uv ω tel que le chemin
i

115 partant de l’état initial et d’étiquette uv ω passe par au moins deux fois par un
116 état terminal.
117 2. Montrer que le chemin partant de l’état initial et d’étiquette uv ω est
118 lui-même ultimement périodique, et qu’il est décidable s’il passe au moins deux
119 fois par un état terminal. Conclure.

120 5 Opérations sur les langages

121 Exercice 5.1 Le but de cet exercice est de montrer que la clôture par conju-
122 gaison d’un langage algébrique est encore algébrique, en utilisant le théorème
123 de Chomsky-Schützenberger.
124 Soit A un alphabet fini. Deux mots x, y sur A sont conjugués s’il existe dex
125 mots u, v tels que x = uv et y = vu. La relation de conjugaison est une relation
126 d’équivalence. Pour tout mot x, on note γ(x) S l’ensemble des mots de A∗ qui
127 sont conjugués à x. Si L ⊂ A , on pose γ(L) = x∈L γ[x).
∗

128 1. Montrer que si K est un langage rationnel local, alors γ(K) est un langage
129 rationnel.
130 2. Montrer que pour tout morphisme alphabetique h : A∗ → B ∗ et tout
131 langage L ⊂ A∗ , on a
γ(h(L)) = h(γ(L)) .
132 En déduire que si L est rationnel, alors γ(L) est rationnel.
133 3. Soient L, M deux langages sur A. Montrer que γ(L ∩ M ) ⊂ γ(L) ∩ γ(M )
134 et donner un exemple qui montre que l’inclusion peut être stricte.
135 4. Soit # un lettre qui n’est pas dans A. Montrer que γ(#L ∩ #M ) =
136 γ(#L) ∩ γ(#M ).
137 5. On rappelle que le langage de Dyck D∗ sur A ∪ Ā, où Ā est une copie
138 disjointe de A est engendré par la grammaire dont les règles sont
X
S→ aSāS + ε .
a∈A

139 Donner une description de γ(#D∗ ). Montre que c’est un langage algébrique.

4
140 6. Le théorème Chomsky-Schützenberger s’énonce comme suit. L est algé-
141 brique si est seulement si il est l’image, par un morphisme alphabétique, d’un
142 langage de Dyck et d’un langage rationnel. Déduire de ce qui précède que si L
143 est algébrique, alors γ(L) l’est aussi.

144 Exercice 5.2 Soit K un langage. On partage chaque mot w de K de longueur

145 paire en deux parties w = w0 w1 de même longueur, et on pose K0 = {w0 | w ∈
146 K}. Si K est rationnel, alors K0 est rationnel. Si K est algébrique, alors K0
147 n’est pas nécessairement algébrique.

148 Exercice 5.3 (Suite du précédent) On fixe un entier N ≥ 2 et deux entiers

149 d, f , avec 0 ≤ d < f ≤ N . Soit K un langage. On partage chaque mot
150 w de K de longueur multiple de N en N parts de longueurs égales : w =
151 w0 w1 · · · wN −1 , |w0 | = |w1 | = · · · = |wN −1 |, et on conserve le facteur “central”
152 wP = wd wd+1 · · · wf −1 . On considère le langage KP = {wP | w ∈ K}. Si K est
153 rationnel, alors KP est rationnel.

154 Exercice 5.4 (Suite du précédent) On fixe un entier N ≥ 2 et une partie P

155 de {0, 1, . . . , N − 1}, soit P = {i1 < i2 < · · · < ip } Soit K un langage. On
156 partage chaque mot w de K de longueur multiple de N en N parts de longueurs
157 égales : w = w0 w1 · · · wN −1 , et on conserve le facteur wP = wi1 wi2 · · · wip .
158 Même si K est un langage rationnel, le langage KP = {wP | w ∈ K} n’est pas
159 nécessairement rationnel.

160 Exercice 5.5 Soit K un langage. On pose s(K) = {w | ww ∈ K}. Si K est un

161 langage rationnel, alors s(K) est rationnel. Si K est algébrique, s(K) n’est pas
162 nécessairement algébrique.

163 Exercice 5.6 Soit K un langage. On pose m(K) = {w | ww e ∈ K}. Si K est

164 un langage rationnel, alors m(K) est rationnel. Si K est algébrique, m(K) n’est
165 pas nécessairement algébrique.

166 Exercice 5.7 (suite de précédent) Soit K un langage. Pour un entier n ≥ 2,

167 on pose s(K, n) = {w | wn ∈ K}. Si K est un langage rationnel, alors s(K, n)
168 est rationnel.

169 Exercice 5.8 (suite de précédent) Soit K un langage. On considère le langage

170 Rac(K) = {w | ∃n ≥ 2, wn ∈ K} Si K est un langage rationnel, alors Rac(K)
171 est rationnel.

172 Exercice 5.9 (suite de précédent) Soit K un langage. On considère le langage

173 Exp(K) = {wn | n ≥ 1, w ∈ K}. Ce langage n’est pas rationnel, si K est
174 rationnel.

175 Exercice 5.10 Soient A = {a, b}, B = {a, b, c}. Soient n ≥ 1 un entier fixé, et
176 u1 , . . . , un , v1 , . . . , vn des mots de A+ . On définit les trois langages suivants :

U = {baik · · · bai1 cui1 · · · uik | k ≥ 1, 1 ≤ i1 , . . . , ik ≤ n}

V = {baik · · · bai1 cvi1 · · · vik | k ≥ 1, 1 ≤ i1 , . . . , ik ≤ n}
X = U cVe

5
177 (On rappelle que pour w = a1 · · · an , on a w e = {w
e = an · · · a1 , et que K e|w∈
178 K}.) Par ailleurs, on pose

M = {xcyce x | x, y ∈ A∗ },
yce K =X ∩M.

179

180 1. Prouver que U , V et M sont des langages algébriques.

181 2. Montrer que K est vide ou infini.
182 3. Montrer que K ne contient pas de langage algébrique infini.
183 4. Montrer que B ∗ \ K est algébrique.

184 Exercice 5.11 Soit G la grammaire dont les règles sont

S → 11 | 1001 | S0 | SS .

185

186 1. Montrer que tout mot engendré par G est la représentation en base 2
187 d’un entier multiple de 3.
188 2. Montrer que G n’engendre pas tous les multiples de 3 en base 2.
189 3. Donne une grammaire que engendre toutes les représentations des mul-
190 tiples de 3 en base 2.

191 Exercice 5.12 On cherche à construire un langage algébrique dont le complé-

192 mentaire a n1/3 mots de longeur n.
On considère le langage

K = {an #ap bq | p + q = n, n, p, q ∈ N}

193 Ce langage a exactement n + 1 mots de longueur 2n + 1. Ainsi, pour n = 2,

194 il contient les mots aa#aa, aa#ab et aa#bb. On laisse les b inchangés, et on
195 substitue au i-ième a du préfixe an le mot ui aba2 b · · · ai bc. Ainsi, aaaa#abbb de-
196 vient abcaba2 bcaba2 ba3 bcaba2 ba3 ba4 bc#abbb. Le langage L cherché est le langage
197 obtenu en faisant les substitutions dans les mots de K.
198 Le mot ui est de longueur ki = 1 + i + (1 + 2 + · · · + i) = (1 + i)(2 + i)/2.
199 Le mot obtenu à partir de an #ap bq a longueur k1 + · · · kn + n + 1, et ce nombre
200 est clairement en n3 . Ainsi, L a environ n mots de longueur n3 .
201 Prouver que le complémentaire de L est algébrique.

202 6 Problèmes
203 6.1 Index rationnel
204 On note Ratn (A∗ ) l’ensemble des langages rationnels sur A reconnus par un
205 automate fini (nondéterministe) à n états. Par ailleurs, on pose, pour L ⊂ A∗ ,
206 L 6= ∅,
kLk = min{|w| : w ∈ L} , µ(L){w ∈ L : |w| = kLk} ,
207 et k∅k = 0, µ(∅) = ∅. Ainsi, µ(L) est l’ensemble des mots de L de longueur
208 minimale. Pour M ⊂ A∗ , on définit

gM (n) = max{kM ∩ Kk : K ∈ Ratn (A∗ )} .

6
209 Question 1. Soit L ⊂ A∗ . Montrer que pour n ≤ m, on a gL (n) ≤ gL (m).
210 Question 2. On considère, sur l’alphabet A = {a, b}, le langage X = a∗ b, et
211 pour n ≥ 1, le langages Kn = (an−1 b)∗ .
212 a) Vérifier que n = kX ∩ Kn k et 2n = kX 2 ∩ Kn k. En déduire que gX (n) ≥ n
213 et gX 2 ≥ 2n.
214 b) Prouver que gX (n) ≤ n.
215 Question 3. Vérifier que pour L, M ⊂ A∗ , on a gL∪M (n) = max(gL (n), gM (n)).
216 Question 4. Démontrer que pour L, M ⊂ A∗ , on a gLM (n) = gL (n) + gM (n).
217 En déduire que pour X = X = a∗ b, on a gX 2 (n) = 2n.
218 Question 5. Démontrer que pour X ⊂ A∗ , on a gX + (n) ≤ n · gX (n).
219 Question 6. Soit K ⊂ A∗ un langage rationnel, et L ⊂ A. Démontrer qu’il
220 existe un entier p tel que gL∩K (n) ≤ gL (pn) pour tout n.
221 Question 7. Soit φ : A∗ → B ∗ un morphisme alphabétique (φ(A) ⊂ B ∪ ε).
222 Soient L ⊂ A∗ et M ⊂ B ∗ . Démontrer que gφ(L) (n) ≤ gL (n) et gφ−1 (M) (n) ≤
223 n · gM (n).
224 Question 8. Soit τ : A∗ → B ∗ une transduction rationnelle, soit L ⊂ A∗ et
225 posons M = τ (L). Déduire des questions précédentes un majoration de gM au
226 moyen de gL .
227 On considère l’alphabet A = {a, b, c} et la grammaire G dont les règles sont

S → aSSc, S → b.

228 Soit E le langage engenré par cette grammaire.

229 Question 9. Montrer que w ∈ E si et seulement si w = b ou il existe u, v ∈ E
230 tels que w = auvc.
231 Question 10. Montrer que E est préfixe. (On rappelle qu’un ensemble X est
232 préfixe si aucun mot de X n’est préfixe d’un autre mot de X.)
233 On pose K0 = b∗ et on définit, pour n ≥ 1, Kn comme le langage reconnu par
234 l’automate An représenté par la figure suivante.

a a a
An : 0 1 2 ··· n−1 n b
c c c
235

236 Question 11. Montrer que Kn = (aKn−1 c)∗ pour n ≥ 1.

237 On définit une suite de mots (wn ) par w0 = b et wn = awn−1 wn−1 c pour n ≥ 1.
238 Question 12. Montrer que, pour n ≥ 0, on a wn ∈ Kn ∩ E.
239 On définit, pour i, j ≤ n les langages Li,j i,j
n par : w ∈ Ln si et seulement si w est
240 l’étiquette d’un chemin de i à j dans l’automat An .
241 Question 13. Montrer que pour i 6= j, on a Li,j i,i
n ∩ E = ∅, et que w ∈ Ln ∩ E
242 implique w ∈ Kn−i ∩ E.
243 Question 14. En déduire que E ∩ Kn = {wn }.
244 Question 15. Déduire de ce qui précède que gE (n) ≥ 3 2n − 2.
245 On considère le langage P = {an bn | n ≥ 1}. Pour n ≥ 1, soit Rn le langage
246 rationnel reconnu par l’automate suivant.

7
 b t1 b a s1 a

t2 s0 s2

b a

··· b a ···
247 tn sn−1 a
b
248 Question 16. Vérifier que µ(P ∩ Rn ) = {an(n+1) bn(n+1) }.
249 Question 17. En déduire que gP (n) > n2 /2.
250 Question 18. En calculant une grammaire pour P ∩ R, avec R ∈ Ratn (A∗ ),
251 montrer que gP (n) ≤ 2n2 .
252 Question 19. (difficile) Montrer que pour tout langage algébrique L, il existe
2
253 α > 0 tel que gL (n) ≤ 2αn .

254 Note La fonction gL est l’index rationnel du langage L. L’index rationnel a été
255 défini et étudié dans Boasson et al. (1981).

256 6.2 Langages métalinéaires

257 Une grammaire G = (V, P, S) sur A est dite métalinéaire si elle vérifie les
258 conditions suivantes :
259 – l’axiome S ne figure dans aucun membre droit de règle ;
260 – les seules règles non linéaires ont S pour membre gauche.
261 Un langage algébrique est métalinéaire s’il existe une grammaire métalinéaire
262 qui l’engendre. On désigne par Mlin la famille des langages métalinéaires.
263 Question 1. Montrer que la famille des langages linéaires est strictement in-
264 cluse dans Mlin.
265 Question 2. Montrer que Mlin est fermé par union et produit.
266 Question 3.
267 a) Montrer que Mlin est fermé pzr intersection rationnelle et par morphisme.
268 b) Montrer que Mlin est fermé par morphisme alphabétique inverse.
269 c) En déduire que Mlin est un cône rationnel.
270 On désigne par Link la fermeture par union de (Lin)k .
271 Question 4.
272 a) Montrer que Link est un cône rationnel principal.
273 b) Montrer que [
Mlin = Link .
k≥1

274 Question 5. Soit D le langage {an bn | n ≥ 1}.

275 a) Montrer que Dk ∈ Link et Dk ∈ / Link−1 .
276 b) Montrer que D∗ ∈/ Mlin. En déduire que Mlin n’est pas fermé par étoile.

8
277 6.3 Approximants du langage de Dyck
278 Soit A un alphabet fixe. Pour deux parties X, Y de A∗ , on pose

v(X, Y ) = min{|w| | w ∈ (X \ Y ) ∪ (Y \ X)} .

Par convention, v(X, X) = +∞. On défini la distance d(X, Y ) par

d(X, Y ) = 2−v(X,Y )

279 Question 1. Vérifier que d est une distance ultramétrique, c’est-à-dire que :
280 (1) d(X, Y ) = 0 si et seulement si X = Y ;
281 (2) d(X, Y ) ≤ max(d(X, Z), d(Z, Y )) pour tous X, Y, Z ⊂ A∗ .
282 Étant donné une suite (Xn )n≥0 de parties de A∗ , on écrira limn→∞ Xn = X
283 lorsque limn→∞ d(Xn , X) = 0.
284 Question 2. Soit L ⊂ A∗ . Pour tout entier p ≥ 1, soit Rp l’union des langages
285 rationnels contenus dans L et dont l’automate minimal a au plus p états.
286 a) Montrer que Rp est un langage rationnel.
287 b) Montrer que limp→∞ Rp = L.
288 c) Pour tout langage rationnel R ⊂ L, il existe un entier p tel que R ⊂ Rp .
289 Soit maintenant A = {a, b} et soit D le langage de Dyck sur A, défini comme
290 suit : w ∈ D si et seulement si |w|a = |w|b et |w′ |a ≥ |w′ |b pour tout préfixe w′
291 de w.
292 On appelle hauteur d’un mot w le nombre h(w) = max{|w′ |a − |w′ |b :
293 w préfixe de w}. Pour L ⊂ A∗ , on pose h(L) = max{h(w) | w ∈ L}.
′

294 Question 3. Soit R un langage rationnel contenu dans D, et soit k le nombre

295 d’états de l’automate minimal complet reconnaissant R. Montrer que si k ≥ 2,
296 alors h(R) ≤ k − 2.
297 Pour p ≥ 2, on pose Qp = {w ∈ D | h(w) ≤ p − 2}.
298 Question 4. Construire un automate reconnaissant Qp /
299 Question 5. Montrer que Q2 = {e} et Qp+1 = aQp bQp ∪ {e} pour p ≥ 2.
300 Question 6. a) Montrer que, pour tout X ⊂ A∗ , l’application fX de l’ensemble
301 des parties de A∗ dans lui-même qui à Y associe fX (Y ) = XY est continue.
302 b) Montrer que limp→∞ Qp = D, et en déduire que le langage D vérifie
303 l’équation D = aDbD ∪ {e}.

304 6.4 Centre d’un langage

305 Soit A un alphabet fini. On écrit x ≤ y lorsque x est préfixe de y, et on note
306 P (X) l’ensemble des préfixes des mots d’un ensemble X.
307 Soit L ⊂ A∗ . On appelle centre de L, et on note c(L), l’ensemble des mots
308 infiniment prolongeables de L, c’est-à-dire :

c(L) = {w ∈ A∗ | ∀n ∈ N, ∃x ∈ L, |x| ≥ n, w ≤ x}

309 En d’autre termes, w ∈ c(L) si et seulement si wA∗ ∩ L est infini.

310 Question 1. a) Calculer c(a∗ ), c(a∗ b), c({an bn | n ≥ 0}).
311 b) Montrer que c(L1 ∪ L2 ) = c(L1 ) ∪ c(L2 ) et que c(L) ⊂ P (L).
312 c) Montrer que P (c(L)) = c(L).

9
313 d) Montrer que c(L) est infini si et seulement L est infini.
314 Question 2. a) Montrer que pour tout w ∈ c(L), il exist a ∈ A tel que
315 wa ∈ C(L).
316 b) Montrer que c(c(L)) = c(L).
317 Question 3. Montrer que si h : A∗ → B ∗ est un morphisme littéral (c’est-à-dire
318 vérifiant h(A) ⊂ B), alors h(c(L)) = c(h(L)).
319 Soit R un langage local de la forme R = DA∗ ∩ A∗ F \ A∗ T A∗ , ave D, F ⊂ A et
320 T ⊂ A2 .
321 Question 4. OnSpose B0 = F et Bi+1 = Bi ∪ {a ∈ A | ∃b ∈ Bi : ab ∈ / T }.
322 Soient enfin B = i≥0 Bi , D′ = D ∩ B, T ′ = T ∩ B 2 .
323 a) Montrer que B est effectivement calculable.
324 b) Montrer que P (R) = D′ B ∗ \ A∗ T A∗ = D′ B ∗ \ B ∗ T ′ B ∗ .
325 Question 5. Soit Z0 = {b ∈ B | ∃x ∈ B ∗ : bxb ∈ B ∗ \ B ∗ T ′ B ∗ }. Montrer que
326 l’on peut calculer Z0 effectivement.
327 Question 6. Montrer que tout mot w ∈ B ∗ \ B ∗ T ′ B ∗ de la forme w = axb,
328 avec a ∈ D′ , x ∈ B ∗ et b ∈ Z0 , on a w ∈ C(R).
S
329 On pose Zi+1 = Zi ∪ {a ∈ B | ∃b ∈ Bi : ab ∈ / T }, et soient Z = i≥0 Zi .
330 Question 7. Montrer que Z est effectivement calculable.
331 Question 8. Déduire des questions précédentes que le centre d’un langage
332 rationnel est encore un langage rationnel.

333 Question 9. Soit L un langage algébrique engendré par une grammaire G.

334 Donner une construction qui permet d’obtenir, à partir de G, une grammaire
335 engendrant P (L). En déduire que le centre d’un langage algébrique est un lan-
336 gage algébrique.

337 6.5 Langages très simples

338 Une grammaire G = (V, S, P ) sur A est très simple si elle vérifie les deux
339 conditions suivantes :
340 (i) Pour toute règle X → α, on a α ∈ AV ∗ ;
341 (ii) Pour tout lettre a ∈ A, il existe exactement une règle dont le membre
342 droit commence par a.
343 Question 1. Quelles sont les grammaires très simples parmi les grammaires
344 suivantes :
345 – S → aSS | b ;
346 – S → aSbS | aSb | abS | ab ;
347 – S → aST SU | d; T → b; U → c.
348 Question 2. Montrer qu’une grammaire très simple est inambiguë.
349 On considère désormais une grammaire très simple fixée G = (V, S, P ) sur A.
∗
350 Question 3. Soient α ∈ V ∗ , u, v ∈ A∗ tels que α → uv. Montrer qu’il un mot
351 β ∈ V ∗ unique tel que
∗ ∗
α → uβ et β → v .

352 Question 4. Soient α, β, β ′ ∈ V ∗ et u ∈ A∗ . Montrer l’implication

∗ ∗
α → uβ, α → uβ ′ =⇒ β = β ′ .

10
353 Question 5. En déduire que pour tout α, le langage LG (α) est préfixe (c’est-
354 à-dire vérifie u, uv ∈ LG (α) =⇒ v = ε).
355 Question 6. Soient α, β ∈ V ∗ et u ∈ A∗ . Montrer que
∗ ∗
α → u, β → u =⇒ α = β .

356 On suppose désormais que LG (X) n’est pas vide pour toute variable X, et
∗
357 qu’il existe une dérivation S → uXv pour des mots u, v (toute variable est
358 “accessible"). On dit que G a un facteur itérant s’il existe α ∈ V + , u ∈ A+ tels
+
359 que α → uα.
360 Question 7. Montrer que si G est sans facteur itérant, alors LG (α) est suffixe
361 pour tout α ∈ V ∗ .
362 Question 8. Montrer réciproquement que si LG (α) est suffixe pour tout α ∈
363 V ∗ , alors G est sans facteur itérant.
364 Question 9. Montrer que G est sans facteur itérant si et seulement si LG (S)
365 ne contient pas de langage rationnel infini.

366 7 Solution
367 2.2 On considère la transduction τ qui à an bp associe a+ bn . On a aq bn ∈ τ (aq bn )
368 si et seulement si q = n.
369 On considère ensuite la relation rationnelle S = {(u, v) | u 6= v} ∪ T , où T
370 est la relation associée à τ . On a σ(u) = A∗ si et seulement si u = an bn (le tout
371 modulo a∗ b∗ ).
372 Pour la dernière question, on ne conserve, dans le transducteur associé, que
373 les chemins dont l’étiquette de sortie contient le mot vide sur un circuit.

374 3.4 Soit Q le nombre d’états de l’automate, soit w ∈ K avec |w| ≡ 0 mod Q!,
375 et soit w = xyz, q = |y| ≤ Q, avec xy ∗ z ⊂ K, et soit k tel |w| = kQ!. On a

|xy j y n z| = kQ! + (j + n − 1)q ,

376 donc |xy j z| = |y n | si et seulement si kQ! + jq − q = nq, donc si et seulement si

377 kQ! = (n − j + 1)q. On pose T = kQ!/q. C’est un entier. Soient n, j des entiers
378 positifs tels que T = n − j + 1. Posons enfin

X = xy j , Z = z , Y = y n .

379 Alors |XZ| = |xy j z| = |y n | = |Y |, et évidemment XY ∗ Z ⊂ K.

380 5.2 On note λ le morphisme littéral qui envoie toutes les lettres sur une même
381 lettre. Soient X, Y deux parties de A∗ . Alors H(X, Y ) = λ−1 (λ(X) ∩ λ(Y )) est
382 l’ensemble des mots w de A∗ tels qu’il existe des mots x ∈ X et y ∈ Y avec
383 |w| = |x| = |y|. Si X, Y sont rationnel, et plus généralement si λ(X) et λ(Y )
384 sont rationnels, alors H(X, Y ) est rationnel. En particulier, X ∩ H(X, Y ) est
385 l’ensemble des mots x ∈ X tels qu’il existe y ∈ Y avec |x| = |y|.

11
 Soit maintenant A = (Q, I, T ) un automate fini reconnaissant K. On pose
w
p Kq = {w ∈ A | p → q}. Pour tout i ∈ I, t ∈ T , on pose
∗

[
i Pt = i Kq ∩ H(i Kq , q Kt )
q∈Q
S
386 On a K0 = i∈I,t∈T i Pt . D’où le résultat.
Pour la deuxième partie, considérons le langage

L = {an bn cp−1 c̄d3p | n, p > 0}

387 et l’ensemble L0 ∩ a∗ b∗ c∗ c̄. Comme 2n + p = 3p si un mot est dans cet ensemble,

388 on a L0 ∩ a∗ b∗ c∗ c̄ = {an bn cn−1 c̄}.

5.3 On pose

H(X0 , X1 , . . . , XN −1 ) = λ−1 (λ(X0 ) ∩ λ(X0 ) ∩ · · · ∩ λ(XN −1 ))

et, pour une suite q = (q0 , q1 , . . . , qN −1 , qN ) d’états, et un entier n avec 0 ≤ n <

N
R(n, q) = (qn Kqn+1 ∩ H(q0 Kq1 , q1 Kq2 , . . . qN −1 qKqN ))
Un mot x est dans R(n, q) si et seulement s’il existe des mots x0 , . . . , xn−1 , et
xn+1 , . . . , xN −1 , tous de la même longueur que x, de sorte que xj ∈ qj Kqj+1 et
x ∈ qn Kqn+1 . Soit
[
i Pt = (R(d, q) ∩ R(d + 1, q) ∩ · · · ∩ R(f − 1, q))
q

389 où l’union est sur toutes les suites q = (q0 , q1 , . . . qN −1 , qN ) telles que q0 = i et
390 qN = t. S
391 Alors KP = i∈I,t∈T i Pt . D’où le résultat.

392 5.4 On considère le langage K = a+ āb+ c̄c+ , et N = 3, P = {0, 2}. KP est

393 donc obtenu en supprimant, dans chaque mot de longueur multiple de 3 de
394 K, le tiers du milieux et en concaténant la partie gauche avec la partie droite.
395 Soit L = KP ∩ a+ āc̄c+ . Comme les lettres barrées sont consécutives, et que ā
396 termine les a, et c̄ précède les c, ce sont exactement les b qui ont été supprimés.
397 Soit n les nombre de b supprimés. Alors le mot d’origine est an−1 ābn c̄cn−1 et
398 L = {an āc̄cn | n ≥ 0}.

5.5 On considère un automate fini A = (Q, I, T ) reconnaissant K. On pose

w
p Kq = {w ∈ A | p → q}, pour p, q ∈ Q. On a
∗

[ [
s(K) = (i Kq ∩ q Kt ) .
i∈I,t∈T q∈Q

399 Par ailleurs, considérons le langage algébrique L = {an bp cq ap br cn } Un mot dans

400 s(L)∩a+ b+ c+ doit vérifier n = p, q = n, donc s(L)∩a+ b+ c+ = {an bn cn | n > 0}.

5.6 On a [ [
m(K) = (i Kq ∩ (q Kt )∼ ) .
i∈I,t∈T q∈Q

12
401 Par ailleurs, le langage L = {an bp cq cp bn ar } fait l’affaire.

5.7 On a
[ [
s(K) = (i Kq1 ∩ q1 Kq2 ∩ · · · ∩ qn−1 Kt ) .
i∈I,t∈T q1 ,...,qn−1 ∈Q

S
402 5.8 SOn a Rac(K) =S n≥2 s(K, n). Si K est rationnel, il existe un entier N tel
403 que n≥2 s(K, n) = 2≤n≤N s(K, n).

404 5.9 Il suffit de considérer par exemple K = a+ b.

405 Références
406 Luc Boasson, Bruno Courcelle, and Maurice Nivat. The rational index : A
407 complexity measure for languages. SIAM J. Comput., 10(2) :284–296, 1981.
408 Kojiro Kobayashi. Classification of formal languages by functional binary trans-
409 ductions. Information and Control, 15(1) :95–109, 1969.

13