Langages 2 – TD1
langages réguliers — algorithme de Brzozowski
2024-2025
L’objectif de ce TD est d’exécuter, comprendre et démontrer l’algorithme de minimisation de Brzozowski.
Dans le premier exercice, il s’agira de démontrer une caractérisation des automates minimaux. Les
exercices 2 et 3 rappelleront deux transformations connus des automates, à savoir le renversement (qui
←−−−
transforme un automate non-déterministe A en automate non-déterministe B tel que L (B) = L (A)) et la
déterminisation (qui transforme un automate non-déterministe A en un automate déterministe B équivalent
à A). Des propriétés sur les résultats de ces deux algorithmes seront démontrés. Enfin, l’algorithme de
minimisation de Brzozowski, qui utilise le renversement et la déterminisation, sera étudié dans l’exercice 4.
En particulier, en se basant sur les résultats obtenus aux exercices précédents, il sera démontré que le
résultat de cet algorithme est bien l’automate minimal équivalent à l’automate d’entrée.
Un automate, nommé A1 est donné en figure 1 (à la fin du sujet). Il est utilisé dans les différents
exercices pour illustrer les notions et les algorithmes.
Exercise 1 Automate minimal
On rappelle qu’un état q est dit accessible s’il existe un mot permettant de le rejoindre depuis un état
initial. Il est dit inaccessible sinon. De façon similaire, q est dit co-accessible s’il existe un mot permettant
de rejoindre un état final depuis q.
1. On s’intéresse à l’automate A1 donné en figure 1.
a) L’état i est-il accessible ? Et f ?
b) Trouver un (autre) état accessible de A1 .
c) L’état f est-il co-accessible ? Et i ?
d) Trouver un (autre) état co-accessible de A1 .
e) Y-a-t-il un état qui n’est pas co-accessible ?
f) Trouver un état inaccessible de A1 .
g) Quel langage 1 est reconnu par l’automate obtenu depuis A1 en supprimant l’état inaccessible
(et toutes les transitions le faisant intervenir) de la question précédente ?
2. Démontrer de façon générale le lemme suivant :
Lemme 1. Si un automate déterministe admet un état inaccessible, alors il n’est pas minimal.
3. Proposer et démontrer un lemme (Lemme 2.) pour traiter du cas de la présence d’un état qui
n’est pas co-accessible.
Étant donné deux états p et q de A, et un mot u, on dit que u distingue p et q, s’il peut être accepté
depuis p mais pas depuis q ou, inversement, depuis q mais pas depuis p. On dit que p et q sont distingables
s’il existe un tel mot u qui les distingue, et qu’ils sont indistingables sinon.
4. On s’intéresse à l’automate A1 donné en figure 1.
a) Trouver deux états distingables de A1 et un mot qui les distingue.
b) Parmi les paires d’états suivantes, lesquelles sont indistingables ? Justifier. 2
• c et d • e et f • j et f • a et b • g et h
c) Trouver une (autre) paire d’états indistingables et accessibles de A1 .
d) Montrer qu’il est possible de retirer de A1 l’un des deux états indistingables trouvés à la
question précédente, sans changer le langage reconnu, à condition d’adapter quelque peu la
fonction de transition.
1. Il s’agit de décrire le langage en fonction du langage reconnu par A1 .
2. Si prouver que deux états sont distingables est aisé (il suffit de trouver un mot qui les distingue), il est plus compliqué
de prouver que deux états sont indistingables. Un outil pratique (mais pas toujours suffisant) est de trouver des mots de
synchronisant. Si, pour un mot w, l’ensemble des états accessibles depuis p en lisant w est égal à l’ensemble des états
accessibles depuis q en lisant w, alors pour tout mot u, le mot wu est accepté depuis p si et seulement si il est accepté
depuis q. On dit que w synchronise p et q.
1
5. Montrer de façon générale le lemme suivant.
Lemme 3. Si un automate déterministe admet une paire d’états indistingables, alors il n’est pas
minimal.
6. On cherche désormais à prouver le résultat suivant :
Lemme 4. Un automate déterministe est minimal si et seulement si :
1. ses états sont tous accessibles ;
2. ses états sont tous co-accessibles ;
3. il n’admet pas de paire d’états indistingables.
a) Déduire des lemmes 1 à 3 le sens directe de l’équivalence établie dans le lemme ( =⇒ ).
** b) On s’intéresse maintenant à la réciproque de ce résultat ( ⇐= ). On fixe un automate
déterministe A qui satisfait les trois conditions du lemme, et on note Q son ensemble d’états.
On procède par l’absurde. On suppose donc que A n’est pas minimal, autrement dit, qu’il
existe un automate déterministe B équivalent à A, qui possède strictement moins d’états
que A.
i – Montrer qu’il existe une famille (uq )q∈Q de mots distincts (q ≠ p =⇒ uq ̸= up ) telle
que pour chaque état q ∈ Q, le mot uq permet de rejoindre q depuis l’état initial (i.e.,
δ(i, uq ) = q où i est l’état initial de A).
ii – En observant le calcul de B sur chacun des mots uq , trouver la contradiction.
Exercise 2 Renversement
On considère l’automate A1 = (Q1 , Σ, I1 , F1 , δ1 ) donné en figure 1.
1. Accepte-t-il les mots suivants ?
a) ε b) 000001 c) 0001 d) 0111 e) 011110 f) 01111001
2. Transformer l’automate A1 , afin d’obtenir un automate A2 = (Q2 , Σ, I2 , F2 , δ2 ) qui reconnaît
←−−−−
L (A2 ) = L (A1 ), le miroir de L (A1 ).
a) Comment avez-vous procédé ?
b) Vérifier son comportement sur les miroirs des mots de la question précédente.
c) Combien d’états a A2 ?
d) Quels sont les états initiaux de A2 ?
e) Quels sont les états finaux de A2 ?
f) A2 est-il déterministe ?
3. Si l’on transforme A2 par la même méthode, qu’obtient-on ?
On note renverser cette transformation (renverser(A1 ) = A2 ). Soit A = (Q, Σ, I, F, δ) un automate
non-déterministe quelconque.
4. Donner la description formelle de renverser(A).
5. Si A est déterministe, a-t-on nécessairement que renverser(A) est déterministe ?
6. Démontrer formellement le lemme suivant :
Lemme 5. Si tous les états de A sont accessibles alors tous les états de renverser(A) sont
co-accessibles.
7. Écrire un lemme (Lemme 6.) pour le cas où les états de A seraient co-accessibles, et impliquant la
réciproque du lemme précédent (on rappelle que, d’après la question 3, renverser est involutive).
On dit qu’un état q est fortement distingable, s’il existe un mot vq qui le distingue de tout autre état.
** 8. Montrer que cette propriété est strictement plus forte que celle d’être distingable avec tout autre
état.
On dit qu’un automate A est co-déterministe si son renversé, renverser(A) est déterministe (l’automate A
lui-même n’est pas nécessairement déterministe).
9. Montrer le résultat suivant.
Lemme 7. Soit A un automate co-déterministe et p un de ses états. Si p est co-accessible alors p
est fortement distingable.
2
Exercise 3 Déterminisation
On note déterminiser(A) l’automate obtenu par déterminisation, selon la méthode des parties, d’un
automate A. On suppose que la déterminisation n’inclut jamais l’état ∅.
1. Construire A3 , l’automate obtenu par déterminisation (selon la méthode des parties) de l’automate
A2 = renverser(A1 ) obtenu à la question 2 de l’exercice 2.
a) A3 a-t-il des états inaccessibles ?
b) A3 a-t-il des états qui ne sont pas co-accessibles ?
c) A3 admet il une paire d’états indistingables ?
2. Expliquer pourquoi le résultat suivant est vrai.
Lemme 8. Si B est le résultat de la déterminisation d’un automate A (i.e., B = déterminiser(A))
alors les états de B sont accessibles.
3. Expliquer le résultat suivant :
Lemme 9. Si les états de A sont tous co-accessibles, alors les états de déterminiser(A) le sont
aussi.
Exercise 4 Minimisation par l’algorithme de Brzozowski
Il est finalement temps de s’intéresser à l’algorithme de Brzozowski, décrit ci-dessous :
Fonction minimiserB(A)
1 A1 ← A;
2 A2 ← renverser(A1 );
3 A3 ← déterminiser(A2 );
4 A4 ← renverser(A3 );
5 A5 ← déterminiser(A4 );
6 return A5 ;
1. Donner l’automate A4 , obtenu par renversement de l’automate A3 lui-même obtenu à la question 1
de l’exercice 3 (un renommage préalable des états est fortement suggéré).
2. Construire A5 = déterminiser(A4 ).
3. On a A5 = déterminiser(renverser(déterminiser(renverser(A1 )))). Vérifier que A5 est mini-
mal.
On s’intéresse maintenant à la preuve de l’algorithme. Chaque question doit être justifiée à l’aide des
lemmes établis dans les exercices précédents.
4. Vérifier que, quelque soit l’entrée A = A1 de l’algorithme, les automates intermédiaires A3 et A5
sont toujours déterministes, et leurs états sont toujours tous accessibles.
5. En déduire que dans A4 tous les états sont co-accessibles.
6. En déduire que dans A5 , tous les états sont accessibles et co-accessibles.
7. Montrer que dans A4 , chaque état est fortement distingable.
8. En déduire que dans A5 , toute paire d’états est distingable.
9. En déduire une preuve du théorème suivant :
Théorème 1. Pour tout automate non-déterministe A, l’automate minimiserB(A) (qui est égal à
déterminiser(renverser(déterminiser(renverser(A))))) est l’automate déterministe minimal
reconnaissant L (A).
3
1
a d
0, 1
0
0 1 c 1
1 0, 1
g 1
i f h
1
0, 1
1 1 e 0
1
0
b j 0, 1
0
Figure 1 – L’automate non-déterministe A1 sur l’alphabet {0, 1}. L’état i est initial, et les états f et j
sont acceptants.
