Université Hassan II Casablanca
Faculté des Sciences et Techniques Mohammedia
Département de Mathématiques
GMI 3ème année
2024/2025
Mathématiques Discrètes
Langages rationnels et automates finis
Dans cette partie, nous définissons les langages rationnels, les automates finis(déterministes
et non déterministes). Nous introduisons les opérations de base sur les automates : produit,
déterminisation, minimisation et complétion ; nous concluons par la preuve du théorème de
Kleene, c’est-à-dire que les langages rationnels et langages reconnaissables par automates finis
forment une seule et même famille de langages.
1. Le monoïde libre
Exercice 1 Les objets suivants sont-ils des monoïdes ?
1) L’ensemble des applications E −→ E, avec l’opération de composition.
2) L’ensemble N, avec l’opération "puissance" : (x, y) 7→ xy .
3) L’ensemble des mots de A∗ de longueur paire.
4) L’ensemble des mots de A∗ où le nombre d’occurrences de a est égal à celui de b.
5) L’ensemble des parties finies de E avec l’opération de réunion.
6) L’ensemble des parties finies de E avec l’opération d’intersection.
Exercice 2 Soit les matrices
1 1 1 0
A= et B =
0 1 1 1
1 0
On considère l’ensemble M1 formé de la matrice identité I = et des matrices obtenues
0 1
en faisant des produits des matrices A et B ; on considère aussi l’ensemble M2 des matrices
2 × 2 de déterminant +1 dont les coefficients sont des entiers positifs ou nuls.
1) Montrer que les matrices de M1 sont toutes de déterminant +1 et que toutes sont
à coefficients entiers positifs ou nuls, en procédant par récurrence sur le nombre de
matrices A et B dont elles sont le produit.
Ceci implique que M1 ⊆ M2 ; nous allons maintenant montrer l’inclusion inverse.
2) Montrer qu’une matrice à coefficients entiers positifs ou nuls, qui n’est pas la matrice
identité, est de déterminant +1 seulement si les coefficients de l’une de ses colonnes
sont
simultanément
plus grands que les coefficients de l’autre colonne. Plus précisément,
x y
(x, y, z, t ∈ N) est de déterminant +1 seulement si, soit x ≥ y et z ≥ t, soit
z t
x ≤ y et z ≤ t.
3) Calculer les inverses desmatrices
A et B. Utiliser le résultat de la question 2) pour mon-
x y
trer que toute matrice dans M2 s’écrit d’une manière unique comme produit
z t
de matrices A et B (utiliser le principe d’induction complète en faisant une récurrence
sur x + y + z + t).
1
Université Hassan II Casablanca
Faculté des Sciences et Techniques Mohammedia
Département de Mathématiques
GMI 3ème année
4) En déduire l’égalité M1 = M2
5) Construire un homomorphisme de monoïde {a, b}∗ −→ M1 . Montrer que cet homomor-
phisme est injectif et surjectif.
Exercice 3 Soit A un alphabet contenant au moins deux lettres a et b.
1) Donner un homomorphisme de A∗ dans (A.A)∗ .
2) Donner un homomorphisme de A∗ dans (A \ {b})∗ .
3) Y a-t-il un isomorphisme de monoïde entre (A \ {a})∗ et (A \ {b})∗ ?
Exercice 4 Lemme de Lévi : Soient u, v, x, y ∈ A∗ . Montrer que uv = xy si et seulement
si l’un des trois cas suivants est vérifié :
(i) |u| = |x|, u = x et v = y.
(ii) |u| < |x| et il existe t ∈ A∗ tel que ut = x et v = ty.
(iii) |u| > |x| et il existe t ∈ A∗ tel que u = xt et tv = y.
Exercice 5 Équations en mots : Soient u, v ∈ A∗ . Montrer les équivalences suivantes :
(1) uv = vu si et seulement si il existe w ∈ A∗ et m, n ∈ N tel que u = wm et v = wn .
(2) up = uq (avec p, q ∈ N) si et seulement si il existe w ∈ A∗ et m, n ∈ N tel que u = wm
et v = wn .
(3) uu = u si et seulement si u = .
(4) ua = au si et seulement si il existe p ∈ N tel que u = ap .
(5) ua = bu (avec a 6= b) si et seulement si 0 6= 0
2. Langages rationnels
Exercice 6 1) Montrer que (P(A∗ ), ., ) est un monoïde.
2) Montrer que (Li )i∈I est une famille quelconque de langages, alors
[ [
( Li )i∈I . L = ( Li . L)i∈I
3) Montrer que L∗ = (L + )∗ = + L.L∗
4) Montrer que ∅∗ =
Exercice 7 Soit X = b et Y = (A \ b) . b∗ .
1) Décrire informellement les éléments de X∗ , Y, et Y ∗ .
2) Montrer que tout mot de A∗ commençant par une lettre distincte de b appartient à Y ∗ .
3) Montrer que tout mot u de A∗ s’écrit d’une façon unique sous la forme u = vw, où
v ∈ X∗ et w ∈ Y ∗ .
2
Université Hassan II Casablanca
Faculté des Sciences et Techniques Mohammedia
Département de Mathématiques
GMI 3ème année
Exercice 8 Soit L un langage sur un alphabet A et Pref(L) := {u ∈ A∗ /∃v ∈ A∗ : uv ∈ L}
l’ensemble des préfixes de L.
Montrer que si L est reconnaissable, alors Pref(L) est aussi reconnaissable.
Exercice 9 Montrer que tout langage fini est reconnu par un automate fini déterministe. (On
expliquera comment on peut construire un tel automate à partir des préfixes des mots de ce
langage).
Exercice 10 Soit A un automate fini sur un alphabet A fini.
1. Montrer que les propositions suivantes sont équivalentes :
(i) le langage reconnu par A est fini ;
(ii) Le graphe orienté correspondant à l’ensemble des transitions de A ne contient pas
de circuit ayant un sommet sur un chemin allant d’un état initial à un état final.
2. Donner alors la borne supérieure de la taille du langage en fonction du nombre d’états
et de la taille de l’alphabet.
3. On suppose que l’automate A est déterministe et complet. Décrire les automates pour
lesquels cette borne est atteinte.
Exercice 11 Déterminiser et compléter l’automate suivant sur l’alphabet {a, b, c}, où l’état
initial et les états finaux sont notés i et f, f 0 .
f ←− x ←− i ←→ y −→ z ←→ f 0
Exercice 12 Soit A = {a, b, c}. Donner des automates déterministes complets reconnaissant
les langages suivants :
1. L’ensemble des mots de longueur paire.
2. L’ensemble des mots où le nombre d’occurrences de "b" est divisible par 3.
3. L’ensemble des mots se terminant par "b".
4. L’ensemble des mots ne se terminant pas par "b".
5. L’ensemble des mots non-vides ne se terminant pas par "b".
6. L’ensemble des mots contenant au moins un "b".
7. L’ensemble des mots contenant au plus un "b".
8. L’ensemble des mots contenant exactement un "b".
9. L’ensemble des mots ne contenant aucun "b".
10. L’ensemble des mots contenant au moins un "a" et dont la première occurrence de "a"
n’est pas suivie par un "c".
11. L’ensemble des mots comportant au moins trois lettres et dont la troisième lettre à
partir de la fin est un "a" ou un "c".
3
Université Hassan II Casablanca
Faculté des Sciences et Techniques Mohammedia
Département de Mathématiques
GMI 3ème année
Exercice 13 Considérons un automate fini non complet A. Supposons qu’on en dérive un
automate complet A 0 de la façon suivante : pour a ∈ A et s ∈ S tels qu’il n’existe pas de
transition d’origine s et d’étiquette a, on ajoute une boucle d’étiquette a en s, c’est-à-dire la
transition (s, a, s).
1. Si A est déterministe, A 0 l’est-il aussi ?
2. Quelle relation y a-t-il entre L(A) et L(A 0 ) ?
Exercice 14 (Lemme d’itération)
1. Montrer que si G est un graphe orienté à n sommets et c est un chemin de longueur
≥ n dans G, alors le sous-chemin de c constitué des n premières arêtes de c contient
un circuit.
2. Considérons un système de transitions à n états étiqueté sur un alphabet A, et soit q,
q’ deux de ces états. Montrer que si z ∈ Lq,q 0 et | z |≥ n, alors il existe u, v, w ∈ A∗
tels que z = uvw, v 6= , | uv |≤ n, et v est la trace d’un circuit ; de plus pour tout
i ∈ N, uvi w ∈ Lq,q 0 .
3. soit A un automate fini à n états. Alors pour tout z ∈ L(A) vérifiant | z |≥ n, il existe
u, v, w ∈ A∗ tels que z = uvw, v 6= , | uv |≤ n, et pour tout i ∈ N, uvi w ∈ L(A).
Exercice 15 Application : Montrer que les langages suivants sont ne sont pas reconnais-
sables parce qu’ils ne peuvent pas être égaux à L(A) pour un automate fini A.
1) {an bn | n ∈ N}.
2) {an | n ∈ N}
2
3) {ap | p est premier}
4) {ww | w ∈ A∗ }, quand A a au moins deux lettres.
5) L’ensemble des palindromes, en d’autres termes des mots w1 , ..., wn ∈ A∗ n ≥ 0 tels
que w1 ...wn = wn ...w1 , c’est-à-dire, wi = wn+1−i pour i=1,...,n, quand A au moins
deux lettres.
Dans tous les cas on va raisonner par l’absurde : on suppose que le langage donné est
reconnu par un automates à k états, et en appliquant le lemme d’itération, on montrera
qu’il doit contenir aussi d’autres mots que ceux indiqués.
