Théorie des langages : Exercices autommates et grammaires
Télécharger PDFAutomates et grammaires
Durée : 2h00, sans documents.
Tous les appareils électroniques sont interdits à l'exception des montres.
Le barème est donné à titre indicatif.
Le sujet comporte 6 exercices indépendants.
Le sujet est sur 75 mais il suffit d'avoir 50 pour obtenir la note maximale, ce qui vous donne le choix et vous permet de faire l'impasse sur 2 exercices.
Commencez par lire tout le sujet pour repérer les questions faciles.
Exercice 1 : Grammaire des identifiants
Dans la plupart des langages de programmation, les noms de variables (appelés identifiants) doivent respecter les contraintes suivantes :
1. Les identifiants sont formés de lettres minuscules ('a', ..., 'z'), de lettres majuscules ('A', ..., 'Z'), de chiffres ('0', ..., '9') et du caractère souligné '_'.
2. Un identifiant doit commencer par une lettre minuscule dans 'a', ..., 'z'.
Exemple : x, y sont des identifiants ; A, 1, - ne sont pas des identifiants.
3. Un identifiant ne doit pas se terminer par un souligné '_'.
Exemple : x_1, y_bs sont des identifiants ; x_, y_ ne sont pas des identifiants.
Q1. Grammaire des identifiants
Donnez une grammaire des identifiants qui respecte ces contraintes.
Q2. Grammaire avec contraintes supplémentaires
Donnez une grammaire des identifiants qui respecte les contraintes précédentes et les contraintes suivantes (qui n'existent pas dans les langages de programmation) :
4. Un identifiant ne doit pas contenir plusieurs caractères '_' consécutifs.
Exemple : x_A_1, y_B_2 sont des identifiants ; x__, y__2 ne sont pas des identifiants.
5. Un chiffre doit être précédé d'un souligné '_' ou d'un chiffre.
Exemple : x_1, y_2 sont des identifiants ; x1, y2 ne sont pas des identifiants.
Exercice 2 : Grammaire des déclarations de variables en C
La syntaxe des déclarations de variables en C est définie par une grammaire avec le non-terminal SomeDecl, et pour règles :
SomeDecl → OneDeclSomeDecl | ε
OneDecl → TypeVarsOptAsc ';' Type → "int" | "float"
Vars → OneVarMoreVars
MoreVars → ε | ',' Vars
OneVar → grammaire de l'Exercice 1 : OptAsc → ε | '=' Value
Value → Float | Int
Q3. Attributs hérités et synthétisés
Ajoutez des attributs à la grammaire ci-dessus de manière à ce que le non-terminal SomeDecl retourne une liste de déclarations indépendantes de variables, au format du langage Pascal, et avec leur valeur d'initialisation si elle est présente.
Indication : Vous devez produire un résultat conforme aux exemples ci-dessous.
Exemples :
- SomeDecl[〈int x, y, z = 0;〉] = ["x : integer = 0"; "y : integer = 0"; "z : integer = 0"]
- SomeDecl[〈int x = 0; float x, y = 3.14;〉] = ["x : integer := 0"; "x : real := 3.14"; "y : real := 3.14"]
Exercice 3 : Transducteurs et addition binaire d'automates
Dans tout l'exercice, on considère des nombres en binaire écrits avec l'unité à gauche.
Exemples :
(1) ≡ (1)₂ ≡ (1.0000)₂ ≡ (1.0*)₂
(2) ≡ (0.1)₂ ≡ (0.1.0*)₂
(3) ≡ (1.1)₂ ≡ (1.1.0*)₂
Q4. Automate reconnaissant les nombres binaires impairs ≥ 3
Donnez un automate A qui reconnaît les nombres binaires impairs ≥ 3, écrits avec les unités à gauche. Autrement dit, {11, 101, 111, 1001} ∈ L(A) et {0, 01, 001} ∉ L(A).
Q5. Expression régulière équivalente à A₂
Donnez une expression régulière équivalente à A₂.
Q6. Transducteur T1
On considère le transducteur T1 défini par :
d = //
? → = <89:; 76540123
q 0/1 II 1/0
Décrire (à chaque fois en une phrase) :
1. Le langage reconnu par le transducteur T1.
2. L'effet du transducteur T1 sur les mots qu'il reconnaît.
3. Le langage de sortie du transducteur T1.
Q7. Automate A
On considère l'automate A défini par :
GFED@ABC ? → = <89:; a 1
GFED@ABC ? → = <89:; a '0
Décrire en une phrase les nombres binaires (avec unité à gauche) reconnus par l'automate A.
Q8. Produit de A par T1
Construisez le produit de A par le transducteur T1, puis décrire en une phrase le langage de sortie de l'automate A × T1.
Q9. Transducteur T2
Donnez un transducteur T2 qui reconnaît tous les mots et qui remplace les 0 par des 1 lorsque le 0 est précédé d'un 1.
Exemples :
- T2(001001) = 001101
- T2(000000) = 000000
- T2(101000) = 111100
Q10. Transducteur-additionneur Tp
Construisez le transducteur-additionneur Tp associé à l'automate A défini par :
GFED@ABC a 01
GFED@ABC a 11
GFED@ABC ? → = <89:; a 20
Q11. Explication sur les automates An et Ap
On suppose que An et Ap sont des automates sur Σ = {0, 1}. Expliquez comment obtenir l'automate qui reconnaît le langage {n + p | n ∈ L(An), p ∈ L(Ap)}.
Exercice 4 : Modélisation de protocoles médicaux à l'aide d'AEF
Durée : 30 min, 15 points.
4.1 Produit d'automates harmonisés
On considère les automates suivants :
A1 défini par :
? → = <89:; 1 a
? → = <89:; 2 b
? → = <89:; 76540123 sur l'alphabet Σ₁ = {a, b}
A2 défini par :
GFED@ABC 1 'a
GFED@ABC 2 'c
GFED@ABC ? → = <89:; 3 sur l'alphabet Σ₂ = {a, c}
Q12. Langage reconnu par A1 × A2
Décrivez le langage L(A1 × A2) reconnu par l'automate A1 × A2. Justifiez avec précision votre réponse.
4.2 Harmonisation d'automates
Lorsqu'on souhaite harmoniser deux automates qui n'ont pas le même alphabet (Σ₁ et Σ₂), on étend les automates pour qu'ils aient un alphabet commun (Σ = Σ₁ ∪ Σ₂). Cela consiste à rendre un automate insensible à un symbole qui n'était pas dans son alphabet, en ajoutant à chaque état de l'automate une boucle sur les nouveaux symboles.
Exemple : AΣ1 et AΣ2 ci-dessous sont les versions harmonisées des automates précédents étendus à l'alphabet Σ = {a, b, c}.
AΣ1 défini par :
? → = <89:; 1 a
? → = <89:; 2 b
? → = <89:; 76540123 c
AΣ2 défini par :
? → = <89:; 1 'a
? → = <89:; 2 'c
? → = <89:; 76540123 'b
Q13. Produit AΣ1 × AΣ2
Construisez le produit AΣ1 × AΣ2.
Q14. Langage reconnu par AΣ1 × AΣ2
Donnez le langage reconnu par AΣ1 × AΣ2.
4.3 Imagerie médicale
Protocole P1 : On commence par injecter dans le patient un produit radioactif (phase d'injection = i) qui permet de voir un organe par analyse du rayonnement, on peut ainsi visualiser l'organe (phase photographie = p). Ensuite, on injecte des produits qui neutralisent par capture les produits radioactifs (phases neutralisation 1, 2 = n1, n2) qui sont ensuite éliminés par le corps (phase d'élimination = e).
Q15. Alphabet Σ₁ du protocole P1
Donnez l'alphabet Σ₁ du protocole P1.
Q16. Automate correspondant à P1
Donnez l'automate correspondant à P1.
4.4 Intervention chirurgicale
Protocole P2 : On commence par une analyse de sang (phase s) avant toute injection, ensuite on effectue une photographie de l'organe (phase p), ensuite on effectue une série d'anesthésie (phase a) suivie d'une intervention chirurgicale (phase c). Enfin, on surveille le patient jusqu'à son réveil (phase r).
Q17. Alphabet Σ₂ du protocole P2
Donnez l'alphabet Σ₂ du protocole P2.
Q18. Expression régulière correspondant à l'automate P2
Donnez l'expression régulière correspondant à l'automate ci-dessous :
P2 défini par :
// /.-,()*+ s
/.-,()*+ p
/.-,()*+ a r
/.-,()*+ c ]]
4.5 Combinaisons de protocoles
On souhaite combiner les protocoles P1 et P2 avec deux contraintes à respecter :
C1 : L'analyse de sang (phase s) doit avoir lieu avant l'injection de produits radioactifs (phase i).
C2 : Après une injection (phase i), on doit faire une neutralisation 1 (phase n1) avant toute anesthésie (phase a).
Q19. Modélisation de la contrainte C1
Expliquez comment modéliser la contrainte C1 sur l'alphabet Σ = Σ₁ ∪ Σ₂.
Q20. Modélisation de la contrainte C2
Expliquez comment modéliser la contrainte C2 sur l'alphabet Σ = Σ₁ ∪ Σ₂.
Q21. Construction du protocole P
Expliquez comment construire un protocole P qui indique comment pratiquer une imagerie médicale en respectant le protocole P1 et d'effectuer une intervention chirurgicale ensuite en respectant le protocole P2 tout en respectant les contraintes C1 et C2.
Q22. Critère de réalisabilité du protocole P
Expliquez comment savoir si le protocole P est réalisable. Autrement dit, donnez un critère qui permet de déterminer s'il est possible de satisfaire simultanément les exigences de P1, P2, C1 et C2.
Q23. Algorithme pour vérifier la réalisabilité de P
Donnez un algorithme qui permet de savoir si P est réalisable.
Q24. Dispositif informatique pour suivre les étapes du protocole P
Imaginons que P soit réalisable. Proposez un dispositif informatique qui, à partir de l'automate P, permet de savoir à chaque étape du protocole quelles sont les actions autorisées.
Exercice 5 : Inclusions de langages
On considère l'alphabet Σ = {a, b} et les langages L1 à L5 ci-dessous.
Q25. Comparez les langages deux à deux et indiquez les relations qu'ils vérifient : ⊆ (inclusion large), ⊂ (inclusion stricte), = (égalité), ou bien intersection vide. Justifiez chaque réponse par un raisonnement ou un contre-exemple.
Les justifications comptent pour 2/3 des points.