Examen final
Licence Sciences et Technologies INF 232: Langages et Automates
Université Joseph Fourier L2, 2015/2016
Rappel à propos des consignes et quelques conseils et remarques
— Durée : 2 heures.
— Pas de sortie avant 30 minutes. Pas d’entrée après 30 minutes.
— Tout document du cours ou du TD est autorisé. Tout autre document est interdit.
— Tout dispositif électronique est interdit (calculette, téléphone, tablette, etc.).
— Le soin de votre copie sera pris en compte (-1 point si manque de soin).
— Les exercices sont indépendants.
— Le barème est donné à titre indicatif.
Exercice 1 Vrai/Faux (1 points)
1. Plus le nombre d’états est grand dans un automate d’états finis, plus celui-ci reconnaı̂t de mots.
2. Dans la méthode de Floyd, tout programme est partiellement correct par rapport à n’importe quelle
spécification qui s’écrit (Faux, P), où P est un prédicat quelconque.
Exercice 2 Des automates à trouver (2 points)
Soit Σ = {0, 1}.
1. Soit L1 l’ensemble des mots dans Σ∗ qui contiennent 010. Donner un automate A1 d’états finis
(déterministe ou non-déterministe) qui reconnait L1 .
2. Soit L2 l’ensemble des mots qui ne contiennent pas 010. Construire à partir de l’automate A1 de la
première question un automate d’états finis A2 qui reconnait le langage L2 .
3. Soit L3 l’ensemble des mots qui commencent par 01 ou 10. Donner un automate d’états finis
(déterministe ou non-déterministe) A3 qui reconnait L3 .
4. Soit L4 l’ensemble des mots qui commencent par 01 ou 10 et qui ne contiennent pas 010. Construire
à partir des automates A2 et A3 un automate qui reconnait L4 .
Exercice 3 Expression régulière et automate (3 points)
1. Donner une expression régulière représentant l’ensemble des mots avec un nombre pair de zéros
et un nombre pair de uns, en définissant d’abord un automate reconnaissant ce langage puis en
utilisant la méthode associant les équations aux états.
Exercice 4 Déterminisation et minimisation (4 points)
Soit Σ = {a, b}. Déterminiser l’automate de la Figure 1 et minimiser l’automate obtenu.
Exercice 5 Langages non réguliers (5 points)
1. Montrer que le langage {a2n b2n | n ≥ 0} n’est pas régulier en se servant du lemme d’itération.
2. En utilisant le résultat de la question précédente, montrer que : {ω ∈ {a, b}∗ | |ω|a = |ω|b | = 2k, k ≥
0} n’est pas régulier.
3. En utilisant les résultats des questions précédentes, montrer que : {ai bj c2k | i + j = 2k} n’est pas
régulier.
1
2
a b
1
a
a b a a
0 3 4 5 6
b
b
b a
7 8 9
b
Figure 1: Un automate à déterminiser
i := 0 i < n −→ s := t
q0 q1 q2
i ≥ n −→ r := s ∗ t/4 t := s + 2 ∗ (i + 1) + 1
i := i + 1
q3
qt
Figure 2: Un automate étendu
Exercice 6 Méthode de Floyd (5 points)
On considère l’automate étendu de la Figure 2, où q0 est l’état initial et qt est l’état terminal.
1. Calculer les exécutions de cet automate dans les états initiaux suivants :
(a) σ(t) = 1, σ(s) = 0 et σ(n) = 3
(b) σ(t) = 1, σ(s) = 0 et σ(n) = 5
(c) σ(t) = 1, σ(s) = 0 et σ(n) = 6
2. Montrer, en utilisant la méthode de Floyd, que l’automate satisfait la spécification
n2 (n + 1)2
(P, Q) où P ≡ s = 0 ∧ t = 1 ∧ n ≥ 0 et Q ≡ r =
4
Indication : Pour Pq1 , compléter le prédicat suivant :
s = i··· ∧ t = (i + · · · )2 ∧ · · ·