Établissement : UVBF Département : Sciences du numérique
Matière : Introduction à la compilation Enseignant : Mohamed Zeba/Dr. Aminata Zerbo Sabané
Parcours : Pure Developer Niveau : Licence 1 Semestre 1
Mars 2023
Travaux dirigés N°1 : Théorie des langages
Exercice 1
Soient L et M deux langages définis par des mots de longueur 1 comme suit :
L = {0, 1, 2, 3} et M = {7, 8, 9}.
Que définissent les langages suivants : L∪M, L 2, L.M, (L∪M)+
Exercice 2
Soient L = {A, B, ..., Z} U {a, b, ..., z} et C = {0, 1, ..., 9}.
Donnez une description littéraire des langages suivants :
L∪C, LC, L4 , L(L∪C)
Exercice 3
Soit l’alphabet A = {a, b}
Étant donnés les mots u = aa et v = bab, écrire les mots uv, (uv)2 et u3v.
Énoncer tous les mots de longueur 2 définis sur A.
Soient les ensembles :
• E 1 = {u.v/u ∈ A+, v ∈ A+}
• E 2 = {u.v/u ∈ A+, v ∈ A∗}
• E 3 = {u.v/u ∈ A∗, v ∈ A∗}
À quoi correspondent ces ensembles ?
Exercice 4
Déterminez l’alphabet pour chacun des langages suivants :
1. Les nombres hexadécimaux ;
2. Les nombres romains ;
3. Les nombres réels en C ;
4. Les identificateurs en C ;
5. Le langage C ;
Exercice 5
Trouvez les langages correspondants aux définitions suivantes :
1. Tous les mots sur l’ensemble {a, b, c} de longueur 2 contenant un a ou un b mais pas les deux ;
2. Tous les mots sur l’ensemble {a, b} contenant au maximum deux a ou bien un b ;
3. Tous les mots sur l’ensemble {a, b} qui contiennent plus de a que de b ;
4. Le langage L défini comme suit : {ε ; u ∈ L ⇒ aaub ∈ L}
Exercice 6
Sur l’alphabet A = {0, 1}, on considère les langages L1 et L2 définis par : L1 = {01 n, / n ∈ N} et L2 = {0n1, / n ∈ N }.
Définir les langages L1.L2, L∩L2 et L12.
Exercice 7
Sur l’alphabet A = {a, b}, on considère le langage L1 des mots formés de n fois la lettre a suivi de n fois la lettre b, et
le langage L2 des mots comportant autant de a que de b.
o Définir formellement ces deux langages.
o Que sont les langages suivants : L1 ∪ L2, L1 ∩ L2 , L12 , L22 ?
o Que peut-on dire de L1* et L2* par rapport à L1 et L2 ?
Travaux dirigés N°2 : Expression régulière
Exercice 1 : Pour s’échauffer
Soit l'expression régulière E1= (a + b) *. Est-ce que les mots aa, aab et baa appartiennent au langage décrit
par E1 ?
Soit l'expression régulière E2= (a* b* c*). Est-ce que les mots aa, ab, aab, cb et aabc appartiennent au
langage décrit par E2 ?
Soit l'expression régulière E3= (a + b) *abb. Est-ce que les mots aa, aab, abaab et aaabb appartiennent au
langage décrit par E3 ?
Exercice 2
Décrire les langages, définis sur = {a, b}, dénotés par les expressions régulières suivantes et donnez à
chaque fois 6 exemples de mots appartenant à ce langage.
• a(a|b) * a
• a|b *
• (a|b) * abb(a|b) *
• b * ab * ab * ab *
Exercice 3
1. Donner une expression régulière qui valide une forme simplifiée des adresses électroniques. On
considérera la définition simplifiée suivante :
• Une adresse électronique est constituée d’un champ ou plusieurs suivies d’un @ suivi d’un
champ ou plusieurs.
• un champ est constitué d’un caractère ou plusieurs (lettre, chiffre, -, _).
2. Donner une expression régulière qui accepte les nombres binaires constitués d’au moins deux 0.
3. Donner une expression régulière qui accepte les nombres binaires constitués d’au plus trois 0
Exercice 4
Sur l’alphabet Σ = {0, 1}, écrire des expressions régulières qui définissent les langages suivants :
Tous les mots qui se terminent par 1.
Tous les mots ayant au moins un 1.
Tous les mots ayant au plus un 1.
Tous les mots ayant exactement un seul 1.
Tous les mots dont la troisième position à droite est un 1.
Tous les mots ayant un nombre pair de 1.
Tous les mots dans lesquels chaque suite de 1 consécutifs est de longueur paire.