PandaCodeur · Examen 2 / 4
Examen de compilation : 2. Lexique et automates
Sujet original : 2 heures, niveau licence, 20 points.
Consignes et rappel
Barème : 4 + 4 + 6 + 6 = 20 points. Fixez les conventions de regex. Une expression décrit un langage ; un AFN accepte si un chemin complet est acceptant ; un AFD suit un seul chemin.
1. Langages et compilation : 4 points
Définir mot, langage, compilation et token (2 points). Calculer {a,ab}{ε,b}, puis comparer ∅* et {ε}* (2 points).
Afficher la correction expliquée
Un mot est une suite finie de symboles ; un langage est un ensemble de mots ; compiler consiste à traduire vers une représentation cible ; un token est une catégorie lexicale éventuellement accompagnée d’un attribut. Le produit vaut {a,ab,abb} : ab n’est compté qu’une fois. ∅* = {ε}* = {ε}.
2. Motifs et priorité : 4 points
Donner des motifs ASCII pour ID et un nombre décimal à exposant optionnel (2 points). Découper ifx==20E+2; en indiquant le rôle de la plus longue correspondance et de la priorité IF/ID (2 points).
Afficher la correction expliquée
ID = [A-Za-z_][A-Za-z0-9_]*
NUMBER = [0-9]+(\.[0-9]+)?([Ee][+-]?[0-9]+)?
Tokens : ID(ifx), EQEQ, NUMBER(20E+2), SEMIifx est plus long que le mot-clé if, donc ID gagne. Sur if seul, les motifs IF et ID ont même longueur : la priorité du mot-clé tranche. == est préféré à =.
3. Déterminisation : 6 points
Σ = {0,1} ; initial q0 ; final q2
δ(q0,0) = {q0,q1} ; δ(q0,1) = {q0}
δ(q1,1) = {q2} ; autres transitions = ∅Déterminiser (3 points), donner une expression régulière du langage (1 point), tracer 101 et 010 (2 points).
Afficher la correction expliquée
| État | 0 | 1 | Final |
|---|---|---|---|
| → A={q0} | B | A | Non |
| B={q0,q1} | B | C | Non |
| * C={q0,q2} | B | A | Oui |
Expression : (0|1)*01. Sur 101 : A → A → B → C, accepté. Sur 010 : A → B → C → B, refusé. Les trois ensembles accessibles sont tous non vides ; cet AFD est complet.
4. Minimiser et complémenter : 6 points
Minimiser l’AFD obtenu (3 points). Construire son complément et tester ε, 1 et 01 (3 points).
Afficher la correction expliquée
P0 = {{C},{A,B}}. Sur 1, A mène à A non final et B mène à C final, donc A et B se séparent. Les trois états sont accessibles et distinguables : l’automate est minimal. Pour le complément, garder les transitions et prendre {A,B} comme états finaux, car l’AFD est déjà complet. ε et 1 sont acceptés ; 01 est refusé.