Théorie des langages : Td automate et grammaire
Télécharger PDFRICM3 – Automates et Grammaires
Durée : 2h00, 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 sur 25.5 mais il suffit d’avoir 20 pour avoir la note maximale, ce qui
vous donne le choix et vous permet de faire l’impasse sur certaines questions.
Exercice 1Questions de cours(20 min)3.5pt Q1.Pour un alphabetΣdonné et une longueur de mot`donnée, est-il possible de constuire un0.5pt automate (à nombre) d’états fini que reconnaît les mots de longueur`?Si ouiexpliquez le principe
de construction de l’automate.Si nonexpliquez pourquoi cela est impossible.
Q2.Décrivez par une phrase en français le langage correspondant à l’expression régulière(a|b)∗ ·c.0.5pt Est-il fini ou inifini ?
Q3. Complétez (répondez sur votre copie)0.5pt (1){a,b}·{c,d}=
(2){a,b}·{a,e}=(3){a} ∗·{}= (4){}∗ ·{a}=
(5){a,}·{a}∗ =
Q4.Comment savoir si un automate (à nombre) d’états fini est déterministe ou non-déterministe ?0.5pt Q5.Est-il possible qu’un automate (à nombre) d’états fini reconnaisse un langage infini ?Si oui0.5pt donnez un exemple.Si nonexpliquez pourquoi cela est impossible.
Q6. Complétez (répondez sur votre copie)Deux automates sont équivalentssi et seulement0.5pt si...
Q7.Les automates (à nombre) d’états fini déterministes sont-ils capables de reconnaitre les mêmes0.5pt langages que les automates (à nombre) d’états fini non-déterministes ?Justifiez votre réponse.
Exercice 2Définition des identificateurs par différence d’expressions
régulières(20 min)5.5pt 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 :xet- ysont des identificateurs,1- xn’en est pas un.
3. un identificateur ne doit pas se terminer par un souligné’- ’
Exemple :x- 1est un identificateur valide,x- n’en est pas un.
4. un identificateur doit contenir au moins une lettre
Exemple :- 1- xest un identificateur valide,- 1- 2n’en est pas un.
5. un identificateur ne doit pas contenir deux soulignés consécutifs
Exemple :- 1- xest un identificateur valide,-- xn’en est pas un.
Le but de cet exerciceest 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 pare1 et rejetté pare2 .
L’intérêt de cette description c’est qu’il est difficile d’écrire directement l’expression régulière qui tient
compte de toutes les contraintes alors qu’il est facile d’écrire une expression régulièree1 qui traite une
partie des contraintes et de corriger ce qu’elle accepte en trop par une expression régulièree2 , elle aussi
simple à écrire.
Q8.Donnez les expressions régulières(el ,ec ,Σ)qui reconnaissent respectivement une lettre, un0.25pt chiffre, et l’alphabet considéré dans cet exercice.
Q9.Donnez une expression régulièree1 qui reconnaît les mots qui respectent les contraintes 1,2,3.0.75pt Q10.Dessinez l’automateA1 correspondant àe1 .0.75pt Q11.Donnez deux mots de longueur 4 qui ne satisfont pas la contraintes 4 et deux mots de0.25pt longueur 4 qui ne satisfont pas la contrainte 5.
Q12.Donnez une expression régulièree2 qui accepte les mots qui respectent la contrainte 1 mais0.75pt pas la contrainte 4, ni la contrainte 5 ; de sorte quee1 \e2 correspondent exactement aux identificateurs
valides, c’est-à-dire aux mots qui respectent les contraintes 1,2,3,4,5.
Q13.Dessinez l’automateA2 correspondant àe2 .0.75pt Transformation en une expression régulière sans opérateur «\»Sur des ensemblesEetF,
l’opération «privé de», notéeE\F, correspond àE∩F. Sachant cela, on peut définir le langage reconnupare 1\e 2: L(e1 \e2 ) =L(e1 )∩L(e 2) Q14.Décrivez les(≥6)étapes qui permettent, à partir des automatesA1 etA2 , d’obtenir une2pt expression régulière équivalente àe1 \e2 mais qui n’utilise plus l’opérateur «\».On vous demande
ni calcul, ni algorithme, mais une description précise, en français, de la méthode à suivre
en faisant référence à des algorithmes vus en cours.
Exercice 3Minimisation(20 min)3.5pt On considère l’automate suivant :A i1 a2345678 a9 a499881966
b322372722
c144465588
Q15.Le langage reconnu par l’automate ci-dessus est-il vide ?Justifiez votre réponse.0.5pt Q16.Minimisez l’automate en justifiant chaque étape de l’algorithme. Les2 3
des points sont2pt attribués aux justifications.
Q17.Dessinez l’automate minimisé.1pt
Exercice 4Grammaire des listes de diffusion(30 min)6pt Les adresses email sont formées d’un nom d’utilisateur et d’un nom de domaine séparées par’@’. Les
noms d’utilisateur et de domaines sont formés d’une séquence d’identificateurs séparés par des’.’.
Les identificateurs sont des mots comportant des lettres, des chiffres et des’- ’.
Indication :Dans cet exercice on suppose que les identificateurs sont déjà définis parIdent. Vous
pouvez donc l’utiliser.
Les adresses email sont définies par l’expression régulièreemail def
=Ident·(’.’·Ident)∗ ·’@’·Ident·(’.’·Ident)∗ Ne pas confondre «·» qui est l’opération 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’appartiennent pas0.25pt L(email)
Q19.Donnez une grammaire avec pour germe le non-terminalEmailqui reconnaît le même1pt langage que l’expression régulièreemail.
Q20.Complétez la grammaire précédente avec un non-terminalDiffafin qu’elle engendre les0.5pt listes de diffusion définies comme séquence (éventuellement vide) d’adresses email séparées par des
virgule’,’et terminée par une virgule’,’.
Q21.Complétez la grammaire précédente avec un attributn∈Nafin qu’elle retourne le nombre1.5pt d’adresse dans la liste de diffusion.
Q22.Modifiez la grammaire pour lui ajouter un attributfréquence:Liste(Ident×N)afin qu’elle1.5pt 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 codeCamlde la fonction qui permet d’incrémenter la fréquence d’un hébergeur.1.25pt
Exercice 5Modélisation à l’aide d’automates – les «fuzzy password»
(30 min)7pt L’objectif de cet exercice est de proposer une nouvelle forme de mot de passe basée sur les automates.
Un «fuzzy password» est défini par un code secret,4137dans l’exemple, et pour le rendre imprévisible
(fuzzy) on permet de mêler des symboles quelconque au code secret.
On considère l’alphabetΣ =L∪Cconstitué des lettresL={a,...,z}et des chiffresC={0,...,9}.
Q24.On considère le langageL1 formé des mots sur l’alphabetΣqui contiennent les chiffres du0.25pt code4137dans cet ordre. Autrement dit, les mots deL1 sont de la forme...4...1...3...7....
Donnez trois mots qui appartiennent àL1 et trois mots qui n’appartiennent pas àL1 .
Q25.Dessinez un automate (à nombre) d’états fininon-déterministeA1 qui reconnaîtL1 .0.75pt Résistance d’un telfuzzy passwordCe mot de passe est très facile à casser1 : il suffit d’essayer
toutes les symboles de l’alphabet autant de fois qu’il y a de symboles dans le code4137. Pour le rendre
plus résistant aux attaques, on décide de limiter à 12 le nombre de symboles qu’on peut taper.
Q26.Expliquez comment construire, à partir de l’automateA1 de la question précédente, un1.25pt automateA2 qui reconnaît le langageL2 constitué des mots deL1 de longueur≤12.On ne vous
demande pas de construire l’automate mais juste de décrire la méthode pour le construire.
Q27.Donnez une borne supérieure sur le nombre d’états de l’automateA2 .Justifiez votre0.75pt réponse.
AméliorationAfin d’empêcher un attaquant d’essayer systématiquement tous les symboles deΣ,
on souhaite se restreindre au langageL3 des mots surΣqui ne contiennent pas plusieurs occurences
d’un même symbole deΣ.
Exemple :aa... /∈L3 car il contient deux occurences dea,01234567890... /∈L3 est rejeté puisqu’il
contient deux occurences de 0
Q28.Expliquez comment construire unautomate (à nombre) d’états fini déterministeA3 qui1.5pt reconnaît le langageL3 .On ne vous demande pas l’automate mais la méthode de contruction.
Indication :Vous pourrez nommer les états deA3 par les symboles qu’on a encore le droit de taper.
Q29.Donnez le nombre exact d’états de l’automateA3 .Justifiez votre réponse.0.5pt Q30.Expliquez comment construire un automateA4 qui reconnaît les mots de passe valide deL1 0.5pt
qui sont sans occurence multiple de symboles deΣ.Justifiez votre réponse.
Autre proposition defuzzy passwordOn considère à présent un autre type d’automate qui
permet de glisser le code secret4137choisi par l’utilisateur au milieu de lettres qui semblent aléatoires
mais qui doivent en réalité respecter des contraintes connues seulement de l’utilisateur.
Prenons un exemple, on s’intéresse au langageL5 ={l.4.c.1.c.3.l.7|l∈L,c∈C}
Autrement dit, les mots de passe valides contiennent le code secret avec en plus une lettrelet un
chiffrecque l’utilisateur choisira librement au moment de rentrer son mot de passe et qu’il doit repéter
au bon emplacement dans le mot de passe. L’utilisateur est bien sûr le seul à savoir quand placer ces
deux symboles libres.
Q31.Dessinez un automateA5 qui reconnaît le langageL5 1.5pt
1. 01234567890123456789 casse le mot de passe puisque le 012345678901234567est accepté