DEVOIR SURVEILLE
Semestre : 1 2
Session : Principale Rattrapage
Module : Théorie des langages et compilation
Enseignant(s) : Equipe TLA
Classe(s) : 3A31 ..3A61
Documents autorisés : OUI NON Nombre de pages : 2
Calculatrice autorisée : OUI NON Internet autorisée : OUI NON
Date : 08/11/2023 Heure 13h30 Durée : 1h
Exercice 1 : (5 pts)
1. Soit l’alphabet = {a,b}. Construire, en précisant toutes les étapes, un automate qui
reconnait tous les mots sur * sauf ceux qui contiennent la séquence ab. (4 pts)
2. Donner l’expression régulière correspondante. (1 pt)
Exercice 2 (7 pts) :
Soit l’expression régulière suivante sur l’alphabet = {a,b}: 𝑏 ∗ 𝑎𝑏(𝑏|𝑎+ )
1. Donner un AFN reconnaissant ce langage avec l'algorithme de Thompson. (2 pts)
2. Donner l’automate fini déterministe équivalent. (3 pts)
3. Minimiser cet automate. (2 pt)
Exercice 3 (7 pts) :
1. Donner les expressions régulières correspondantes aux langages suivants :
a. Le langage L1 de tous les mots 𝑤 construits sur {a,b} et dont la |𝑤| = 3 . (0.5 pt)
b. Le langage L2 de tous les mots les mots formés d’alternance de a et b (1.5 pt)
c. Le langage L3 de tous les mots sur {a,b}* contenant un nombre de a divisible par 3
(1.5 pt)
1
2. Compléter les deux parties du fichier de spécification Flex suivant pour construire un
analyseur lexical reconnaissant les trois langages L1, L2 et L3 et permettant de retourner sur
la console, à chaque identification d’un lexème, la chaine reconnue ainsi que la description.
(1.5 pt)
…………………………………………………
…………………………………………………
…………………………………………………
%%
{………………} printf(…………………………………………………………………………);
{………………} printf(…………………………………………………………………………);
{………………} printf(…………………………………………………………………………);
%%
int main(void){
yylex() ;
return 0 ;
}
3. Donner le résultat d’exécution de l’analyseur lexical sur les instructions suivantes : (2 pts)
a. 𝑎𝑏𝑏𝑎𝑎𝑏𝑎𝑏𝑎
b. 𝑏𝑏𝑎𝑏𝑎𝑏𝑏𝑎𝑏𝑏𝑎
c. 𝑎𝑏𝑎𝑎𝑏𝑏𝑎𝑏
d. ababbba
Bon Travail
