Théorie des langages : Exercices langages automates non determinisme grammaires
Télécharger PDFLangages, Automates, Non-déterminisme et Grammaires
Durée : 2 heures, sans documents.
Tous les appareils électroniques sont interdits à l'exception des montres.
Le barème est donné à titre indicatif.
Le sujet comporte 4 exercices indépendants.
Ne répondez pas sur le sujet ; répondez sur votre copie.
Exercice 1 : Questions de cours (7 points)
Justifiez chacune de vos réponses de façon précise (3 ou 4 lignes suffisent pour démontrer votre réponse).
Chaque question est notée de la façon suivante : 1 point pour la réponse et 3 points pour la justification.
1.1 Élimination des ε et déterminisme
Q1. Donnez l'automate obtenu par élimination des transitions ε dans l'automate ci-dessous.
Q2. L'automate obtenu est-il déterministe ?
Q3. Un automate fini contenant des transitions ε est-il forcément non-déterministe ?
Q4. L'élimination des transitions ε produit-elle forcément un automate non-déterministe ?
1.2 Complémentaire, produit et restriction
On considère l'alphabet Σ = {a, b, c}.
Q5. Qu'est-ce qu'un langage sur l'alphabet Σ ?
Q6. Donnez un automate qui reconnaît le langage Σ*.
Q7. Quel est le plus grand langage sur l'alphabet Σ ?
Q8. Donnez un automate qui reconnaît le langage complémentaire de Σ*.
Q9. Complétez la définition de Σ+ :
Σ+ = {tous les mots sur Σ de longueur ≥ 1} et donnez un automate qui reconnaît le langage Σ+.
Q10. Donnez un automate qui reconnaît Σ+.
Q11. Décrivez en une phrase le langage reconnu par l'automate de la question précédente.
Q12. Donnez un automate minimal qui reconnaît ce langage.
Q13. Donnez un automate qui reconnaît le langage Σ* \ Σ+.
Q14. Donnez un automate qui reconnaît le complémentaire de ce langage.
Q15. Décrivez en une phrase le langage reconnu par l'automate de la question précédente.
Q16. Quel est le langage reconnu par le produit des automates A1 et A2 ci-dessous ?
A1 :
q0 → a
q1 → b
q2 → c
q3 → d
q4 → f
A2 :
q0 → a
q1 → d
q2 → b
q3 → c
q4 → f
1.3 Langage régulier, langage irrégulier
Q17. Un langage fini peut-il être régulier ?
Q18. Si L ∩ R est irrégulier et R un langage régulier, que peut-on dire de L ? Donnez une preuve.
Q19. Si L est irrégulier alors L est.................... Donnez une preuve.
Q20. Soit A1 et A2 des automates à états finis ; L1 un langage reconnu par A1 et L2 le langage reconnu par A2. Expliquez le principe de construction de l'automate qui reconnaît le langage L1 \ L2 à l'aide des opérateurs sur les automates.
Q21. Si le langage L \ L' est irrégulier et si L' est régulier alors L est.................... Complétez la preuve.
Preuve : Rappelons que L \ L' est défini comme {tous les mots de L qui ne sont pas dans L'}. Puisque L' est régulier, alors L' est un langage régulier. Si L \ L' est irrégulier, alors L est un langage non régulier (d'après la question 18).
1.4 Grammaires et automates
Q25. Donnez une grammaire de type 3 (c'est-à-dire régulière) qui génère le langage c*.
Q26. Donnez une grammaire qui génère le langage (a + c)*.b.
Q27. Donnez un automate à pile qui reconnaît le langage des palindromes de la forme ω.c* où ω ∈ Σ* avec Σ = {a, b}.
Q28. Cet automate est-il déterministe ? Justifiez votre réponse.
Q29. Donnez une grammaire qui génère le même langage.
Q30. Donnez une grammaire qui génère le langage reconnu par l'automate suivant :
q0 → a
q1 → b
q2 → c
Q31. Donnez l'expression régulière correspondant à l'automate précédent. Détaillez les étapes de résolution.
Exercice 2 : Langage irrégulier (3 points)
Q32. Montrez que le langage {0^n.1^k.0^m | k, n, m ∈ N} est irrégulier en utilisant le lemme de pompage.
Rappel : Il faut choisir un mot ω qui vous facilite la démonstration et il faut que ce mot dépende de la longueur n.
Exercice 3 : Preuve de correction partielle de l'algorithme d'exponentiation rapide (6 points)
Algorithme x := A ; y := N ; r := 1 ;
while (y > 0) { if (y % 2 == 0) { x := x * x ; y := y / 2 ; } else { r := r * x ; y := y - 1 ; } }
Q33. Donnez les transitions de l'automate pour lequel il correspond au programme précédent.
Adoptez la présentation ci-dessous mais répondez sur votre copie.
q0 → A
q1 → x
q2 → y
q3 → r
q4 → 1
Q34. Complétez l'exécution de l'automate en adoptant la présentation ci-dessous. Répondez sur votre copie.
a) Pour les valeurs A = 3, N = 3 et état q0 :
x : ...................
y : ...................
r : ....................
b) Même question pour les valeurs A = 2, N = 0.
Q35. Donnez la propriété de correction qui exprime qu'à la sortie de l'automate la variable r contient la valeur de A^N.
Q36. Preuve de correction partielle (soignez la rédaction !)
Donnez et démontrez l'implication associée à chaque transition et donnez les 5 invariants (ψ0, ψ1, ψ2, ψ3, ψ4) associés aux états q0, q1, q2, q3, q4.
Q37. En déduire les conditions d'utilisation du programme.
Exercice 4 : Politiques de sécurité (4 points)
On considère un réseau constitué de deux parties : un réseau sûr car protégé par un pare-feu et Internet.
Pour contrôler l'usage des machines sur le réseau, on installe sur chaque compte utilisateur un moniteur de sécurité qui observe les commandes suivantes :
login qui lance une session principale
quit qui ferme la session principale
rlogin qui permet d'ouvrir une connexion sur une machine du réseau protégé
ssh qui permet d'ouvrir une session avec encryption des échanges sur une machine hors du réseau protégé
exit qui permet de fermer toutes les sessions en cours (sauf la session principale).
Dans cet exercice, on considère que les autres commandes que l'utilisateur peut utiliser ne sont pas soumises au contrôle de sécurité.
Principe d'un moniteur de sécurité : Un moniteur de sécurité prend en entrée une politique de sécurité P décrite sous la forme d'une expression régulière ou d'un automate d'états finis ou d'un automate à une pile déterministe. Il autorise uniquement les séquences de commandes qui appartiennent au langage L(P).
Q38. Alphabet Σ considéré par les politiques de sécurité sur ce réseau.
Σ = {login, quit, rlogin, ssh, exit}.
Q39. Exemples de séquences de commandes respectant ou non les contraintes de la politique de sécurité n°1.
Exemples respectant la politique n°1 :
login, rlogin, exit, quit
login, ssh, exit, quit
login, rlogin, ssh, exit, exit, quit
Exemples ne respectant pas la politique n°1 :
login, ssh, rlogin, quit
rlogin, ssh, exit
login, ssh, rlogin, exit, quit
Q40. Expression régulière P1 décrivant la politique de sécurité n°1.
P1 = (login.(rlogin.exit)* + ssh.exit)*.quit
Q41. Automate à états finis P2 décrivant la politique de sécurité n°2.
Les étapes de construction sont :
1. Décrire les états initiaux et finaux.
2. Ajouter des transitions pour les commandes login et quit.
3. Limiter les sessions rlogin à une seule ouverture simultanée.
4. Limiter les sessions ssh à deux ouvertures simultanées.
5. Interdire les états où rlogin et ssh sont simultanément ouverts.
Q42. Automate P3 décrivant la politique de sécurité n°3.
Les étapes de construction sont :
1. Décrire les états initiaux et finaux.
2. Ajouter des transitions pour les commandes login et quit.
3. Autoriser uniquement les sessions ssh.
4. Permettre plusieurs sessions ssh simultanées.
5. Exiger une commande exit pour chaque session ssh ouverte.
FAQ
Q : Qu'est-ce qu'un langage régulier ?
R : Un langage régulier est un langage qui peut être reconnu par un automate fini. Il est défini par une expression régulière.
Q : Comment reconnaître un langage complémentaire ?
R : Le complémentaire d'un langage L sur un alphabet Σ est Σ* \ L. Pour le reconnaître, on peut compléter l'automate de L pour qu'il reconnaisse toutes les séquences non reconnues par L.
Q : Qu'est-ce que le lemme de pompage ?
R : Le lemme de pompage est un outil utilisé pour prouver qu'un langage n'est pas régulier. Il stipule que tout mot suffisamment long peut être décomposé en trois parties x, y, z telles que xy^iz ∈ L pour tout i ≥ 0.