Solution - TD Feuille 4 - Clôture des langages reconnaissables,

expressions régulières

Licence 3 - Université de Bordeaux

Solution de l’exercice 1 :
1. On a :
— L1 ∪ L2 = {aa, baa, ab, aba, bbb, a}.
— L1 ∩ L2 = {ab}.
— L1 •L2 = {aabbb, aaa, aaab, baabbb, baaa, baaab, abbbb, aba, abab, ababbb, abaa, abaab}.
— L1 \ L2 = {aa, baa, aba}.
— (L2 )2 = L2 • L2 = {bbbbbb, bbba, bbbab, abbb, aa, aab, abbbb, aba, abab}.
— L∗2 = (bbb + a + ab)∗ .
— (a + b)∗ \ L1 =  + a + b + ba + bb + bab + bba + bbb + aaa + aab + abb + (a + b)4 (a + b)∗
2. On donne un automate équivalent sans -transitions :

a b
6 7 8
a b b a
b
a 1 2 b
a
b b b a

3 a 4 a 5

1
3. On construit un automate pour L(A1 ) ∪ L(A2 ) :

a 2

1 b b
a
3

10 a
a b 20 b
a
30

Figure 1 – Automate pour L(A1 ) ∪ L(A2 )

On calcule l’automate produit pour L(A1 ) ∩ L(A2 ) :

b a
(3, 3) (2, 1) (1, 3)
a a
a b
(1, 1) (2, 2) (3, 2)
b

Figure 2 – Automate pour L(A1 ) ∩ L(A2 )

Pour L(A1 ) • L(A2 ), on commence par faire une version avec -transitions :


a 2 10 a

1 b b a b 20 b
a  a
3  30

Figure 3 – Automate pour L(A1 ) • L(A2 ) (avec -transitions)

2
On élimine ensuite les -transitions :

a
a
a 2 10 a
b
1 b b a b 20 b
a a a
3 30
b
a

Figure 4 – Automate pour L(A1 ) • L(A2 ) (sans -transitions)

On fait de même pour (L(A2 ))2 , on commence par faire une version avec -transitions :

1 a b  10 a
a b 2 a b 20 b
a  a
3 30

Figure 5 – Automate pour (L(A2 ))2 (avec -transitions)

On élimine ensuite les -transitions :

1 a b a 10 a
a b 2 a b 20 b
a b a
3 30

Figure 6 – Automate pour (L(A2 ))2 (sans -transitions)

3
On fait de même pour (L(A2 ))∗ , on commence par faire une version avec -transitions :

 1 a
b

0  a b 2 4
a
3

Figure 7 – Automate pour (L(A2 ))∗ (avec -transitions)

On élimine ensuite les -transitions (et l’état 4 qui devient inaccessible) :

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

Figure 8 – Automate pour (L(A2 ))∗ (sans -transitions)

Pour L(A1 ) \ L(A2 ), on doit construire un automate pour le complémentaire de A2 puis

en faire l’intersection avec A1 . On commence par déterminiser et compléter A2 :

{1}
b
a

a
a

a b
b {2} {3} P uits
b b
a b
{2, 3} {1, 3}
b

a
a

{1, 2}

Figure 9 – Automate déterministe complet pour L(A2 )

4
 On en déduit un automate pour (a + b)∗ \ L(A2 ) :

b
a
a

a
a b
b 2 3 6
b b
a b
4 5

a
7
a

Figure 10 – Automate (déterministe complet) pour (a + b)∗ \ L(A2 )

Il nous reste maintenant à faire l’intersection avec A1 pour avoir L(A1 ) \ L(A2 )

a a a a
(2, 7) (3, 2) (1, 3) (2, 1) (3, 6)

(1, 5) b b b b b b (1, 6)
b a a b a
a (3, 4) (2, 2) (1, 1) (3, 3) (2, 6)

Figure 11 – Automate pour L(A1 ) \ L(A2 )

Solution de l’exercice 2 :
On prouve la clôture par intersection. Soit L1 , L2 deux langages réguliers, on montre que
L1 ∩ L2 est aussi régulier. Puisque L1 , L2 sont réguliers on dispose de A1 = (Q1 , I1 , F1 , δ1 )
et A1 = (Q2 , I2 , F2 , δ2 ) des automates qui acceptent respectivement L1 et L2 . On construit à
partir de A1 et A2 , un nouvel automate B qui accepte L1 ∩ L2 .
B = (Q, I, F, δ) est l’automate produit défini comme suit : Q = Q1 × Q2 , I = I1 × I2 , F =
F1 × F2 et δ = {((q1 , q2 ), a) → (r1 , r2 ) | (q1 , a) → r1 ∈ δ1 et (q2 , a) → r2 ∈ δ2 }. Il reste à
montrer que B accepte bien L1 ∩ L2 . On prouve la double inclusion (i.e. L1 ∩ L2 ⊆ L(B) et
L(B ⊆ L1 ∩ L2 )).
Soit w = a1 · · · an un mot. Par définition de B : w ∈ L(B) si et seulement si il existe une
séquence d’états de Q : (q10 , q20 ), (q11 , q21 ), . . . , (q1n , q2n ) telle que :
— (q10 , q20 ) ∈ I
— (q1n , q2n ) ∈ F
— Pour tout i < n, ((q1i , q2i ), ai+1 ) → (q1i+1 , q2i+1 ) ∈ δ.
En utilisant les définitions de I, F, δ on obtient que cette propriété est équivalente à l’exis-
tence de de deux séquences : q10 , q11 , . . . , q1n sur Q1 et q20 , q21 , . . . , , q2n sur Q2 telles que :
— q10 ∈ I1 et q20 ∈ I2
— q1n ∈ F1 et q2n ∈ F2
— Pour tout i < n, (q1i , ai+1 ) → q1i+1 ∈ δ1 et (q2i , ai+1 ) → q2i+1 ∈ δ2 .

5
 Autrement dit w ∈ L(B) si et seulement si w ∈ L(A1 ) et w ∈ L(A2 ), on en déduit
L(B) = L1 ∩ L2

Solution de l’exercice 3 :
Équations : Figure 4
On utilise ici la méthode par résolution d’équations avec le lemme d’Arden. Il est important
ici de faire une remarque : il existe deux ’versions’ symétriques du lemme suivant la forme de
l’équation que l’on considère :

Si X = KX + L et  6∈ K Si X = XK + L et  6∈ K
alors alors
X = K ∗L X = LK ∗
Suivant la version qu’on utilise la méthode pour générer les équations est légérement dif-
férente. On utilise ici la version de droite (on utilisera la version de gauche pour la figure 2)
On considère L1 , L2 , L3 , L4 les langages définis comme suit : w ∈ Li si et seulement si il
existe un calcul de l’automate sur w partant de l’état intial et arrivant dans l’état i (attention
si on utilisait l’autre version du lemme la définition serait différente). Il découle des transitions
qu’on a les équations suivantes :

L1 = 
L2 = L1 a
L3 = L2 b + L3 (a + b)
L4 = L1 b + L2 a + L4 a
En substituant L1 par sa valeur on obtient :

L1 = 
L2 = a
L3 = L2 b + L3 (a + b)
L4 = b + L2 a + L4 a
En substituant L2 par sa valeur on obtient :

L1 = 
L2 = a
L3 = ab + L3 (a + b)
L4 = b + aa + L4 a
Enfin en appliquant le lemme d’Arden (version de droite) aux deux dernières équations on
obtient :

L1 = 
L2 = a
L3 = ab(a + b)∗
L4 = (b + aa)a∗

Équations : Figure 5
On utilise cette fois la version de gauche du lemme d’Arden.

6
 On considère L1 , L2 , L3 , L4 les langages définis comme suit : w ∈ Li si et seulement si il
existe un calcul de l’automate sur w partant de l’état i et arrivant dans un état final (attention
si on utilisait l’autre version du lemme la définition serait différente). Il découle des transitions
qu’on a les équations suivantes :

L1 = aL1 + bL4 + 
L2 = aL1 + aL3 + 
L3 = bL1
L4 = bL2
En substituant L3 et L4 on obtient :

L1 = aL1 + bbL2 + 
L2 = aL1 + abL1 + 
L3 = bL1
L4 = bL2
En substituant L2 on obtient :

L1 = (a + bba + bbab)L1 + bb + 
L2 = aL1 + abL1 + 
L3 = bL1
L4 = bL2
Enfin en appliquant le lemme d’Arden (version de gauche) à la première équation on
obtient : L1 = (a + bba + bbab)∗ (bb + ).

Brzozowski et McCluskey : Figure 5

On commence par compléter l’automate avec un unique état final et un unique état intial
puis on élimine les états un par un en les remplaçant par des transitions généralisées :

a  0

b 1 b

5 4 a 3

b 2 a


On supprime 3 :

7
 a  0

b 1

5 4 a + ab

b 2


On supprime 4 :

a  0

1

5 bb a + ab

2


On supprime 2 :

0
 + bb 
1

5 a + bba + bbab

Enfin, on supprime 1 :

bb) 0
∗ ( +
ba b)
+b
bba
(a +
5

Solution de l’exercice 4 :
1. aa(a + ab)∗ b. Après renommage, on obtient : a1 a2 (a3 + a4 b5 )∗ b6 .

8
 a3

a3 3 b6
a1 a2

a3
a4

a4
0 1 2 b6 6
b5
4 5
a4
b6

En reprenant l’alphabet initial on obtient :

a

a 3 b
a a

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

2. (a + ab)∗ ( + ab). Après renommage, on obtient : (a1 + a2 b3 )∗ ( + a4 b5 ).

a1

a1 1 a4
b5
a1

a2
a2

0 a4 4 5
b3
2 3
a2
a4

En reprenant l’alphabet initial on obtient :

a

a 1 a
b
a

0 a a 4 5
b
2 3
a
a

3. aab∗ (ab)∗ +ab∗ +a∗ bba. Après renommage, on obtient : a1 a2 b∗3 (a4 b5 )∗ +a6 b∗7 +a∗8 b9 b10 a11 .

9
 b3 a4
a2 b3 a4 b5
1 2 3 4 5
b7 a4

a1
a6 b7
0 6 7
a8

a8
b9 b10 a11
8 9 10 11
b9

En reprenant l’alphabet initial on obtient :

b a
a b a b
1 2 3 4 5
b a
a

a b
0 6 7
a
a

b b a
8 9 10 11
b

4. a((ab)∗ cb∗ )∗ + a(ababacb∗ )∗ a∗ . Après renommage, on obtient :

a1 ((a2 b3 )∗ c4 b∗5 )∗ + a6 (a7 b8 a9 b10 a11 c12 b∗13 )∗ a∗14 .
c4
a2 c4 b5
a2 b3 c4 b5
1 2 3 4 5
a2 c4
a1

a2 a7
0
a6

a7 b1 a14
3
a7 a9 b10 a11 b13 a14
6 7 8 9 10 11 c 12 13 14
b8 12
a14

a14

En reprenant l’alphabet initial on obtient :

10
 c
a c b
a b c b
1 2 3 4 5
a c
a

a
0 a

a a
a

b
a a b a b a
6 7 8 9 10 11 c 12 13 14
b
a

11