Théorie des langages : Td automate et grammaire
Télécharger PDFRICM3 – Automates et Grammaires
Durée : 2 heures, sans documents.
– Tous les appareils électroniques sont interdits, à l'exception des montres mécaniques.
– Le barème est donné à titre indicatif.
– Le sujet comporte 5 exercices indépendants.
– Le sujet est noté sur 25,5 points, mais il suffit d'obtenir 20 pour avoir la note maximale, ce qui vous permet de choisir et de sauter certaines questions.
Exercice 1
Questions de cours (20 min) – 3,5 points
Q1. Pour un alphabet Σ donné et une longueur de mot n donnée, est-il possible de construire un automate à états finis qui reconnaît les mots de longueur n ? Si oui, expliquez le principe de sa construction. Si non, expliquez pourquoi cela est impossible.
Q2. Décrivez par une phrase en français le langage correspondant à l'expression régulière (a|b)*·c. Est-il fini ou infini ?
Q3. Complétez (répondez sur votre copie) :
(1) {a,b}*·{c,d} =
(2) {a,b}*·{a,e} =
(3) {a}*·{} =
(4) {}*·{a} =
(5) {a,b}*·{a}* =
Q4. Comment savoir si un automate à états finis est déterministe ou non-déterministe ?
Q5. Est-il possible qu'un automate à états finis reconnaisse un langage infini ? Si oui, donnez un exemple. Si non, expliquez pourquoi cela est impossible.
Q6. Complétez (répondez sur votre copie) : Deux automates sont équivalents si et seulement si...
Q7. Les automates à états finis déterministes sont-ils capables de reconnaître les mêmes langages que les automates à états finis non-déterministes ? Justifiez votre réponse.
Exercice 2
Définition des identificateurs par différence d'expressions régulières (20 min) – 5,5 points
Dans la plupart des langages de programmation, les noms de variables (appelés identificateurs) doivent respecter les contraintes suivantes :
1. Les identificateurs sont formés de lettres (a,...z), de chiffres (0,...9) et du caractère souligné '_'.
2. Un identificateur doit commencer par une lettre (a,...z) ou le caractère '_'.
Exemple : x et _y sont des identificateurs, 1_x n'en est pas un.
3. Un identificateur ne doit pas se terminer par un souligné '_'.
Exemple : x_1 est un identificateur valide, x_ n'en est pas un.
4. Un identificateur doit contenir au moins une lettre.
Exemple : _1_x est un identificateur valide, _1_2 n'en est pas un.
5. Un identificateur ne doit pas contenir deux soulignés consécutifs.
Exemple : _1_x est un identificateur valide, __x n'en est pas un.
Le but de cet exercice est de décrire les identificateurs valides par la différence de deux expressions régulières, e1 \ e2. Autrement dit, un identificateur sera valide s'il est reconnu par e1 et rejeté par e2.
L'intérêt de cette description est qu'il est difficile d'écrire directement une expression régulière qui respecte toutes les contraintes, alors qu'il est facile d'écrire une expression régulière e1 qui traite une partie des contraintes et de corriger ce qu'elle accepte en trop par une expression régulière e2, également simple.
Q8. Donnez les expressions régulières (e_l, e_c, Σ) qui reconnaissent respectivement une lettre, un chiffre, et l'alphabet considéré dans cet exercice.
Q9. Donnez une expression régulière e1 qui reconnaît les mots respectant les contraintes 1, 2 et 3.
Q10. Dessinez l'automate A1 correspondant à e1.
Q11. Donnez deux mots de longueur 4 qui ne satisfont pas la contrainte 4 et deux mots de longueur 4 qui ne satisfont pas la contrainte 5.
Q12. Donnez une expression régulière e2 qui accepte les mots respectant la contrainte 1 mais pas les contraintes 4 et 5, de sorte que e1 \ e2 correspondent exactement aux identificateurs valides.
Q13. Dessinez l'automate A2 correspondant à e2.
Transformation en une expression régulière sans opérateur «\»
Sur des ensembles E et F, l'opération «privé de», notée E\F, correspond à E ∩ Fᶜ. Sachant cela, on peut définir le langage reconnu par e1 \ e2 comme suit : L(e1 \ e2) = L(e1) ∩ L(e2ᶜ).
Q14. Décrivez les étapes (≥6) qui permettent, à partir des automates A1 et A2, d'obtenir une expression régulière équivalente à e1 \ e2 sans utiliser l'opérateur «\».
Exercice 3
Minimisation (20 min) – 3,5 points
On considère l'automate suivant :
États : 1, 2, 3, 4, 5, 6, 7, 8, 9
Transitions :
a : 1→2, 3→4, 9→8, 4→9, 9→9
b : 3→2, 2→2, 3→7, 2→7, 7→2
c : 1→4, 4→4, 4→6, 5→5, 8→8
État initial : 1
États finaux : 6, 9
Q15. Le langage reconnu par l'automate ci-dessus est-il vide ? Justifiez votre réponse.
Q16. Minimisez cet automate en justifiant chaque étape de l'algorithme. Les états équivalents sont notés 2 et 3.
Q17. Dessinez l'automate minimisé.
Exercice 4
Grammaire des listes de diffusion (30 min) – 6 points
Les adresses email sont formées d'un nom d'utilisateur et d'un nom de domaine séparés par '@'. Les noms d'utilisateur et de domaine sont formés d'une séquence d'identificateurs séparés par des points '.'.
Les identificateurs sont des mots comportant des lettres, des chiffres et des caractères '-'.
Indication : Dans cet exercice, on suppose que les identificateurs sont déjà définis par le non-terminal Ident. Vous pouvez donc l'utiliser.
Les adresses email sont définies par l'expression régulière :
email = Ident·('.'·Ident)*·'@'·Ident·('.'·Ident)*
Ne pas confondre «·» (opérateur de concaténation) avec le caractère '.' qui fait partie de l'alphabet Σ.
Q18. Donnez deux mots qui appartiennent à L(email) et deux mots qui n'en appartiennent pas.
Q19. Donnez une grammaire avec le non-terminal Email comme germe qui reconnaît le même langage que l'expression régulière email.
Q20. Complétez la grammaire précédente avec un non-terminal Liste afin qu'elle engendre les listes de diffusion définies comme une séquence (éventuellement vide) d'adresses email séparées par des virgules ',' et terminée par une virgule ','.
Q21. Complétez la grammaire précédente avec un attribut n ∈ ℕ afin qu'elle retourne le nombre d'adresses dans la liste de diffusion.
Q22. Modifiez la grammaire pour lui ajouter un attribut fréquence : Liste(Ident × ℕ) afin qu'elle retourne la fréquence de chaque nom d'hébergeur dans la liste de diffusion.
La partie hébergeur d'un domaine est son premier identificateur.
Exemple : les domaines gmail.com et gmail.fr ont le même hébergeur : gmail.
Q23. Donnez le code Caml de la fonction qui permet d'incrémenter la fréquence d'un hébergeur.
Exercice 5
Modélisation à l'aide d'automates – les «fuzzy password» (30 min) – 7 points
Un «fuzzy password» est défini par un code secret (par exemple, 4137) et permet d'y mêler des symboles quelconques pour le rendre imprévisible.
On considère l'alphabet Σ = L ∪ C, où L = {a,...,z} et C = {0,...,9}.
Q24. On considère le langage L1 formé des mots sur l'alphabet Σ contenant les chiffres du code 4137 dans cet ordre. Donnez trois mots qui appartiennent à L1 et trois mots qui n'y appartiennent pas.
Q25. Dessinez un automate à états finis non-déterministe A1 qui reconnaît L1.
Résistance d'un tel mot de passe
Ce mot de passe est facile à casser : il suffit d'essayer toutes les combinaisons de symboles de l'alphabet autant de fois qu'il y a de symboles dans le code 4137. Pour le rendre plus résistant, on limite à 12 le nombre de symboles qu'on peut taper.
Q26. Expliquez comment construire, à partir de l'automate A1 de la question précédente, un automate A2 qui reconnaît le langage