2ème année Licence Fondamentale en Informatique et Multimédia
Année Universitaire : 2024-2025
Module : Théorie des Langages et Automates (TLA)
Enseignants :Tarek el Falah et Mahrez Ben Naila
Travaux Dirigés – Série N : 2
Exercice 1.
Sur l’alphabet X = {x, y} construire des automates finis déterministes reconnaissant les langages
suivants :
L1 = x*
L2 = x+
L3 = x*y*
L4 = x+y+ ≥
Vérifier en utilisant le lemme d’Arden
Exercice 2.
Donner un automate fini déterministe (AFD) qui accepte les mots ayant abc comme facteur.
Exercice 3.
1) Déterminer des automates finis déterministes reconnaissant les langages suivants :
X = {a, b, c}
L1 = {w X* / w contient un facteur abc}
L2 = {w X* / w se termine par aabb}
X = {0, 1}
L3 = {w X* / n(w) = 3k + 1, k 0} avec w est la représentation binaire de n(w)
L4 = l’ensemble des mots tels qu’il y ait soit deux 0 soit deux 1 consécutifs
1) En déduire des expressions régulières pour chacun des langages L1, L2, L3 et L4.
Exercice 4.
Rendre déterministe l’automate suivant :
M = ({q, r, s}, {a, b}, q, {s}, {(q, b, q), (q, a, r), (q, a, s), (r, a, q), (r, a, r), (s, a, s), (s, a, q), (s, b,
r)})
Minimiser l’automate suivant :
M1 = ({1, 2, 3, 4, 5}, {a, b}, 1, {4}, {(1, a, 2), (2, a, 3), (3, b, 4), (4, a, 5), (5, b, 4)})
1
Exercice 5.
Soit L1 = {w {a, b}* / w commence par a et se termine par bb}
1) Montrer que le langage L1 est régulier
2) Déterminer un automate fini déterministe qui reconnaît L1
Exercice 6.
1) Donner une expression régulière (ER) qui représente les commentaires dans les langages
de programmation C et python.
(On utilisera l’alphabet suivant {/, *, #, a, m, +, -, A, 1, "}).
2) Construire l’automate correspondant.
3) Rendre cet automate déterministe.
