Université de YDE 1 / DEP INFORMATIQUE TD Compilation
MASTER 1 Informatique
Dr. NGUIMEYA T BAUDOIN/ Dr KOUEKAM
Exercice 1 question de cours
1. La compilation est constituée des plusieurs phases : citez-les
2. L’erreur suivante : fi (a == f(x)) au lieu de if ( a == f(x) ), est de quel type ?
3. Dans l’analyse syntaxique ascendante, la réduction d’une chaine est L’inverse d’une dérivation à
droite : vrai ou faux
4. Tout langage régulier est hors-contexte : vrai ou faux
GISELE
Exercice 2
Soit la grammaire LL (1) suivante :
S → ABC | DAD
A → aA | ε
B → bB | ε
C → eC | ε
D → dD | f
Ou l’axiome est {S}, les terminaux sont {a, b, e, d, f}, et les non terminaux sont {S, A, B, C, D}
1. Construire les ensembles PREMIER et SUIVANT pour cette grammaire.
2. Établir la table d'analyse de cette grammaire.
3. Simuler l'analyse de l'expression abe par un analyseur descendant LL(1).
Exercice 3
Les palindromes sont les mots qui sont inchangés par renversement.
Exemple : "", "a", "abba", "abcba" sont des palindromes sur l’alphabet {a,b,c}.
1. Donnez une grammaire qui reconnait les palindromes sur l’alphabet {a,b,c}.
2. Donnez l’arbre de dérivation qui permet à votre grammaire de générer le mot
3. "abccba".
Exercice 4
On considère l’alphabet Σ = {a,b,c}. On note · l’opérateur de concaténation de mots.
a) Dessinez l’automate obtenu par élimination des ℰ-transitions dans l’automate ci-dessous
1/4
Université de YDE 1 / DEP INFORMATIQUE TD Compilation
MASTER 1 Informatique
Dr. NGUIMEYA T BAUDOIN/ Dr KOUEKAM
b) Donnez un automate qui reconnaît le langage Σ∗
c) Donnez un automate complet qui reconnaît le langage Σ
d) Donnez la définition de L1 • L2 où • est l’opérateur de concaténation de langages.
e) Décrivez en une phrase en français le langage reconnu par l’expression régulière Σ•Σ∗
f) Donnez un automate qui reconnaît le langage associé à Σ • Σ∗.
Exercice 5 : Déterminisation d’un automate à deux états initiaux
On considère l’automate suivant qui comporte deux états initiaux et un état accepteur :
A 1i 2 3i 4a
a 1,2 3 4
b 1 3 4
a) Rappelez la définition de l’acceptation d’un mot par un automate non-déterministe.
b) Donnez l’arbre d’exécution de l’automate sur le mot « aabb ». Dessinez toutes les branches,
celles qui n’acceptent pas le mot et celles qui l’acceptent.
c) Déterminiez l’automate et donnez le résultat sous forme de tableau.
d)
Exercice 6
Exercice 1.1 Soit la grammaire formelle G =({a,b},{S,T},P,S) dont les règles de P sont :
(1) S → aS
(2) S → bR
(3) S → b
(4) R → aR
(5) R → bS
1. Montrer que le mot abbb est généré par G .
2. Montrer que le mot abb n’est pas généré par G.
3. Montrer qu’un mot se terminant par a ne peut pas être généré par G.
4. Montrer que les mots générés par G ont tous un nombre impair de b.
Exercice 7
Soit la grammaire formelle G =({a,b},{S,T},P,S) dont les règles de P sont :
(1) S → ε
(2) S → a
(3) S → b
(4) T → aSa
(5) T → bSb
1. Montrer que le mot abbabba est généré par G. Montrer que le mot baba n’est pas généré par G.
2/4
Université de YDE 1 / DEP INFORMATIQUE TD Compilation
MASTER 1 Informatique
Dr. NGUIMEYA T BAUDOIN/ Dr KOUEKAM
2. Montrer que G engendre l’ensemble L de tous les mots palindromes définis sur l’alphabet Σ={a,b}.
(Un palindrome est un mot identique à lui-même quand on lit ses symbole dans l’ordre inverse.)
Exercice 8
Exercice ; Determiniser et minimiser l’automate suivant :
Exercice 9 :
Donner, pour chacun des langages suivants, un automate qui le reconnaît.
3/4
Université de YDE 1 / DEP INFORMATIQUE TD Compilation
MASTER 1 Informatique
Dr. NGUIMEYA T BAUDOIN/ Dr KOUEKAM
Exercice 10
Soit l'automate
1. Dire pourquoi A n’est pas déterministe. Donner, sans justification, une expression réguliere
équivalente.
2. Déterminiser A et représenter le graphe de l’automate déterministe D obtenu.
3. Minimiser l’automate D apres l’avoir éventuellement complété. Dessiner l’automate
obtenu.
4/4
