Théorie des Langages 1

Cours 3 : ε-transitions + déterminisation

L. Rieg

Grenoble INP - Ensimag, 1re année

Année 2024-2025

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 1 / 21

Une propriété
Proposition
Pour tout automate fini A, il existe un automate fini B avec :
un unique état initial sans transition entrante,
un unique état acceptant sans transition sortante,
équivalent à A.

Construction :

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 2 / 21

Une propriété
Proposition
Pour tout automate fini A, il existe un automate fini B avec :
un unique état initial sans transition entrante,
un unique état acceptant sans transition sortante,
équivalent à A.

Construction :

ε ε
ε
A
ε
ε

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 2 / 21

Union
Etant donnés deux automates A1 et A2 , construire un automate
reconnaissant L(A1 ) ∪ L(A2 ).

A1

A2

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 3 / 21

Union
Etant donnés deux automates A1 et A2 , construire un automate
reconnaissant L(A1 ) ∪ L(A2 ).

A1
ε ε

ε ε
A2

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 3 / 21

Union
Etant donnés deux automates A1 et A2 , construire un automate
reconnaissant L(A1 ) ∪ L(A2 ).

A1
ε ε

ε ε
A2

Formellement :
Si A1 = (Q1 , V, δ1 , I1 , F1 ) et A2 = (Q2 , V, δ2 , I2 , F2 ), on a :
def
A1 ∪ A2 = (Q1 ⊎ Q2 ⊎ {i, f } , V, δ, {i} , {f })
avec
def
δ = δ1 ∪ δ2 ∪ {(i, ε, q) | q ∈ I1 ∪ I2 } ∪ {(q, ε, f ) | q ∈ F1 ∪ F2 }
L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 3 / 21
Concaténation
Etant donnés deux automates A1 et A2 , construire un automate
reconnaissant L(A1 ).L(A2 ).

A1

A2

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 4 / 21

Concaténation
Etant donnés deux automates A1 et A2 , construire un automate
reconnaissant L(A1 ).L(A2 ).

A1

ε
A2

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 4 / 21

Concaténation
Etant donnés deux automates A1 et A2 , construire un automate
reconnaissant L(A1 ).L(A2 ).

A1

ε
A2

Exercice : écrire formellement cette transformation

Si A1 = (Q1 , V, δ1 , I1 , F1 ) et A2 = (Q2 , V, δ2 , I2 , F2 ), on a :

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 4 / 21

Concaténation
Etant donnés deux automates A1 et A2 , construire un automate
reconnaissant L(A1 ).L(A2 ).

A1

ε
A2

Exercice : écrire formellement cette transformation

Si A1 = (Q1 , V, δ1 , I1 , F1 ) et A2 = (Q2 , V, δ2 , I2 , F2 ), on a :
def
A1 .A2 = (Q1 ⊎ Q2 , V, δ, I1 , F2 )
def
avec δ = δ1 ∪ δ2 ∪ {(f, ε, i) | f ∈ F1 , i ∈ I2 }
L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 4 / 21
Comment montrer que cette définition est correcte ?
def
On pose A1 .A2 = (Q1 ⊎ Q2 , V, δ, I1 , F2 )
def
δ = δ1 ∪ δ2 ∪ {(f, ε, i) | f ∈ F1 , i ∈ I2 }
Montrer que L(A1 .A2 ) = L(A1 ).L(A2 ).

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 5 / 21

Comment montrer que cette définition est correcte ?
def
On pose A1 .A2 = (Q1 ⊎ Q2 , V, δ, I1 , F2 )
def
δ = δ1 ∪ δ2 ∪ {(f, ε, i) | f ∈ F1 , i ∈ I2 }
Montrer que L(A1 .A2 ) = L(A1 ).L(A2 ).
Par double inclusion :
L(A1 ).L(A2 ) ⊆ L(A1 .A2 ) :

L(A1 .A2 ) ⊆ L(A1 ).L(A2 ) :

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 5 / 21

Comment montrer que cette définition est correcte ?
def
On pose A1 .A2 = (Q1 ⊎ Q2 , V, δ, I1 , F2 )
def
δ = δ1 ∪ δ2 ∪ {(f, ε, i) | f ∈ F1 , i ∈ I2 }
Montrer que L(A1 .A2 ) = L(A1 ).L(A2 ).
Par double inclusion :
L(A1 ).L(A2 ) ⊆ L(A1 .A2 ) : Soient
w1 ∈ L(A1 )
w2 ∈ L(A2 )

L(A1 .A2 ) ⊆ L(A1 ).L(A2 ) :

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 5 / 21

Comment montrer que cette définition est correcte ?
def
On pose A1 .A2 = (Q1 ⊎ Q2 , V, δ, I1 , F2 )
def
δ = δ1 ∪ δ2 ∪ {(f, ε, i) | f ∈ F1 , i ∈ I2 }
Montrer que L(A1 .A2 ) = L(A1 ).L(A2 ).
Par double inclusion :
L(A1 ).L(A2 ) ⊆ L(A1 .A2 ) : Soient
w1 ∈ L(A1 ) ⇐⇒ ∃χ1 chemin de i1 ∈ I1 à f1 ∈ F1 de trace w1
w2 ∈ L(A2 ) ⇐⇒ ∃χ2 chemin de i2 ∈ I2 à f2 ∈ F2 de trace w2

L(A1 .A2 ) ⊆ L(A1 ).L(A2 ) :

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 5 / 21

Comment montrer que cette définition est correcte ?
def
On pose A1 .A2 = (Q1 ⊎ Q2 , V, δ, I1 , F2 )
def
δ = δ1 ∪ δ2 ∪ {(f, ε, i) | f ∈ F1 , i ∈ I2 }
Montrer que L(A1 .A2 ) = L(A1 ).L(A2 ).
Par double inclusion :
L(A1 ).L(A2 ) ⊆ L(A1 .A2 ) : Soient
w1 ∈ L(A1 ) ⇐⇒ ∃χ1 chemin de i1 ∈ I1 à f1 ∈ F1 de trace w1
w2 ∈ L(A2 ) ⇐⇒ ∃χ2 chemin de i2 ∈ I2 à f2 ∈ F2 de trace w2
Alors χ1 · (f1 , ε, i2 ) · χ2 est un chemin de i1 à f2 dans A1 .A2 de trace
w1 w2 . Ainsi, w1 w2 ∈ L(A1 .A2 ).
L(A1 .A2 ) ⊆ L(A1 ).L(A2 ) :

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 5 / 21

Comment montrer que cette définition est correcte ?
def
On pose A1 .A2 = (Q1 ⊎ Q2 , V, δ, I1 , F2 )
def
δ = δ1 ∪ δ2 ∪ {(f, ε, i) | f ∈ F1 , i ∈ I2 }
Montrer que L(A1 .A2 ) = L(A1 ).L(A2 ).
Par double inclusion :
L(A1 ).L(A2 ) ⊆ L(A1 .A2 ) : Soient
w1 ∈ L(A1 ) ⇐⇒ ∃χ1 chemin de i1 ∈ I1 à f1 ∈ F1 de trace w1
w2 ∈ L(A2 ) ⇐⇒ ∃χ2 chemin de i2 ∈ I2 à f2 ∈ F2 de trace w2
Alors χ1 · (f1 , ε, i2 ) · χ2 est un chemin de i1 à f2 dans A1 .A2 de trace
w1 w2 . Ainsi, w1 w2 ∈ L(A1 .A2 ).
L(A1 .A2 ) ⊆ L(A1 ).L(A2 ) : Soit w ∈ L(A1 .A2 ), donc il existe un
chemin dans A1 .A2 de i ∈ I1 à f ∈ F2 de trace w.

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 5 / 21

Comment montrer que cette définition est correcte ?
def
On pose A1 .A2 = (Q1 ⊎ Q2 , V, δ, I1 , F2 )
def
δ = δ1 ∪ δ2 ∪ {(f, ε, i) | f ∈ F1 , i ∈ I2 }
Montrer que L(A1 .A2 ) = L(A1 ).L(A2 ).
Par double inclusion :
L(A1 ).L(A2 ) ⊆ L(A1 .A2 ) : Soient
w1 ∈ L(A1 ) ⇐⇒ ∃χ1 chemin de i1 ∈ I1 à f1 ∈ F1 de trace w1
w2 ∈ L(A2 ) ⇐⇒ ∃χ2 chemin de i2 ∈ I2 à f2 ∈ F2 de trace w2
Alors χ1 · (f1 , ε, i2 ) · χ2 est un chemin de i1 à f2 dans A1 .A2 de trace
w1 w2 . Ainsi, w1 w2 ∈ L(A1 .A2 ).
L(A1 .A2 ) ⊆ L(A1 ).L(A2 ) : Soit w ∈ L(A1 .A2 ), donc il existe un
chemin dans A1 .A2 de i ∈ I1 à f ∈ F2 de trace w. Par contruction de
A1 .A2 , ce chemin passe par une ε-transition entre un état f1 ∈ F1 et
un état i2 ∈ I2 . Ainsi, on a χ = χ1 · (f1 , ε, i2 ) · χ2 .

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 5 / 21

Comment montrer que cette définition est correcte ?
def
On pose A1 .A2 = (Q1 ⊎ Q2 , V, δ, I1 , F2 )
def
δ = δ1 ∪ δ2 ∪ {(f, ε, i) | f ∈ F1 , i ∈ I2 }
Montrer que L(A1 .A2 ) = L(A1 ).L(A2 ).
Par double inclusion :
L(A1 ).L(A2 ) ⊆ L(A1 .A2 ) : Soient
w1 ∈ L(A1 ) ⇐⇒ ∃χ1 chemin de i1 ∈ I1 à f1 ∈ F1 de trace w1
w2 ∈ L(A2 ) ⇐⇒ ∃χ2 chemin de i2 ∈ I2 à f2 ∈ F2 de trace w2
Alors χ1 · (f1 , ε, i2 ) · χ2 est un chemin de i1 à f2 dans A1 .A2 de trace
w1 w2 . Ainsi, w1 w2 ∈ L(A1 .A2 ).
L(A1 .A2 ) ⊆ L(A1 ).L(A2 ) : Soit w ∈ L(A1 .A2 ), donc il existe un
chemin dans A1 .A2 de i ∈ I1 à f ∈ F2 de trace w. Par contruction de
A1 .A2 , ce chemin passe par une ε-transition entre un état f1 ∈ F1 et
un état i2 ∈ I2 . Ainsi, on a χ = χ1 · (f1 , ε, i2 ) · χ2 . χ1 et χ2 sont
acceptants dans A1 et A2 d’où tr(χ1 ) ∈ L(A1 ) et tr(χ2 ) ∈ L(A2 ).

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 5 / 21

Comment montrer que cette définition est correcte ?
def
On pose A1 .A2 = (Q1 ⊎ Q2 , V, δ, I1 , F2 )
def
δ = δ1 ∪ δ2 ∪ {(f, ε, i) | f ∈ F1 , i ∈ I2 }
Montrer que L(A1 .A2 ) = L(A1 ).L(A2 ).
Par double inclusion :
L(A1 ).L(A2 ) ⊆ L(A1 .A2 ) : Soient
w1 ∈ L(A1 ) ⇐⇒ ∃χ1 chemin de i1 ∈ I1 à f1 ∈ F1 de trace w1
w2 ∈ L(A2 ) ⇐⇒ ∃χ2 chemin de i2 ∈ I2 à f2 ∈ F2 de trace w2
Alors χ1 · (f1 , ε, i2 ) · χ2 est un chemin de i1 à f2 dans A1 .A2 de trace
w1 w2 . Ainsi, w1 w2 ∈ L(A1 .A2 ).
L(A1 .A2 ) ⊆ L(A1 ).L(A2 ) : Soit w ∈ L(A1 .A2 ), donc il existe un
chemin dans A1 .A2 de i ∈ I1 à f ∈ F2 de trace w. Par contruction de
A1 .A2 , ce chemin passe par une ε-transition entre un état f1 ∈ F1 et
un état i2 ∈ I2 . Ainsi, on a χ = χ1 · (f1 , ε, i2 ) · χ2 . χ1 et χ2 sont
acceptants dans A1 et A2 d’où tr(χ1 ) ∈ L(A1 ) et tr(χ2 ) ∈ L(A2 ).

Exercice : faire de même pour l’union A1 ∪ A2 .

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 5 / 21
Concaténation itérée
Etant donné un automate A, construire un automate reconnaissant L(A)∗ .
ε
ε

ε A ε

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 6 / 21

Concaténation itérée
Etant donné un automate A, construire un automate reconnaissant L(A)∗ .
ε
ε

ε A ε

ε
∗ ∗
Exemple : L(A) = {a} {b} {c}
ε
b
q0 q1
ε
a c

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 6 / 21

Concaténation itérée
Etant donné un automate A, construire un automate reconnaissant L(A)∗ .
ε
ε

ε A ε

ε
∗ ∗
Exemple : L(A) = {a} {b} {c}
ε
b
q0 q1
ε
a c

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 6 / 21

Concaténation itérée
Etant donné un automate A, construire un automate reconnaissant L(A)∗ .
ε
ε

ε A ε

ε
∗ ∗
Exemple : L(A) = {a} {b} {c}
ε
b
q0 q1
ε
a c

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 6 / 21

Concaténation itérée
Etant donné un automate A, construire un automate reconnaissant L(A)∗ .
ε
ε

ε A ε

ε
∗ ∗
Exemple : L(A) = {a} {b} {c}
ε
b
q0 q1
ε
a c

On ne reconnaît pas ε.

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 6 / 21

Concaténation itérée
Etant donné un automate A, construire un automate reconnaissant L(A)∗ .
ε
ε

ε A ε

ε
∗ ∗
Exemple : L(A) = {a} {b} {c}
ε
b
q0 q1
ε
a c

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 6 / 21

Concaténation itérée
Etant donné un automate A, construire un automate reconnaissant L(A)∗ .
ε
ε

ε A ε

ε
∗ ∗
Exemple : L(A) = {a} {b} {c}
ε
b
q0 q1
ε
a c

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 6 / 21

Concaténation itérée
Etant donné un automate A, construire un automate reconnaissant L(A)∗ .
ε
ε

ε A ε

ε
∗ ∗
Exemple : L(A) = {a} {b} {c}
ε
b
q0 q1
ε
a c

On reconnaît {a}∗ en trop.

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 6 / 21

Concaténation itérée
Etant donné un automate A, construire un automate reconnaissant L(A)∗ .
ε
ε

ε A ε

ε
∗ ∗
Exemple : L(A) = {a} {b} {c}
ε
b
q0 q1
ε
a c

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 6 / 21

Concaténation itérée
Etant donné un automate A, construire un automate reconnaissant L(A)∗ .
ε
ε

ε A ε

ε
∗ ∗
Exemple : L(A) = {a} {b} {c}
ε
b
q0 q1
ε
a c

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 6 / 21

Concaténation itérée
Etant donné un automate A, construire un automate reconnaissant L(A)∗ .
ε
ε

ε A ε

ε
∗ ∗
Exemple : L(A) = {a} {b} {c}
ε
b
q0 q1
ε
a c

On reconnaît {c}∗ en trop.

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 6 / 21

Concaténation itérée
Etant donné un automate A, construire un automate reconnaissant L(A)∗ .
ε
ε

ε A ε

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 6 / 21

Résumé
Théorème
La classe des langages réguliers est fermée :
par union
par concaténation
par concaténation itérée

Nous en verrons d’autres au cours 7.

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 7 / 21

Plusieurs automates pour le même langage
AFND :
q1
ε
a a
ε ε
q0 q3 q4 q5
ε
b
ε q2

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 8 / 21

Plusieurs automates pour le même langage
AFND :
q1
ε
a a
ε ε
q0 q3 q4 q5
ε
b
ε q2

AFND−ε :
a
q0 q4

a, b a

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 8 / 21

Plusieurs automates pour le même langage
AFND :
q1
ε
a a
ε ε
q0 q3 q4 q5
ε
b
ε q2

AFND−ε : AFD :
b
a
q0 q4
p0 p1
a

a, b a
b a

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 8 / 21

Résumé
Théorème
La classe des langages réguliers est fermée :
par union
par concaténation
par concaténation itérée

Nous en verrons d’autres au cours 7.

Question
Peut-on toujours effectuer les transformations

AF (N D) ⇐⇒ AF (N D) − ε ⇐⇒ AFD ?

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 9 / 21

Résumé
Théorème
La classe des langages réguliers est fermée :
par union
par concaténation
par concaténation itérée

Nous en verrons d’autres au cours 7.

Question
Peut-on toujours effectuer les transformations

AF (N D) ⇐⇒ AF (N D) − ε ⇐⇒ AFD ?

Dans la suite : techniques de transformation, preuves plus tard

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 9 / 21
Algorithme de suppression des ε-transitions
Deux étapes :
1. Déterminer les états qu’on peut atteindre en ne se servant que
d’ε-transitions
2. Se servir de cette information pour construire un automate équivalent
sans ε-transition

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 10 / 21

Algorithme de suppression des ε-transitions
Deux étapes :
1. Déterminer les états qu’on peut atteindre en ne se servant que
d’ε-transitions
2. Se servir de cette information pour construire un automate équivalent
sans ε-transition

Etape 1

Définition (États accessibles)

Etant donné un automate A = ⟨Q, V, δ, I, F ⟩, on définit par induction pour
tout p ∈ Q l’ensemble Accε (p) des états accessibles depuis p par
ε-transitions :

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 10 / 21

Algorithme de suppression des ε-transitions
Deux étapes :
1. Déterminer les états qu’on peut atteindre en ne se servant que
d’ε-transitions
2. Se servir de cette information pour construire un automate équivalent
sans ε-transition

Etape 1

Définition (États accessibles)

Etant donné un automate A = ⟨Q, V, δ, I, F ⟩, on définit par induction pour
tout p ∈ Q l’ensemble Accε (p) des états accessibles depuis p par
ε-transitions :
p ∈ Accε (p)

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 10 / 21

Algorithme de suppression des ε-transitions
Deux étapes :
1. Déterminer les états qu’on peut atteindre en ne se servant que
d’ε-transitions
2. Se servir de cette information pour construire un automate équivalent
sans ε-transition

Etape 1

Définition (États accessibles)

Etant donné un automate A = ⟨Q, V, δ, I, F ⟩, on définit par induction pour
tout p ∈ Q l’ensemble Accε (p) des états accessibles depuis p par
ε-transitions :
p ∈ Accε (p)
si q ∈ Accε (p) et (q, ε, r) ∈ δ alors r ∈ Accε (p)

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 10 / 21

Algorithme de suppression des ε-transitions
Deux étapes :
1. Déterminer les états qu’on peut atteindre en ne se servant que
d’ε-transitions
2. Se servir de cette information pour construire un automate équivalent
sans ε-transition

Etape 1

Définition (États accessibles)

Etant donné un automate A = ⟨Q, V, δ, I, F ⟩, on définit par induction pour
tout p ∈ Q l’ensemble Accε (p) des états accessibles depuis p par
ε-transitions :
p ∈ Accε (p)
si q ∈ Accε (p) et (q, ε, r) ∈ δ alors r ∈ Accε (p)

Calcul de Accε (p) par itération (cf cours 1)

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 10 / 21
Rappel sur le calcul par itération pour Accε (p)
Idée : Calculer les états de Accε (p) accessibles en au plus n pas et faire
croître n. S
Accε (p) = n≥0 An , où la suite (An ) est définie par :

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 11 / 21

Rappel sur le calcul par itération pour Accε (p)
Idée : Calculer les états de Accε (p) accessibles en au plus n pas et faire
croître n. S
Accε (p) = n≥0 An , où la suite (An ) est définie par :
def
A0 = {p}

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 11 / 21

Rappel sur le calcul par itération pour Accε (p)
Idée : Calculer les états de Accε (p) accessibles en au plus n pas et faire
croître n. S
Accε (p) = n≥0 An , où la suite (An ) est définie par :
def
A0 = {p}
def
An+1 = An ∪ {r ∈ Q | ∃q ∈ An ∧ (q, ε, r) ∈ δ}

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 11 / 21

Rappel sur le calcul par itération pour Accε (p)
Idée : Calculer les états de Accε (p) accessibles en au plus n pas et faire
croître n. S
Accε (p) = n≥0 An , où la suite (An ) est définie par :
def
A0 = {p}
def
An+1 = An ∪ {r ∈ Q | ∃q ∈ An ∧ (q, ε, r) ∈ δ}

algorithme Accε (p) =

n ← 0, A0 ← {p}
répéter
An+1 ← An ∪ {κi (e1 , . . . , eki ) | κi ∈ K, e1 , . . . , eki ∈ An }
n←n+1
jusqu’à An+1 = An
renvoyer An

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 11 / 21

Rappel sur le calcul par itération pour Accε (p)
Idée : Calculer les états de Accε (p) accessibles en au plus n pas et faire
croître n. S
Accε (p) = n≥0 An , où la suite (An ) est définie par :
def
A0 = {p}
def
An+1 = An ∪ {r ∈ Q | ∃q ∈ An ∧ (q, ε, r) ∈ δ}

algorithme Accε (p) =

n ← 0, A0 ← {p}
répéter
An+1 ← An ∪ {κi (e1 , . . . , eki ) | κi ∈ K, e1 , . . . , eki ∈ An }
n←n+1
jusqu’à An+1 = An
renvoyer An
Question : Est-ce que ça termine toujours ?

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 11 / 21

Rappel sur le calcul par itération pour Accε (p)
Idée : Calculer les états de Accε (p) accessibles en au plus n pas et faire
croître n. S
Accε (p) = n≥0 An , où la suite (An ) est définie par :
def
A0 = {p}
def
An+1 = An ∪ {r ∈ Q | ∃q ∈ An ∧ (q, ε, r) ∈ δ}

algorithme Accε (p) =

n ← 0, A0 ← {p}
répéter
An+1 ← An ∪ {κi (e1 , . . . , eki ) | κi ∈ K, e1 , . . . , eki ∈ An }
n←n+1
jusqu’à An+1 = An
renvoyer An
Question : Est-ce que ça termine toujours ?

Au besoin, on fait un tableau des An jusqu’à stabiliser.

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 11 / 21
Algorithme de suppression des ε-transitions (suite)
Etape 2.
Définition
Etant donné un automate A = ⟨Q, V, δ, I, F ⟩, on définit l’automate
B = ⟨Q, V, δ ′ , I, F ′ ⟩ de la façon suivante :

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 12 / 21

Algorithme de suppression des ε-transitions (suite)
Etape 2.
Définition
Etant donné un automate A = ⟨Q, V, δ, I, F ⟩, on définit l’automate
B = ⟨Q, V, δ ′ , I, F ′ ⟩ de la façon suivante :
(p, a, q) ∈ δ ′ ssi a ̸= ε et ∃r ∈ Accε (p) tel que (r, a, q) ∈ δ

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 12 / 21

Algorithme de suppression des ε-transitions (suite)
Etape 2.
Définition
Etant donné un automate A = ⟨Q, V, δ, I, F ⟩, on définit l’automate
B = ⟨Q, V, δ ′ , I, F ′ ⟩ de la façon suivante :
(p, a, q) ∈ δ ′ ssi a ̸= ε et ∃r ∈ Accε (p) tel que (r, a, q) ∈ δ
a ε a
p q ⇐⇒ ∃ r, p r q

B A A

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 12 / 21

Algorithme de suppression des ε-transitions (suite)
Etape 2.
Définition
Etant donné un automate A = ⟨Q, V, δ, I, F ⟩, on définit l’automate
B = ⟨Q, V, δ ′ , I, F ′ ⟩ de la façon suivante :
(p, a, q) ∈ δ ′ ssi a ̸= ε et ∃r ∈ Accε (p) tel que (r, a, q) ∈ δ
a ε a
p q ⇐⇒ ∃ r, p r q

B A A

F ′ = {p ∈ Q | Accε (p) ∩ F ̸= ∅}

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 12 / 21

Algorithme de suppression des ε-transitions (suite)
Etape 2.
Définition
Etant donné un automate A = ⟨Q, V, δ, I, F ⟩, on définit l’automate
B = ⟨Q, V, δ ′ , I, F ′ ⟩ de la façon suivante :
(p, a, q) ∈ δ ′ ssi a ̸= ε et ∃r ∈ Accε (p) tel que (r, a, q) ∈ δ
a ε a
p q ⇐⇒ ∃ r, p r q

B A A

F ′ = {p ∈ Q | Accε (p) ∩ F ̸= ∅}

Propositions
B est un automate sans ε-transition.

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 12 / 21

Algorithme de suppression des ε-transitions (suite)
Etape 2.
Définition
Etant donné un automate A = ⟨Q, V, δ, I, F ⟩, on définit l’automate
B = ⟨Q, V, δ ′ , I, F ′ ⟩ de la façon suivante :
(p, a, q) ∈ δ ′ ssi a ̸= ε et ∃r ∈ Accε (p) tel que (r, a, q) ∈ δ
a ε a
p q ⇐⇒ ∃ r, p r q

B A A

F ′ = {p ∈ Q | Accε (p) ∩ F ̸= ∅}

Propositions
B est un automate sans ε-transition.

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 12 / 21

Algorithme de suppression des ε-transitions (suite)
Etape 2.
Définition
Etant donné un automate A = ⟨Q, V, δ, I, F ⟩, on définit l’automate
B = ⟨Q, V, δ ′ , I, F ′ ⟩ de la façon suivante :
(p, a, q) ∈ δ ′ ssi a ̸= ε et ∃r ∈ Accε (p) tel que (r, a, q) ∈ δ
a ε a
p q ⇐⇒ ∃ r, p r q

B A A

F ′ = {p ∈ Q | Accε (p) ∩ F ̸= ∅}

Propositions
B est un automate sans ε-transition.
B est équivalent à A.

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 12 / 21

Algorithme de suppression des ε-transitions (suite)
Etape 2.
Définition
Etant donné un automate A = ⟨Q, V, δ, I, F ⟩, on définit l’automate
B = ⟨Q, V, δ ′ , I, F ′ ⟩ de la façon suivante :
(p, a, q) ∈ δ ′ ssi a ̸= ε et ∃r ∈ Accε (p) tel que (r, a, q) ∈ δ
a ε a
p q ⇐⇒ ∃ r, p r q

B A A

F ′ = {p ∈ Q | Accε (p) ∩ F ̸= ∅}

Propositions
B est un automate sans ε-transition.
B est équivalent à A. démo plus tard

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 12 / 21

Exercice
Construire B pour l’automate A suivant :

0 1

q1 ε q2
ε

q0
ε

q3 ε q4

1 0

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 13 / 21

Exercice
Construire B pour l’automate A suivant :
p Accε (p)
0 1 q0 q0 , q1 , q2 , q3 , q4
q1 q1 , q2
ε q2 q2
q1 q2 q3 q3 , q4
ε q4 q4
q0
ε

q3 ε q4

1 0

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 13 / 21

Exercice
Construire B pour l’automate A suivant :
p Accε (p)
0 1 q0 q0 , q1 , q2 , q3 , q4
q1 q1 , q2
ε q2 q2
q1 q2 q3 q3 , q4
ε q4 q4
q0 δ′ 0 1
ε q0 q1 , q4 q2 , q3
ε q1 q1 q2
q3 q4 q2 – q2
q3 q4 q3
q4 q4 –
1 0

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 13 / 21

Exercice
Construire B pour l’automate A suivant :
p Accε (p)
0 1 q0 q0 , q1 , q2 , q3 , q4
q1 q1 , q2
ε q2 q2
q1 q2 q3 q3 , q4
ε q4 q4
q0 δ′ 0 1
ε q0 q1 , q4 q2 , q3
ε q1 q1 q2
q3 q4 q2 – q2
q3 q4 q3
q4 q4 –
1 0
F′ = ?

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 13 / 21

Exercice
Construire B pour l’automate A suivant :
p Accε (p)
0 1 q0 q0 , q1 , q2 , q3 , q4
q1 q1 , q2
ε q2 q2
q1 q2 q3 q3 , q4
ε q4 q4
q0 δ′ 0 1
ε q0 q1 , q4 q2 , q3
ε q1 q1 q2
q3 q4 q2 – q2
q3 q4 q3
q4 q4 –
1 0
F′ = ?

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 13 / 21

Exercice
Construire B pour l’automate A suivant :
p Accε (p)
0 1 q0 q0 , q1 , q2 , q3 , q4
q1 q1 , q2
ε q2 q2
q1 q2 q3 q3 , q4
ε q4 q4
q0 δ′ 0 1
ε q0 q1 , q4 q2 , q3
ε q1 q1 q2
q3 q4 q2 – q2
q3 q4 q3
q4 q4 –
1 0
F′ = ?

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 13 / 21

Exercice
Construire B pour l’automate A suivant :
p Accε (p)
0 1 q0 q0 , q1 , q2 , q3 , q4
q1 q1 , q2
ε q2 q2
q1 q2 q3 q3 , q4
ε q4 q4
q0 δ′ 0 1
ε q0 q1 , q4 q2 , q3
ε q1 q1 q2
q3 q4 q2 – q2
q3 q4 q3
q4 q4 –
1 0
F ′ = {q0 , q1 , q2 , q3 , q4 }

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 13 / 21

Exercice (solution)
0 1

1
q1 q2
0
1
q0
0
1
q3 q4
0

1 0

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 14 / 21

Résumé
Théorème
La classe des langages réguliers est fermée :
par union
par concaténation
par concaténation itérée

Nous en verrons d’autres au cours 7.

Question
Peut-on toujours effectuer les transformations
OK
AF (N D) ⇐===⇒ AF (N D) − ε ⇐⇒ AFD ?

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 15 / 21

Rappels sur les AFD complets
Définition (Automate déterministe complet)
Un AF ⟨Q, V, δ, I, F ⟩ est dit déterministe complet si
1. Card(I) = 1 (exactement un état intial)
2. ̸ ∃ (q, ε, p) ∈ δ
3. ∀(q, a) ∈ Q × V, ∃!p ∈ Q, (q, a, p) ∈ δ.

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 16 / 21

Rappels sur les AFD complets
Définition (Automate déterministe complet)
Un AF ⟨Q, V, δ, I, F ⟩ est dit déterministe complet si
1. Card(I) = 1 (exactement un état intial)
2. ̸ ∃ (q, ε, p) ∈ δ
3. ∀(q, a) ∈ Q × V, ∃!p ∈ Q, (q, a, p) ∈ δ.

Conséquences
L’automate a un seul état initial
δ est une fonction totale : Q × V → Q
δ s’étend aux mots : δ ∗ : Q × V ∗ → Q
Donne directement un « programme » reconnaisseur

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 16 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b
q0 q2 q4

b a
b b

q1 q3
a

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b
q0 q2 q4

b a
b b

q1 q3
a

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b
q0 q2 q4

b a
b b

q1 q3
a

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b
q0 q2 q4

b a
b b

q1 q3
a

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b
q0 q2 q4

b a
b b

q1 q3
a

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b
q0 q2 q4

b a
b b

q1 q3
a

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b
q0 q2 q4

b a
b b

q1 q3
a

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b
q0 q2 q4

b a
b b

q1 q3
a

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b
q0 q2 q4

b a
b b

q1 q3
a

OK : aab ∈ L(A)
L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21
Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a q1 , q2 , q3
a
b
q0 q2 q4

b a q1 , q2 , q4
b b

q1 q3
a

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a q1 , q2 , q3
a
b
q0 q2 q4

b a q1 , q2 , q4
b b

q1 q3
a

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b q0 , q1
q0 q2 q4

b a
b b
q1 , q2 , q3
q1 q3
a

a
q1 , q2 , q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b q0 , q1
q0 q2 q4
a
b a
b b
q1 , q2 , q3
q1 q3
a

a
q1 , q2 , q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b q0 , q1
q0 q2 q4
a
b a
b b
q1 , q2 , q3
q1 q3
a

a
q1 , q2 , q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b q0 , q1
q0 q2 q4
a
b a
b b
q1 , q2 , q3
q1 q3
a

a
q1 , q2 , q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b q0 , q1
q0 q2 q4
a
b a
b b
q1 , q2 , q3 a
q1 q3
a

a
q1 , q2 , q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b q0 , q1
q0 q2 q4
a
b a
b b
q1 , q2 , q3 a
q1 q3
a

a
q1 , q2 , q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b q0 , q1
q0 q2 q4
a
b a
b b
q1 , q2 , q3 a
q1 q3
a
b
a
q1 , q2 , q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Principe de la déterminisation
Idée : suivre tous les chemins en parallèle

Exemple : L’automate suivant reconnaît-il aab ?

a
a
b q0 , q1
q0 q2 q4 ...
b
a
b a
b b
q1 , q2 , q3 a
q1 q3
a
b ...
a a, b
q1 , q2 , q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 17 / 21

Définition
Définition (Automate des parties)
Etant donné un automate A = ⟨Q, V, δA , I, FA ⟩ sans ε-transition, on
construit l’automate B = ⟨P(Q), V, δB , {I} , FB ⟩, où :
δB est défini par
∀P ⊆ Q, ∀a ∈ V, δB (P, a) = {q ∈ Q | ∃p ∈ P : (p, a, q) ∈ δA }
FB = {P ⊆ Q | P ∩ FA ̸= ∅}

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 18 / 21

Définition
Définition (Automate des parties)
Etant donné un automate A = ⟨Q, V, δA , I, FA ⟩ sans ε-transition, on
construit l’automate B = ⟨P(Q), V, δB , {I} , FB ⟩, où :
δB est défini par
∀P ⊆ Q, ∀a ∈ V, δB (P, a) = {q ∈ Q | ∃p ∈ P : (p, a, q) ∈ δA }
FB = {P ⊆ Q | P ∩ FA ̸= ∅}

Remarques
P ⊆ Q ⇐⇒ P ∈ P(Q) et ∅ ⊆ Q : un état puits de B
Certains P ⊆ Q peuvent ne pas être accessibles depuis I donc on
construit B de proche en proche à partir de I.

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 18 / 21

Définition
Définition (Automate des parties)
Etant donné un automate A = ⟨Q, V, δA , I, FA ⟩ sans ε-transition, on
construit l’automate B = ⟨P(Q), V, δB , {I} , FB ⟩, où :
δB est défini par
∀P ⊆ Q, ∀a ∈ V, δB (P, a) = {q ∈ Q | ∃p ∈ P : (p, a, q) ∈ δA }
FB = {P ⊆ Q | P ∩ FA ̸= ∅}

Remarques
P ⊆ Q ⇐⇒ P ∈ P(Q) et ∅ ⊆ Q : un état puits de B
Certains P ⊆ Q peuvent ne pas être accessibles depuis I donc on
construit B de proche en proche à partir de I.

Proposition
L’automate B est un automate fini déterministe complet équivalent à A.
L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 18 / 21
Exemple
Construire un AFD (complet) équivalent à :

b
a q1 q2
a

q0 b
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 }

b
a q1 q2
a

q0 b
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 }
{q0 , q1 }

b
a q1 q2
a

q0 b
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 }
{q0 , q3 }
b
a q1 q2
a

q0 b
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 }
{q0 , q3 }
b
a q1 q2
a

q0 b
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 }
b {q0 , q2 , q3 }
a q1 q2
a

q0 b
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 } {q0 , q1 , q4 }
b {q0 , q2 , q3 }
a q1 q2
a {q0 , q1 , q4 }

q0 b
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 } {q0 , q1 , q4 } {q0 , q3 }
b {q0 , q2 , q3 }
a q1 q2
a {q0 , q1 , q4 }

q0 b
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 } {q0 , q1 , q4 } {q0 , q3 }
b {q0 , q2 , q3 } {q0 , q1 , q4 }
a q1 q2
a {q0 , q1 , q4 }

q0 b
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 } {q0 , q1 , q4 } {q0 , q3 }
b {q0 , q2 , q3 } {q0 , q1 , q4 } {q0 , q3 }
a q1 q2
a {q0 , q1 , q4 }

q0 b
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 } {q0 , q1 , q4 } {q0 , q3 }
b {q0 , q2 , q3 } {q0 , q1 , q4 } {q0 , q3 }
a q1 q2
a {q0 , q1 , q4 } {q0 , q1 }

q0 b
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 } {q0 , q1 , q4 } {q0 , q3 }
b {q0 , q2 , q3 } {q0 , q1 , q4 } {q0 , q3 }
a q1 q2
a {q0 , q1 , q4 } {q0 , q1 } {q0 , q2 , q3 , q4 }
{q0 , q2 , q3 , q4 }
q0 b
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 } {q0 , q1 , q4 } {q0 , q3 }
b {q0 , q2 , q3 } {q0 , q1 , q4 } {q0 , q3 }
a q1 q2
a {q0 , q1 , q4 } {q0 , q1 } {q0 , q2 , q3 , q4 }
{q0 , q2 , q3 , q4 } {q0 , q1 , q4 }
q0 b
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 } {q0 , q1 , q4 } {q0 , q3 }
b {q0 , q2 , q3 } {q0 , q1 , q4 } {q0 , q3 }
a q1 q2
a {q0 , q1 , q4 } {q0 , q1 } {q0 , q2 , q3 , q4 }
{q0 , q2 , q3 , q4 } {q0 , q1 , q4 } {q0 , q3 , q4 }
q0 b {q0 , q3 , q4 }
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 } {q0 , q1 , q4 } {q0 , q3 }
b {q0 , q2 , q3 } {q0 , q1 , q4 } {q0 , q3 }
a q1 q2
a {q0 , q1 , q4 } {q0 , q1 } {q0 , q2 , q3 , q4 }
{q0 , q2 , q3 , q4 } {q0 , q1 , q4 } {q0 , q3 , q4 }
q0 b {q0 , q3 , q4 } {q0 , q1 , q4 }
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 } {q0 , q1 , q4 } {q0 , q3 }
b {q0 , q2 , q3 } {q0 , q1 , q4 } {q0 , q3 }
a q1 q2
a {q0 , q1 , q4 } {q0 , q1 } {q0 , q2 , q3 , q4 }
{q0 , q2 , q3 , q4 } {q0 , q1 , q4 } {q0 , q3 , q4 }
q0 b {q0 , q3 , q4 } {q0 , q1 , q4 } {q0 , q3 , q4 }
b
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 } {q0 , q1 , q4 } {q0 , q3 }
b {q0 , q2 , q3 } {q0 , q1 , q4 } {q0 , q3 }
a q1 q2
a {q0 , q1 , q4 } {q0 , q1 } {q0 , q2 , q3 , q4 }
{q0 , q2 , q3 , q4 } {q0 , q1 , q4 } {q0 , q3 , q4 }
q0 b {q0 , q3 , q4 } {q0 , q1 , q4 } {q0 , q3 , q4 }
b Pas d’autre état accessible
a
b q3 q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 } {q0 , q1 , q4 } {q0 , q3 }
b {q0 , q2 , q3 } {q0 , q1 , q4 } {q0 , q3 }
a q1 q2
a {q0 , q1 , q4 } {q0 , q1 } {q0 , q2 , q3 , q4 }
{q0 , q2 , q3 , q4 } {q0 , q1 , q4 } {q0 , q3 , q4 }
q0 b {q0 , q3 , q4 } {q0 , q1 , q4 } {q0 , q3 , q4 }
b Pas d’autre état accessible
a
b q3 q4

7 états accessibles (sur 32 potentiels)

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 } {q0 , q1 , q4 } {q0 , q3 }
b {q0 , q2 , q3 } {q0 , q1 , q4 } {q0 , q3 }
a q1 q2
a {q0 , q1 , q4 } {q0 , q1 } {q0 , q2 , q3 , q4 }
{q0 , q2 , q3 , q4 } {q0 , q1 , q4 } {q0 , q3 , q4 }
q0 b {q0 , q3 , q4 } {q0 , q1 , q4 } {q0 , q3 , q4 }
b Pas d’autre état accessible
a
b q3 q4

7 états accessibles (sur 32 potentiels)

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Exemple
Construire un AFD (complet) équivalent à :

P(Q) a b
I {q0 , q2 } {q0 , q1 } {q0 , q3 }
{q0 , q1 } {q0 , q1 } {q0 , q2 , q3 }
{q0 , q3 } {q0 , q1 , q4 } {q0 , q3 }
b {q0 , q2 , q3 } {q0 , q1 , q4 } {q0 , q3 }
a q1 q2
a {q0 , q1 , q4 } {q0 , q1 } {q0 , q2 , q3 , q4 }
{q0 , q2 , q3 , q4 } {q0 , q1 , q4 } {q0 , q3 , q4 }
q0 b {q0 , q3 , q4 } {q0 , q1 , q4 } {q0 , q3 , q4 }
b Pas d’autre état accessible
a
b q3 q4

7 états accessibles (sur 32 potentiels)

5 états acceptants accessibles (sur 24 potentiels)

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 19 / 21

Solution

b a
q0 , q3 q0 , q2 q0 , q1

b a
b b

a q0 , q2 , q3 a

a b

a
q0 , q1 , q4 q0 , q3 , q4

b
b a

q0 , q2 , q3 , q4

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 20 / 21

Résumé
Théorème
La classe des langages réguliers est fermée :
par union
par concaténation
par concaténation itérée

Nous en verrons d’autres au cours 7.

Question
Peut-on toujours effectuer les transformations
OK OK
AF (N D) ⇐===⇒ AF (N D) − ε ⇐===⇒ AFD ?

L. Rieg (Ensimag 1A) Théorie des Langages 1 Année 2024-2025 21 / 21