Automates - TD Option informatique - MP
Exercice 1
Déterminer des diagrammes de transition d’AFD sur Σ = {a, b} pour les langages suivants. On essaiera
de minimiser le nombre d’états.
1. L’ensemble des mots ayant aab comme sous-mot.
2. L’ensemble des mots ayant aab comme suffixe.
3. L’ensemble des mots ayant aab comme préfixe.
4. L’ensemble des mots ayant aab comme facteur.
5. L’ensemble des mots ne contenant pas aab comme facteur.
6. L’ensemble des mots dont la dernière lettre apparaît au moins deux fois dans le mot.
Exercice 2
Déterminer des diagrammes de transition d’AFD sur Σ = {0, 1} pour les langages suivants :
1. l’ensemble des mots qui sont la représentation binaire d’un nombre pair ;
2. l’ensemble des mots qui sont la représentation binaire d’un multiple de 3. On prouvera la correction
de l’automate ;
3. l’ensemble des mots qui sont la représentation binaire d’un multiple de 6.
Exercice 3
Déterminer des diagrammes de transition d’AFD sur Σ = {0, 1} pour les langages suivants :
1. l’ensemble des mots qui sont la représentation binaire d’un multiple de 5 ;
2. L’ensemble des mots qui sont la représentation binaire inverse d’un multiple de 5.
Exercice 4
Montrer qu’il existe un langage reconnaissable L tel que tout AFD reconnaissant L possède au moins
deux états finaux. Est-ce vrai si on considère des AFND ?
Exercice 5
Soit A un AFD à n états. Montrer que si L(A) ̸= ∅ si et seulement si L(A) contient un mot de taille
strictement inférieure à n.
Exercice 6
Déterminiser l’automate suivant en construisant l’automate des parties :
a a
a, b a, b
q0 q1 q2
Exercice 7
Montrer que si A est un AFND avec ε-transitions, alors il existe un AFD B tel que L(A) = L(B).
N. Carré Page 1 Louis-le-Grand
Automates - TD Option informatique - MP
Exercice 8
Déterminiser l’automate ci-après. On commencera par construire un AFND équivalent par clôture avant
ou arrière.
ε a b c
→ q0 {q1 , q2 } ∅ {q1 } {q2 }
q1 ∅ {q0 } {q2 } {q0 , q1 }
q2 → ∅ ∅ ∅ ∅
Exercice 9
Soit Σ = {a, b}. Pour n ∈ N, on pose Σ<n l’ensemble des mots de taille < n.
1. Montrer que pour tout n ∈ N, Σ<n est reconnaissable.
Pour n ∈ N, on considère Ln = (Σ<n a)∗ Σn .
2. Déterminer un automate non déterministe à n + 1 états reconnaissant L (on pourra commencer
par n = 1, n = 2, n = 3).
3. Montrer que si A est un automate déterministe complet reconnaissant L, alors il contient au moins
2n+1 états.
Exercice 10
Décrire un algorithme qui, étant donné un AFD A = (Q, Σ, δ, q0 , F ), détermine si L(A) est infini, fini
non vide ou vide. Déterminer sa complexité temporelle.
Exercice 11
On représente un automate non déterministe par listes d’adjacence, un mot étant assimilé à un objet
de type string :
type afnd = {initiaux : bool array; finaux : bool array;
sigma : int; delta : (int * int) list array};;
type mot = string;;
1. Écrire une fonction delta_ens : afnd -> bool array -> char -> bool array qui calcule
l’image d’un ensemble d’états (donné par un tableau de booléens) lors de la lecture d’une lettre.
2. En déduire une fonction delta_etoile_ens : afnd -> bool array -> string -> bool array
qui calcule l’image d’un ensemble d’états lors de la lecture d’un mot (donné par une liste d’entiers),
puis une fonction reconnu : afnd -> string -> bool qui teste si un mot est reconnu.
N. Carré Page 2 Louis-le-Grand
