Ecole Nationale d'Ingénieurs de Tunis A.U.
2023/2024
Département TIC
1ère INFO.
Théorie des langages et des automates
Série 1
1. Soit l'alphabet Σ = {0, 1}. Donnez tous les mots de longueur 3 construit à partir de Σ.
Combien il y a t'il de mots de longueur n sur Σ?
2. Soit L le langage contenant tous les mots de longueur impaire de {a, b, c}∗ . Pour chaque
langage de la colonne de gauche, trouver un langage de la colonne de droite qui lui est
identique.
a. L ∪ ∅ 1. L
b. L ∪ {} 2. {}
c. L.∅ 3. ∅
d. L.{} 4. {a, b, c}∗
e. L∗ 5. aucun de ceux qui précèdent
3. Soit ω = ω1 . . . ωn un mot quelconque sur un alphabet Σ. Une période de ω est un entier
p, 1 ≤ p ≤ |ω| tel que ωi = ωi+p pour tout p, 1 ≤ i ≤ |ω| − p. On note P (ω) l'ensemble
des périodes de ω .
Déterminez P (ω) pour chacun des mots ω suivants : 00000, 010101, 01001010010.
Proposez un langage in ni sur Σ = {0, 1} dont chacun des mots n'admet qu'une seule
période.
4. Soit L un langage sur un alphabet Σ donné. Dans ce qui suit, ω désigne un mot, L∗
désigne la fermeture itérative de L, Ln désigne L.L
| {z. . . L}, et LR désigne le langage des
n fois
mots inversés de L. Déterminer si chacun des énoncés suivants est valide (toujours vrai)
ou pas.
(a) ∈ L∗
(b) L.Σ∗ = Σ∗
(c) L ⊆ L.L
(d) (L∗ )∗ = L∗
(e) L∗ .L = L∗
(f ) |Ln | = |L|n
(g) si ω ∈ L.LR alors ω est palindrome
(h) si ω ∈ L.L alors |ω| est pair
5. Soient R et S deux expressions régulières dé nies comme suit :
R = a(a ∪ b)∗ ba
S = (ab)∗ ∪ (ba)∗ ∪ a∗ ∪ b∗
1
(a) Trouver un mot inclus dans le langage dénoté par R, mais qui ne soit pas inclus dans
le langage dénoté par S.
(b) Trouver un mot inclus dans le langage dénoté par S, mais qui ne soit pas inclus dans
le langage dénoté par R.
(c) Trouver un mot inclus dans le langage dénoté par R et dans le langage dénoté par S.
(d) Trouver un mot qui ne soit inclus ni dans le langage dénoté par S, ni dans le langage
dénoté par R.
6. Soit les expressions régulières R = (0 ∪ 11)+ (01)∗ et S = 0+ ∪ (11)+ ∪ (01)∗ .
Donnez deux mots qui appartiennent à L(R).
Donnez deux mots qui appartiennent à L(S).
Donnez deux mots qui appartiennent à L(R) ∩ L(S).
Donnez deux mots qui appartiennent à L(R) \ L(S).
Donnez deux mots qui appartiennent à L(S) \ L(R).
Donnez deux mots qui appartiennent à L(S) ∪ L(R)
7. Simpli er les expressions régulières suivantes :
(a) (ε ∪ a∗ ∪ b∗ ∪ a ∪ b)∗
(b) a(a ∪ b)∗ b ∪ (ab)∗ ∪ (ba)∗
(c) (ab∗ c∗ ∪ ab∗ ∪ ac∗ )∗
(d) (abc)∗ ∪ a+ (bc)∗ ∪ a(a ∪ b ∪ c)∗ bc
(e) (a∗ b∗ c∗ )∗
8. SoitΣ = {a, b}
L1 = {ω|ω commence par a}
L2 = {mot de longueur paire}
Proposez des expressions régulières pour L1 et L2 .
9. Donner une expression régulière dénotant l'ensemble des mots sur un alphabet Σ =
{a, b, c} comportant exactement deux a, dans lesquels tout b est suivi d'un c et qui se
terminent par a.
10. Donner une expression régulière dénotant l'ensemble des mots sur un alphabet Σ =
{a, b, c} comportant au moins deux a, dans lesquels tout b est suivi d'un a et qui se
terminent par ac.
11. Soient u, v, x et y ∈ Σ∗ . Montrez que uv = xy si et seulement si l'un des trois cas suivants
est véri é :
(a) |u| = |x|, u = x et v=y
(b) |u| < |x| et il existe t ∈ Σ∗ tel que ut = x et v = ty
(c) |u| > |x| et il existe t ∈ Σ∗ tel que u = xt et tv = y
12. Soient u, v ∈ Σ∗ . Montrez que uv = vu si et seulement s'il existe ω ∈ Σ∗ et m, n ∈ N tels
que u = ω m et v = ω n .
