Solution - TD Feuille 5 - Résiduels et minimisation des

automates

Informatique Théorique 2 - Unité J1INPW11

Licence 3 - Université de Bordeaux

Solution de l’exercice 1 :
1. On a :
— L−1
1 · L2 = {ǫ, a, b, ab, ba}.
— L−1
2 · L1 = {ǫ, a, bab, abab, ababab}.
— ǫ−1 · L1 = L1 .
— [(a + b)∗ ]−1 · L1 = {ǫ, a, b, aa, ab, ba, bab, abab, babab, ababab, aababab}.
— ∅−1 · L1 = ∅.
2. Si ǫ ∈ L1 alors L2 ⊆ L−1 −1
1 · L2 . Si L2 = ∅ alors L1 · L2 = ∅.

Solution de l’exercice 2 :
1. On donne les résiduels pour chaque langage. On commence par L1 = a∗ b∗ qui a trois
résiduels. Soit w un mot :
— Si w ∈ a∗ alors Rw = L1 = a∗ b∗ . Par exemple Rǫ = a∗ b∗ .
— Si w 6∈ a∗ et w ∈ a∗ b∗ alors Rw = b∗ . Par exemple Rb = b∗ .
— Sinon Rw = ∅.
On passe maintenant à L2 = a∗ ba + b∗ aba. Ce second langage possède neuf résiduels.
Soit w un mot :
— Si w = ǫ, Rǫ = L2 = a∗ ba + b∗ aba.
— Si w ∈ aa∗ alors Rw = a∗ ba.
— Si w ∈ aa∗ b + b∗ ab, alors Rw = {a}.
— Si w = b, alors Rb = a + b∗ aba.
— Si w = ba, alors Rba = ǫ + ba.
— Si w ∈ bbb∗ , alors Rw = b∗ aba.
— Si w ∈ bbb∗ a, alors Rw = ba.
— Si w ∈ L2 , alors Rw = ǫ.
— Sinon Rw = ∅.
Pour le langage L3 = {an bn | n ≥ 0}, on va voir qu’on a une infinité de résiduels. Soit w
un mot :
— Si il existe i ≥ 0 tel que w = ai alors Rai = {aj bk | i + j = k}.
— Si il existe i > j ≥ 0 tel que w = ai bj alors Rw = {bi−j }.
— Sinon Rw = ∅.

1
 2. On sait qu’un langage est régulier si et seulement si il a un nombre fini de résiduels.
On peut donc d’ores et déjà conclure que seuls L1 et L2 sont réguliers. De plus on sait
que l’automate minimal d’un langage régulier a pour ensemble d’états l’ensemble des
résiduels du langage, chaque mot étant accepté par l’état correspondant à son résiduel.
Le calcul effectué à la question précédente nous permet donc de donner les automates
minimaux de L1 et L2 . On commence avec L1 , on étiquette chaque état avec son rési-
duel. C’est-à-dire que l’étiquette de chaque état représente l’ensemble des mots qui sont
acceptés par l’automate en partant de cet état :
a b
b
a ∗ b∗ b∗

On donne maintenant l’automate des résiduels de L2 :

b
a
b b∗ aba ba

b a
a∗ ba + b∗ aba a + b∗ aba ǫ + ba b
b
a

a b a
a∗ ba a ǫ

Solution de l’exercice 3 :
On souhaite comparer les quatres langages. Pour cela on commence par calculer l’automate
minimal de chaque langage. Il suffira ensuite de comparer ces automates. En effet l’automate
minimal est un objet canonique ne dépendant que du langage, deux langages sont donc égaux
si ils ont le même automate minimal (modulo renommage des états).

Expression Rationnelle (ab∗ a + b(a + b))∗ . On commence par construire un automate par la
méthode de Glushkov :

b 2 b a
1 a a
a
a 3
0 b
b
a 5
b
4
b 6
b

2
 On souhaite maintenant construire l’automate minimal du langage. Pour celà il faut
d’abord déterminiser puis minimiser l’automate ci-dessus. Par chance on a déjà un automate
déterministe, on peut donc directement passer à l’algorithme de Moore. On donne ci-dessous
la partition finale obtenue après stabilisation de l’algorithme :

b 0 b a
0 a a
a
a 1
1 b
b
a 1
b
2
b 1
b

On termine en fusionnant les états équivalents pour obtenir l’automate minimal :

0 b
a
a
1
b

a,b
2

Figure 1 – Automate minimal pour (ab∗ a + b(a + b))∗

Expression Rationnelle (ab + b(a + b))∗ . On commence par construire un automate par la
méthode de Glushkov :

b
1 2 a
a
a
b
0
b
a 5
b
4
b 6
b

3
 Encore une fois, l’automate que nous donne la méthode de Glushkov est déjà détermi-
niste. On peut donc directement appliquer l’algorithme de Moore sans passer par l’étape de
déterminisation. On obtient la partition suivante à la fin de l’algorithme :

b
0 1 a
a
a
b
1
b
a 1
b
2
b 1
b

On fusionne ensuite les états équivalents ce qui donne l’automate minimal suivant :

0
a

b
1
b

a,b
2

Figure 2 – Automate minimal pour (ab + b(a + b))∗

Automate A1 . Pour minimiser A1 , on doit d’abord le déterminiser. On donne ci dessous le

résultat de l’algorithme de déterminisation :

a b
{0, 5} {1} {2}
a,b
b a b
b
{1, 4} {2, 3}
a

On peut maintenant appliquer l’algorithme de Moore. La partition finale obtenue est re-
présentée ci-dessous :

a b
2 1 0
a,b
b a b
b
1 0
a

4
 L’automate minimal s’obtient ensuite en fusionnant les états équivalents :

2
a

b
1
b

a,b
0

Figure 3 – Automate minimal pour A1

Automate A2 . L’automate A2 est déjà déterministe, on passe donc directement à l’algorithme

de Moore. La partition obtenue est la suivante :
b b
1 a 2 b 1
a a
a a a

0 b 0 b 0

Après fusion on obtient l’automate minimal suivant :

0 b
a
a
1
b

a,b
2

Figure 4 – Automate minimal pour A2

Maintenant que nous avons construit l’automate minimal pour chacun des quatre langages,
on peut les comparer. On constate que modulo renommage des états les langages de A1 et
(ab + b(a + b))∗ ont le même automate minimal et sont donc égaux. Il en va de même pour les
langages de A2 et (ab∗ a + b(a + b))∗ .

Solution de l’exercice 4 :
On observe que pour cet exercice, les deux automates à minimiser sont déjà déterministes.
En conséquence on peut sauter l’étape de déterminisation et directement passer à la minimi-
sation. On va détailler l’algorithme de Moore en faisant un schéma pour chaque étape :

Automate A3 . On commence par A3 , la partition initiale est donnée par les états finaux (ce
sont les seuls états qui acceptent le mot vide) :

5
 ab ab
00 01
1 a ab b 1
ab a ab ab
10 a 01 10 01
a
b 0 1 b 0 1
ab a ab a a
00 01
a b b b b
0 1

On met la partition à jour :

ab ab
20 23
1 a ab b 3
ab a ab ab
32 a 23 32 23
a
b 2 3 b 2 3
ab a ab a a
20 23
a b b b b
0 3

On observe que la partition n’est plus raffinée, on a donc bien les classes de Nérode.
En fusionnant les états qui se trouvent dans la même classe on obtient l’automate minimal
suivant :

1 a b
a
b 2 3
a
a b
0

Automate A4 . On passe maintenant à l’automate A4 dont voici la partition initiale :

ab ab ab ab
00 a ∅1 b 01 a ∅0
0 0 1 0

b b
b a
ab ab ab b ab
00 10 00 ∅1
0 0 0 0
b b a

b
a

6
 On met à jour la partition :

ab ab ab ab
24 a ∅1 b 32 a ∅0
0 2 1 3

b b
b a
ab ab ab b ab
24 10 20 ∅1
0 4 0 2
b b a

b
a

On met à nouveau à jour la partition :

ab ab ab ab
24 a ∅1 b 32 a ∅5
0 2 1 3

b b
b a
ab ab ab b ab
24 15 20 ∅1
0 4 5 2
b b a

b
a

La partition est maintenant stable. Elle décrit donc les classes de Nérode. En fusionnant
les états équivalents on obtient l’automate minimal suivant :

a
1 3

b b
a
b

0 4 5 2
b b a

b
a

Solution de l’exercice 5 :
Le premier automate (lecture du mot de gauche à droite) est déjà minimal. Le moyen le plus
simple de s’en apercevoir est d’utiliser l’algorithme du double renversement : l’automate étant
déterministe et co-déterministe (l’automate miroir est lui même déterministe), cet algorithme
laisse l’automate inchangé.

7
 On va confirmer ce résultat une seconde fois en appliquant l’algorithme de Moore au second
automate (lecture du mot de droite à gauche) pour constater qu’on obtient bien le miroir du
premier automate. Voici la partition initiale en états finaux et non finaux :

01 01
10 0 10
1 1
0
1
01
00 1
0
0 0 1 1
0 01
1
01
01
01 1
0
0 0
0 01
00

On met à jour la partition :

01 01
12 0 12
1 1
0
1
01
20 1
0
0 2 1 1
0 01
1
01
01
01 1
0
2 0
0 01
20

La partition n’étant plus raffinée elle représente les classes de Nérode, on obient donc l’au-
tomate minimal en fusionnant les états équivalents. On constate bien qu’on obtient l’automate
miroir du premier automate.

0 1 0 1

1 2 0
1 0

8
Solution de l’exercice 6 :
On sait que pour un langage régulier L chaque résiduel correspond à un état de l’automate
minimal (plus le résiduel vide si l’automate n’est pas complet). En particulier pour chaque
état q, le résiduel associé est égal à l’ensemble des mots acceptés par l’automate en partant de
q. C’est aussi le résiduel Rw pour tout mot w dont le calcul arrive dans l’état q sur l’automate
minimal. L’automate minimal donne donc une description complète des résiduels du langage
associé.
On illustre cette propriété en reprenant l’automate minimal du langage de A3 et en rempla-
çant l’étiquette de chaque état par une expression rationnelle pour le résiduel correspondant :

ǫ + b∗ (ab∗ ab∗ )+ a b
a
b b∗ ab∗ (ab∗ ab∗ )∗ b∗ (ab∗ ab∗ )∗
a
a
b∗ ab∗ ab∗ (ab∗ ab∗ )∗ b

Observons que l’automate est complet, il n’y a donc pas de résiduel vide pour ce langage.

Solution de l’exercice 7 :
1. On donne un automate non déterministe à n états pour L :
a, b
a a
a
1 2 ··· n

b b

2. On souhaite montrer qu’il n’existe pas d’automate déterministe ayant moins de 2n−1
états pour le langage L. On va donc montrer que l’automate minimal a plus de 2n−1 .
On rappelle que chaque état de l’automate minimal correspond à un résiduel non vide
du langage. Il nous suffit donc de montrer que L possède plus de 2n−1 résiduels. C’est
ce que nous allons faire.
Observons tout d’abord que L est le langage des mots dont la (n − 1)-ème lettre en
partant de la droite est un a.
Considérons l’ensemble {1, 2, . . . , n − 1}, à chaque sous ensemble E ⊆ {1, 2, . . . , n − 1}
on associe un mot wE de la façon suivante :
— wE a n − 1 lettres.
— si i ∈ E alors la i-ème lettre de wE en partant de la droite est un a.
— si i 6∈ E alors la i-ème lettre de wE en partant de la droite est un b.
Par exemple w{1} = bn−2 a et w{2,n−1} = abn−4 ab. On va montrer que si E 6= E ′ alors
RwE 6= RwE ′ .
Si E 6= E ′ alors il existe forcément i ∈ {1, 2, . . . , n} tel que i ∈ E et i 6∈ E ′ ou tel que
i ∈ E ′ et i 6∈ E. Les deux cas étant symétriques, on suppose qu’on est dans le premier.
Par définition, wE contient un a à la i-ème position en partant de la droite et wE ′

9
 contient un b à la i-ème position en partant de la droite. Il en découle que wE an−1−i ∈ L
et wE ′ an−1−i 6∈ L, donc an−1−i ∈ RwE et an−1−i 6∈ RwE ′ . On en déduit que RwE 6= RwE ′
De plus pour tout E ⊆ {1, 2, . . . , n − 1}, on constate que an−1 ∈ RwE . Donc L a au
moins autant de résiduels non vides qu’il y a de sous-ensembles E ⊆ {1, 2, . . . , n − 1},
c’est-à-dire 2n−1 .

Solution de l’exercice 8 :
De manière générale il y a seize configurations possibles du plateau. On peut cependant
réduire ce nombre en constatant que certaines conditions sont équivalentes. Tout d’abord,
puisque la condition de victoire impose seulement d’avoir tous les verres dans le même sens
mais n’impose rien sur ce sens, on constate que retourner les quatres verres laisse le barman
dans une situation équivalente pour le reste du jeu. Par exemple les deux configurations
suivantes sont équivalentes :

Grâce à cette observation, on divise déjà le nombre de configurations par deux ce qui nous
laisse les huit configurations suivantes :

De plus, le contrôle de la rotation est laissé à l’adversaire, le barman ne sait donc pas
quelle face lui est présentée. En particulier celà signifie que si il décide de retourner un verre
il ne contrôle pas lequel il retourne. Si il décide de retourner deux verres, il n’a que deux
choix : retourner deux verres adjacents (sur une même face) ou deux verres opposés (sur une
même diagonale). Chacune de ces actions peut avoir plusieurs conséquences suivant les verres
qui sont en pratique retournés, mais ces ensembles de conséquences ne dépendent pas de la
rotation du plateau. On peut donc réduire encore le nombre de configurations équivalentes
pour le barman à quatre :

Configuration 0 Configuration 1 Configuration 2.1 Configuration 2.2

Comme on l’a dit plus haut, le barman a trois actions à sa disposition : retourner un
seul verre (action 1), retourner deux verres adjacents (action 2a) ou retourner deux verres
opposés (action 2o). On représente les conséquences possibles de chaques action pour chaque
configuration dans l’automate suivant, les états sont les quatre configurations et l’alphabet est
l’ensemble des actions possibles {1, 2a, 2o} :

10
 2a
2o

1
2o 1 1

2o
2a
2a

2a

Notons qu’il n’y a aucune action possible depuis la configuration gagnante puisque le
barman a gagné (et s’arrête donc de jouer). On souhaite savoir si le barman a une stratégie
gagnante, c’est à dire une suite d’actions qui, quelle que soit la configuration initiale, mène à
coup sûr dans la configuration gagnante. Pour celà on va déterminiser l’automate. En effet si
on trouve un chemin de l’état {0, 1, 2.1, 2.2} jusqu’à l’état {0} dans le déterminisé celà signifie
qu’il existe une séquence d’actions qui nous mène à coup sûr en 0 ou dans un état bloquant
(0 qui est le seul état bloquant).

{0}

2o 2a,2o
1
{0, 2.2} {1} 2a {0, 1, 2.1, 2.2} 1

2a 2o 1 2o 1
2a,2o
2a 1 1
2a {2.1} 1 1 {0, 1, 2.1}
2o 2a 2o
1
1 2o 2a
{0, 2.1} {0, 2.1, 2.2} {0, 1} {0, 1, 2.2} {1, 2.1}
2o 2a
2a 2o

Observons maintenant que depuis l’état {0, 1, 2.1, 2.2}, en lisant le mot 2o·2a·2o·1·2o·2a·2o,
on arrive dans l’état {0}. Autrement dit, dans notre automate original, partant de n’importe
quelle situation, si le barman joue la séquence 2o · 2a · 2o · 1 · 2o · 2a · 2o, soit il se retrouve à un
moment dans état bloquant (i.e. la configuration gagnante qui est le seul état bloquant), soit
il arrive dans la configuration gagnante après le dernier coup. Dans tous les cas le barman est
sûr d’atteindre la configuration gagnante en jouant cette séquence, c’est donc une stratégie
gagnante.

11
 {0}

2o 2a,2o
1
{0, 2.2} {1} 2a {0, 1, 2.1, 2.2} 1

2a 2o 1 2o 1
2a,2o
2a 1 1
2a {2.1} 1 1 {0, 1, 2.1}
2o 2a 2o
1
1 2o 2a
{0, 2.1} {0, 2.1, 2.2} {0, 1} {0, 1, 2.2} {1, 2.1}
2o 2a
2a 2o

12