TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 1

Mathématiques pour l’informatique

Feuille de TD 2 solutions
Automates finis et expressions rationnelles.
Exercice 1
Soit E = ab*(ba + ab)*b expression rationnelle.
• Construire un automate correspondant à E.
• Déterminiser cet automate.
• Mininiser cet automate.

Solution
L’automate asynchrone AS1 construit selon les règles :

ε 6 a 7 b 8
ε ε
0 a 1 ε 2 b 3 ε 4 ε 5 12 ε 13 b 14
ε ε
ε
9 b 10 a 11

Déterminisation de AS1 :
Notation raccourcie : 0 = 0 ; 1 = 1,2,4,5,6,9,13 ; 3 = 2,3,4,5,6,9,13 ; 7 = 7 ; 8 = 5,6,8,9,12,13 ;
10 = 10 ; 11 = 5,6,9,11,12,13 ; 14 = 14
AD1 :

Etat a b
a,b
E 0 1 P
P
1 7 3 10 14
7 P 8 b
a 11
S 3 10 14 7 11 3 10 14 b a a
b
8 7 10 14 7
b
8 b 10.14
a
7 11 7 8 10 14 a
0 a 1 b b
S 10 14 11 P a
b
S a 8.10.14
8 10 14 7 11 10 14 3.10.14 a 7.11 b
11 7 10 14
P P P

Helen KASSEL, Boris VELIKSON 1 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 1

Version simplifiée de l’automate AS2 :

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

Déterminisation de la version simplifiée :

Notation raccourcie : non nécessaire
AD2
notation complète notation raccourcie
Etat a b Etat a b
E 0 125 P E 0' 1' P
125 3 12456 1' 3' 1'4'6'
S 12456 235 12456 S 1'4'6' 3'5' 1'4'6'
3 P 25 3' P 5'
25 3 46 5' 3' 4' 6'
235 3 2456 3'5' 3' 4' 5' 6'
S 46 25 P S 4' 6' 5' P
S 2456 235 46 S 4' 5' 6' 3'5' 4' 6'
P P P P P P

a,b

P
a b

b b b
3 25 46
a a
a
0 a 125 b b
a
b
a 2456
12456 a 235 a

On observe que la seule différence entre les AD1 et AD2 résultant de la version complète et
simplifiée, c’est que les états 8 et 11 de AD1 fusionnent (c’est l’état 25 de AD2).
Dans cette perspective, on peut soupçonner que le second automate est minimal. Pour voir si
c’est vrai, minimisons AD1, dont on sait déjà qu’il ne l’est pas.

Helen KASSEL, Boris VELIKSON 2 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 1

Minimisation de AD1 (nous n’allons plus utiliser les barres)

0={NT, T}={{0,1,7,8,(7,11),11,P}, {(3,10,14),(10,14),(8,10,14)}}
sous 0
Nom du
groupe a b a b
0 1 P NT NT
1 7 3 10 14 NT T
7 P 8 NT NT
NT 8 7 10 14 NT T
7 11 7 8 10 14 NT T
11 7 10 14 NT T
P P P NT NT

10 14 11 P NT NT
8 10
T 14 7 11 10 14 NT T
3 10
14 7 11 3 10 14 NT T

1 ={ {(0),(7),(P)}, {(1),(8),(7,11),(11)}, {(10,14)}, {(3,10,14), (8,10,14)} qu'on nomme,

dans l'ordre, {A, B, (10,14), C}
sous 1
Nom du
groupe a b a b
0 1 P B A travail terminé
A 7 P 8 A B travail terminé
P P P A A travail terminé

1 7 3 10 14 A C
8 7 10 14 A 10, 14
B
7 11 7 8 10 14 A C
11 7 10 14 A 10, 14

8 10 travail terminé
14 7 11 10 14 B 10, 14
C
3 10 travail terminé
14 7 11 3 10 14 B C

2 ={ (0), (7), (P), {(1), (7,11)}, {(8), (11)}, (10,14), (3,10,14), (8,10,14)}. Il en reste deux
groupes composés de deux états chacun, qu’on appelle par leur composition : {1, (7,11)} et
{8, 11}.

Helen KASSEL, Boris VELIKSON 3 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 2

sous 2
Nom du
groupe a b a b
1 7 3 10 14 7 3 10 14 travail terminé
1, (7,11)
7 11 7 8 10 14 7 8 10 14 travail terminé

8 7 10 14 7 10 14 pas de nouvelle
8,11
11 7 10 14 7 10 14 séparation

Donc 3 = 2 = fin et le seul groupe composé restant est (8,11). Au noms des états près,
nous obtenons donc l’automate AD2 qui est, en conséquence, minimal.

Exercice 2
Pour chaque expression rationnelle donnée en dessous construire un automate correspondant,
puis déterminiser et minimiser l’automate.
1) [(0+1)(0+1)]* + [(0+1)(0+1)(0+1)]*
2) 10 + (0 + 11) 0* 1

Solution

1) [(0+1)(0+1)]* + [(0+1)(0+1)(0+1)]*
1. L’automate asynchrone construit selon les règles AA4:

3 0 4 8 0 9
ε ε ε ε
1 ε 2 7 12 ε 13
ε ε ε ε
5 1 6 10 1 11
ε ε

ε
ε
0 32

ε ε
16 0 17 21 0 22 26 0 27
ε ε ε ε ε ε
14 ε 15 2 25 30 ε 31
ε ε ε ε ε ε
18 1 19 23 1 24 28 1 29

Il est assez difficile de déterminiser et minimiser cet automate. En notation raccourcie sans
noter les barres, on obtient en déterminisant :

Helen KASSEL, Boris VELIKSON 4 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 2

0 1
ES 0 4 17 6 19 A
4 17 9 22 11 24
B
6 19 9 22 11 24
S 9 22 4 27 6 29
C
S 11 24 4 27 6 29
S 4 27 9 17 11 19
D
S 6 29 9 17 11 19
S 9 17 4 22 6 24
E
S 11 19 4 22 6 24
4 22 9 27 11 29
F
6 24 9 27 11 29
S 9 27 4 17 6 19
G
S 11 29 4 17 6 19

Minimisation :
0={NT, T} avec NT={(4,17),(6,19),(4,22),(6,24)} et
T={(0),(9,22),(11,24),(4,27),(6,29),(9,17),(11,19),(9,27),(11,29)}.
On voit tout de suite que les couples d’états tels que ((9,22),(11,24)) ne pourrons jamais se
séparer sous la minimisation. On saute donc un pas et on écrit A, B, C, D, E, F comme ci-
dessus. Passons donc, dans ces termes, à la séparation
’0={NT’, T’}={{B,F},{A,C,D,E,G}} :
A 0,1 B
0 ou 1
0,1 0,1
ES A B
B C G C

S C D 0,1 0,1
S D E
F D
S E F
F G 0,1 0,1
E
S G B

On voit que les états A et G vont se réunir, et les autres, non.

Donc l’automate minimal : B
0,1 0,1
0 ou 1
AG C
ES AG B
B C 0,1 0,1
S C D
F D
S D E
S E F 0,1 0,1
E
F AG

Helen KASSEL, Boris VELIKSON 5 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 2

2. L’automate asynchrone simplifié (i) graphiquement, (ii) prenant en

considération que les caractères 0 et 1, ne figurant qu’en tant que la
combinaison 0+1, peuvent être considérés comme un seul caractère de
l’alphabet d’un caractère : A’={‘0+1’} :
ε

1 0,1 2 0,1 3

ε ε
ε
0 8

ε ε ε

4 0,1 5 0,1 6 0,1 7

Déterminisation utilisant une notation simplifiée :

état 0+1
ES 0 25
25 36
S 36 27
S 27 35
S 35 26
26 37
S 37 25
On obtient le même AD à 7 états qu’on a obtenu auparavant, avec, évidemment le même
automate minimal.
Remarque. L’expression rationnelle d’origine signifie « faire l’opération de lecture d’un
caractère (0 ou 1) un multiple de 2 fois ou un multiple de 3 fois ». 2 et 3 étant mutuellement
premiers, le cycle minimum pour effectuer ceci est de taille 6. D’où la solution immédiate.

2) 10 + (0 + 11) 0* 1

1. L’automate asynchrone construit selon les règles AA1:

2 0 3 ε
ε ε
1 7 ε 8 0 9 ε 10 1 11
ε ε ε
ε ε
4 1 5 1 6
0 15

ε ε
12 1 13 0 14

Helen KASSEL, Boris VELIKSON 6 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 2

2. Simplification graphique peut varier de presque la même chose ( AA2 ) :

2 0 3 0
ε ε
1 7 1 8
ε ε
ε ε
4 1 5 1 6

0 12

ε ε
9 1 10 0 11

à un degré de
simplification très 4
significatif (AA3) 1 0
qui n’est même pas 0 3
asynchrone: 0
0 1
1
2
1
1

a b
E 0 2 14
2 2 3 0
14 3 2 Déterminisation de
S 3 P P AA3 : 0 0 2 1 3
P P P
1 1 0 1,0

14 P

1,0

Une minimisation de cet automate le laisse tel quel :

0={NT, T}={{0,2,14,P),(3)}, tous les états se séparent sous 0.

Helen KASSEL, Boris VELIKSON 7 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 3-1

Exercice 3
Construire des automates finis non déterministes pour les expressions rationnelles qui
suivent.
1. (a+b)*
2. (a*+b*)*
3. a*(ba*)*

Déterminiser ces automates, puis les minimiser.

On peut prouver que deux expressions rationnelles sont équivalentes (égales) en montrant que
leur AFD minimaux sont les mêmes, à l’exception peut-être des noms des états. En utilisant
cette technique, répondez si parmi ces trois expressions rationnelles il y a des expressions
équivalentes.

Solution ε
1. (a+b)*
3 a 4
ε ε
1 ε 2 7 ε 8
ε ε
5 b 6

Déterminisation :
a b a b
ES 123578 235478 235678 ES A B C
S 235478 235478 235678 S B B C
S 235678 235478 235678 S C B C
(j’ai renommé les états pour plus de clarté).
a

B
a
A b a
b
C

a,b

C’est un ADC dont tous les états sont terminaux. Son minimal est :

Helen KASSEL, Boris VELIKSON 8 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 3-2,3-3

2. (a*+b*)*
ε
ε

2 ε 3 a 4 ε 5
ε ε
ε
0 ε 1 10 ε 11
ε
ε ε
6 ε 7 ba 8 ε 9

ε
ε

Notation raccourcie : 0’=(0,1,2,3,5,6,7,9,10,11) =A; 4’=(1,2,3,4,5,6,7,9,10,11) =B;

8’=(1,2,3,5,6,7,8,9,10,11)=C.
Déterminisation :
a b
ES A B C
S B B C
S C B C
On obtient le même ADC et donc le même automate minimal que dans le (1).

3. a*(ba*)*
ε
ε ε

0 ε 1 a 2 ε 3 ε 4 b 5 ε 6 a 7 ε 8 ε 9

ε ε
ε

Notation raccourcie :
0’=(0,1,3,4,9) ; 2’=(1,2,3,4,9) ; 5’=(4,5,6,8,9) ; 7’=(4,6,7,8,9)
Déterminisation :

a b
ES 0’ 2’ 5’
S 2’ 2’ 5’
S 5’ 7’ 5’
S 7’ 7’ 5’
a,b

C’est un ADC dont tous les états sont terminaux. Son minimal est :
Conclusion : Donc, toutes les trois ER sont égales.

Helen KASSEL, Boris VELIKSON 9 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 4-1,4-2

Exercice 4
Donner des expressions rationnelles correspondant aux automates suivants (le système
d’équations est unique pour chaque automate, mais les expressions rationnelles peuvent être
différentes (mais équivalentes) si on les résout dans un ordre différent) :
a b
A1 :
c
0 1
d

Solution (méthode de l’arrivée):

0 =  + 0a + 1d (eq 1)
1 = 0c + 1b (eq 2)
L=1

Version 1
Eq 2 ➔ 1 = 0cb*; remplaçant dans Eq 1, on obtient 0 =  + 0a + 0cb*d ➔ 0 = (a+cb*d)*
= (a+cb*d)*.
Donc L=(a+cb*d)*.

Version 2
Eq. 1 ➔ 0 = (1d + )a* = 1da* + a*; et comme dans la Version 1, 1 = 0cb*; donc
0 = 0cb*da* + a* donc 0 = a*(cb*da*)* = L.

On observe que l’égalité de ces deux expressions pour L n’est pas évidente. En fait, elle le
devient si on utilise l’identité (E+F)*=E*(FE*)*, avec E=a, F=cb*d.

Méthode d’élimination d’états:

1) 2) en éliminant 2 : ce qui donne

3) En éliminant 1 :

Helen KASSEL, Boris VELIKSON 10 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 4-1,4-2

A2 :
b
A B
a,c

b c

C
Solution
A =  + B(a + c) + Cb Eq 1
B = Ab Eq 2
C = Ac Eq 3

Remplaçant B et C dans Eq 1:
A =  + Ab(a + c) + Acb =  + A(ba + bc + cb) = (ba + bc + cb)* = L.

Par la méthode d’élimination d’états :

résulte en L=(ba + bc + cb)*.

Helen KASSEL, Boris VELIKSON 11 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 4-3,4-4

A3 : b

A a B a C
b

Solution
A =  + Ab + Bb + Cb Eq 1
B = Aa Eq 2
C = Ba Eq 3 L=C

Eq 3 et Eq 2 ➔ C = Aaa
Remplaçant dans Eq 1, on obtient
A =  + Ab + Aab + Aaab = (b + ab + aab)*
L = C = (b + ab + aab)*aa

Méthode d’élimination d’états:

On obtient la même expression L = (b + ab + aab)*aa

Helen KASSEL, Boris VELIKSON 12 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 4-3,4-4

a
A4 :
1 b 2
a

a b

01 3

Solution
1 =  + 1a + 2a Eq 1 L=2+3
2 = 1b Eq 2
3 = 1a + 2b Eq 3

Eq 2 dans Eq 1: 1 =  + 1a + 2a =  + 1a + 1ba = (a + ba)*

Donc 2 = (a + ba)*b et 3 = (a + ba)*a + (a + ba)*bb = (a + ba)*(a+bb)

L = (a + ba)*(a + b + bb)
Par l’élimination d’états:

Helen KASSEL, Boris VELIKSON 13 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 4-5

a
A5 :
1 b 2
a

a a b b

0 a 3

Solution
0=
1 = 0a + 1a + 2a Eq 1 L=2+3
2 = 0b + 1b Eq 2
3 = 0a + 1a + 2b Eq 3
Remplaçant 0, on obtient
1 = a + 1a + 2a Eq 1’
2 = b + 1b Eq 2’
3 = a + 1a + 2b Eq 3’
Remplaçant 2 dans Eq 1’ par Eq 2’:
1 = a + 1a + ba + 1ba = (a + ba) + 1(a + ba) = (a + ba)(a + ba)*
Donc 2 = b + 1b = b + (a + ba)(a + ba)*b = b + (a + ba)(a + ba)*b = (a + ba)*b
car X, +XX* = X*
et 3 = a + 1a + 2b = a + (a + ba)(a + ba)*a + (a + ba)*bb = (a + ba)*(a +bb) (pour les memes
raisons)
donc 2 et 3 reconnaissent les mêmes langages que pour A4, et le langage reconnu par
l’automate est le même que celui de A4. L = (a + ba)*(a + b + bb)

Cette conclusion est assez naturelle car A5 est le standardisé de A4.

Or, a+b+bb+(a+ba)(a+ba)*(a+b+bb)=(a + ba)*(a + b + bb).

Helen KASSEL, Boris VELIKSON 14 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 4-6

A6 :

0 a,b 1
b
ab a
2

Solution

rasdva.txt rasq.txt
0 =  + 2b Eq 1
1 = 0(a+b) + 2b Eq 2
2 =  + 0a + 1a Eq 3 L=1+2

Eliminons 1 de l’Eq 3 : 2 =  + 0a + 0(a+b)a + 2ba =  + 0(a + aa+ ba) + 2ba

Eliminons 0 : 2 =  + ( + 2b)(a + aa+ ba) + 2ba
=  + a + aa+ ba + 2ba + 2baa + 2bba + 2ba
= + a + aa+ ba + 2ba + 2baa + 2bba
=  + a + aa+ ba + 2(ba + baa + bba)

= ( + a + aa+ ba) (ba + baa + bba)*

Alors 0 =  + 2b =  + ( + a + aa+ ba) (ba + baa + bba)*b

1 = 0(a+b) + 2b = ( + 2b)(a + b) + 2b = a + b + 2(ba + bb + b)

= a + b + ( + a + aa+ ba) (ba + baa + bba)*(ba + bb + b)

L = 1 + 2 = a + b + ( + a + aa+ ba) (ba + baa + bba)*(ba + bb + b)

+ ( + a + aa+ ba) (ba + baa + bba)*
= a + b + ( + a + aa+ ba) (ba + baa + bba)*(  + ba + bb + b)

Ce n’est certainement pas la seule forme dont on peut exprimer L.

Par l’élimination d’états :

Helen KASSEL, Boris VELIKSON 15 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles
 TD feuille 2 : automates finis et expressions rationnelles, solutions Exo 4-7

0
1 1
A B
A8 :
0
0 1
C

Solution
A =  + A0 + C0 Eq 1
B = A1 + B1 + C1 Eq 2
C = B0 Eq 3 L=A

B = A1 + B1 + C1 = A1 + B1 + B01= A1(1 + 01)*, donc C = A1(1 + 01)*0

A =  + A0 + C0 =  + A0 + A1(1 + 01)*00 =  + A(0 + 1(1 + 01)*00)

= [0 + 1(1 + 01)*00]* = L

Par l’élimination d’états :

Helen KASSEL, Boris VELIKSON 16 Maths pour l’Info (2018/2019)

TD : automates finis et expressions rationnelles