Exercices sur les automates et les langages formels

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

Exercices sur les automates et les langages
formels

J. Berstel and L. Boasson

6 février 2011 11 h 39

1

2

3

4

4

6
6
8
9
9
10

11

Table des matières

1 Mots

2 Langages particuliers

3 Itération

4 Décidabilité

6 Problèmes

5 Opérations sur les langages

7 Solution

1 Mots

Index rationnel

. . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1
6.2 Langages métalinéaires . . . . . . . . . . . . . . . . . . . . . . . .
6.3 Approximants du langage de Dyck . . . . . . . . . . . . . . . . .
6.4 Centre d’un langage . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
6.5 Langages très simples

Exercice 1.1 Soient u et v deux mots non vides. Montrer que les conditions
suivantes sont équivalentes :

(i) uv = vu ;
(ii) il existe des entiers n, m ≥ 1 tels que un = vm ;
(iii) il existe des entiers k, ℓ ≥ 1 et un mot w tels que u = wk et v = wℓ.
(iv) les mots infinis uω et vω ont un préfixe commun de longeur |u| + |v|.
(v) il existe des entiers r, s ≥ 1 et des mots x1, x2, . . . , xr, y1, y2, . . . , ys, tous

égaux à u ou à v, avec x1 6= y1, tels que x1x2 · · · xr = y1y2 · · · ys.

Exercice 1.2 (Application du précédent. Soient u et v deux mots non vides.
Montrer que si ukvk = vkuk pour un entier k ≥ 2, alors uv = vu.

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

1

Exercice 1.4 Soient x, y, u, v des mots non vides.

1. Montrer que si xuy = yxu = vyx, alors u = v et ils sont tous les quatres

puissances d’un même mot.

puissances d’un même mot.

2. Montrer que si xvy = yxu = vyx, alors u = y et ils sont tous les quatres

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

w[k] = akak+1 · · · an−1a0a1 · · · 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]} . (L’ordre est l’ordre lexicographique.) Montrer que x, y sont conjugués si et seule- ment si D(x, y) 6= {0, . . . , n − 1} et D(y, x) 6= {0, . . . , n − 1}. Exercice 1.6 (“Factorisation de Catalan”) Soit D le langage de Dyck sur A = {a, b}, solution de l’équation D = ε + aDbD. Montrer que A∗ = (Db)∗D(aD)∗ . Exercice 1.7 Soient A et E deux alphabets. On dit qu’un mot e ∈ E+ apparaît dans w ∈ A∗ s’il existe un morphisme non effaçant φ de E∗ dans A∗ tel que φ(e) est facteur de w. Un mot e ∈ E+ est inévitable s’il apparaît dans tout mot assez long. Par exemple, le mot xx est inévitable sur 2 lettres, mais évitable sur trois lettres (voir exercice suivant). 1. Les mots de Zimin zn sont définis comme suit : z0 est une lettre, et zn+1 = znazn, où a est une lettre qui ne figure pas dans zn. Par exemple, z1 = aba, z2 = abacaba. Montrer que les mots de Zimin sont inévitables. 2. Démontrer que si E a n lettres, tout mot e de E∗ de longueur ≥ 2n est évitable sur un alphabet de taille assez grande. 2 Langages particuliers Exercice 2.1 Un langage L de A∗ est dit local s’il existe deux parties P, S ⊂ A et une partie N ⊂ A2 telles que L {ε} = (P A∗ ∩ A∗S) A∗N A∗ . La terminologie s’explique ainsi : pour tester si un mot appartient à L, il suffit de vérifier que sa première lettre est dans P , sa dernière lettre est dans S, et que ses facteurs de longueur 2 ne sont pas dans N . Toutes ces vérifications sont “locales". 1. Montrer, en donnant les ensembles P, S, N appropriés, que (abc)∗ est un langage local sur A = {a, b, c}. 2. Montrer qu’un langage local L sur A est reconnu par un automate fini ayant un ensemble Q d’états vérifiant Card(Q) = 1 + Card(A) et tel que {q · a | q ∈ Q} est un singleton pour tout a ∈ A. 31 32 33 34 35 36 37 38 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 2 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 3. Montrer que si L est local, alors L∗ est local. 4. Montrer que si L1 et L2 sont deux langages locaux sur A1 et A2 respec- tivement, avec A1 ∩ A2 = ∅, alors L1 ∪ L2 et L1L2 sont des langages locaux. 5. Montrer qu’un langage L sur A est local si et seulement si, pour tout a ∈ A, l’ensemble {(ua)−1L | u ∈ A∗} contient au plus un élément. 6. On appelle automate local un automate fini déterministe (mais pas nés- sairement complet) A = (Q, i, T ) sur A tel que pour toute lettre a, l’ensemble {q·a | q ∈ Q} contient au plus un élément. Montrer qu’un langage reconnaissable est local ssi il est reconnu par un automate local. 7. Montrer que pour tout langage reconnaissable X ⊂ A∗, il existe un alphabet B, un langage local K sur B et un morphisme littéral f : B∗ → A∗ tel que f (K) = X. Exercice 2.2 1. Donner un exemple d’une transduction rationnelle τ : A∗ → A∗ telle que l’ensemble {u ∈ A∗ | u ∈ τ (u)} n’est pas un langage rationnel. 2. Donner un exemple d’une transduction rationnelle τ : A∗ → A∗ telle que l’ensemble {u ∈ A∗ | τ (u) = A∗} n’est pas un langage rationnel. 3. Démontrer que pour toute transduction rationnelle τ : A∗ → A∗, l’ensem- ble {u ∈ A∗ | τ (u)infini } est un langage rationnel. 3 Itération 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} . Montrer que le langage K ∪ L vérife le lemme de l’étoile, et qu’il n’est pas rationnel. Exercice 3.2 Un langage K ⊂ A∗ est local s’il existe trois ensembles U, V ⊂ A et W ⊂ A2 tels que K ε = (U A∗ ∩ A∗V ) A∗W A∗ . Soit K un langage local. Montrer que, su xyz, xy2z ∈ K pour trois mots x, y, z, alors xy+z ⊂ K. Exercice 3.3 Soit K ⊂ A∗ un langage rationnel. Montrer qu’il existe deux entiers n, m tels que si xykz ∈ K pour un entier k ≥ n, alors xyk(ym)∗z ⊂ K. Exercice 3.4 Soit K ⊂ A∗ un langage rationnel qui vérifie la propriété suiv- ante : pour tout entier n > 0, il existe un mot dans K dont la longueur est un
multiple de n. Montrer qu’il existe dex mots non vides x, y, z tels que xy∗z ⊂ K
et |xz| = |y|.

Exercice 3.5 Soit L ⊂ A∗ un langage algébrique vérifiant la même propriété,
à savoir : pour tout entier n > 0, il existe un mot dans K dont la longueur est
un multiple de n. Montrer qu’il existe dex mots non vides x, u, y, v, z tels que
xukyvkz ∈ L pour tout k ≥ 0 et |xyz| = |uv|.

100

101

3

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

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

Exercice 3.6 Soit L un langage linéaire (engendré par une grammaire linéaire).
1. Montrer qu’il existe un entier N tel que tout mot w de L de longueur au
moins N possède une factorization w = xuyvz telle que uv 6= ε, xukyvkz ∈ L
pour k ≥ 0 et |xuvz| ≤ N .

2. Montrer que, pour L = {anbn | n > 0}, le langage L2 n’est pas linéaire.

4 Décidabilité

Exercice 4.1 Soit L un langage rationnel sur A. On se propose de montrer
qu’il est décidable s’il existe un mot w ∈ A+, et des entiers i, j distincts tels que
wi ∈ L et wj ∈ L.

1. Montrer qu’il existe un mot w ∈ A+, et des entiers i, j distincts tels que
wi ∈ L et wj ∈ L si et seulement s’il existe un mot infini uvω tel que le chemin
partant de l’état initial et d’étiquette uvω passe par au moins deux fois par un
état terminal.

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

5 Opérations sur les langages

Exercice 5.1 Le but de cet exercice est de montrer que la clôture par conju-
gaison d’un langage algébrique est encore algébrique, en utilisant le théorème
de Chomsky-Schützenberger.

Soit A un alphabet fini. Deux mots x, y sur A sont conjugués s’il existe dex
mots u, v tels que x = uv et y = vu. La relation de conjugaison est une relation
d’équivalence. Pour tout mot x, on note γ(x) l’ensemble des mots de A∗ qui
sont conjugués à x. Si L ⊂ A∗, on pose γ(L) = Sx∈L γ[x).

1. Montrer que si K est un langage rationnel local, alors γ(K) est un langage

2. Montrer que pour tout morphisme alphabetique h : A∗ → B∗ et tout

rationnel.

langage L ⊂ A∗, on a

γ(h(L)) = h(γ(L)) .

En déduire que si L est rationnel, alors γ(L) est rationnel.

3. Soient L, M deux langages sur A. Montrer que γ(L ∩ M ) ⊂ γ(L) ∩ γ(M )

et donner un exemple qui montre que l’inclusion peut être stricte.

4. Soit # un lettre qui n’est pas dans A. Montrer que γ(#L ∩ #M ) =

γ(#L) ∩ γ(#M ).

5. On rappelle que le langage de Dyck D∗ sur A ∪ ¯A, où ¯A est une copie

disjointe de A est engendré par la grammaire dont les règles sont

139

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

S → X
a∈A

aS¯aS + ε .

4

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

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

Exercice 5.2 Soit K un langage. On partage chaque mot w de K de longueur
paire en deux parties w = w0w1 de même longueur, et on pose K0 = {w0 | w ∈
K}. Si K est rationnel, alors K0 est rationnel. Si K est algébrique, alors K0
n’est pas nécessairement algébrique.

Exercice 5.3 (Suite du précédent) On fixe un entier N ≥ 2 et deux entiers
d, f , avec 0 ≤ d < f ≤ N . Soit K un langage. On partage chaque mot w de K de longueur multiple de N en N parts de longueurs égales : w = w0w1 · · · wN −1, |w0| = |w1| = · · · = |wN −1|, et on conserve le facteur “central” wP = wdwd+1 · · · wf −1. On considère le langage KP = {wP | w ∈ K}. Si K est rationnel, alors KP est rationnel. Exercice 5.4 (Suite du précédent) On fixe un entier N ≥ 2 et une partie P de {0, 1, . . . , N − 1}, soit P = {i1 < i2 < · · · < ip} Soit K un langage. On partage chaque mot w de K de longueur multiple de N en N parts de longueurs égales : w = w0w1 · · · wN −1, et on conserve le facteur wP = wi1 wi2 · · · wip . Même si K est un langage rationnel, le langage KP = {wP | w ∈ K} n’est pas nécessairement rationnel. Exercice 5.5 Soit K un langage. On pose s(K) = {w | ww ∈ K}. Si K est un langage rationnel, alors s(K) est rationnel. Si K est algébrique, s(K) n’est pas nécessairement algébrique. Exercice 5.6 Soit K un langage. On pose m(K) = {w | w w ∈ K}. Si K est e un langage rationnel, alors m(K) est rationnel. Si K est algébrique, m(K) n’est pas nécessairement algébrique. Exercice 5.7 (suite de précédent) Soit K un langage. Pour un entier n ≥ 2, on pose s(K, n) = {w | wn ∈ K}. Si K est un langage rationnel, alors s(K, n) est rationnel. Exercice 5.8 (suite de précédent) Soit K un langage. On considère le langage Rac(K) = {w | ∃n ≥ 2, wn ∈ K} Si K est un langage rationnel, alors Rac(K) est rationnel. Exercice 5.9 (suite de précédent) Soit K un langage. On considère le langage Exp(K) = {wn | n ≥ 1, w ∈ K}. Ce langage n’est pas rationnel, si K est rationnel. Exercice 5.10 Soient A = {a, b}, B = {a, b, c}. Soient n ≥ 1 un entier fixé, et u1, . . . , un, v1, . . . , vn des mots de A+. On définit les trois langages suivants : U = {baik · · · bai1cui1 · · · uik | k ≥ 1, 1 ≤ i1, . . . , ik ≤ n} V = {baik · · · bai1cvi1 · · · vik | k ≥ 1, 1 ≤ i1, . . . , ik ≤ n} X = U c V e 5