lycée louis-le-grand option informatique

Automates
Jean-Pierre Becirspahic
Lycée Louis-Le-Grand

2015-2016 — Page 1/18

lycée louis-le-grand option informatique

Automates finis déterministes

Un automate est une machine abstraite qui peut prendre un nombre fini
d’états, qui reçoit en entrée un mot écrit sur un alphabet Σ, et qui change
d’état à la lecture des lettres de ce dernier.
Certains états sont acceptants ; à la fin de la lecture du mot passé en
entrée l’automate aura changé d’état ; on dira que le mot est accepté si
l’état final est un état acceptant, et rejeté dans le cas contraire.
a b
b
q0 a q1 q2

L’état initial q0 est désigné par une flèche entrante ; les états acceptants
(ici q2 ) sont représentés par une flèche sortante.

JP Becirspahic — Automates — 2015-2016 — Page 2/18

lycée louis-le-grand option informatique

Automates finis déterministes

Un automate est une machine abstraite qui peut prendre un nombre fini
d’états, qui reçoit en entrée un mot écrit sur un alphabet Σ, et qui change
d’état à la lecture des lettres de ce dernier.
Certains états sont acceptants ; à la fin de la lecture du mot passé en
entrée l’automate aura changé d’état ; on dira que le mot est accepté si
l’état final est un état acceptant, et rejeté dans le cas contraire.
a b
b
q0 a q1 q2

Pour qu’un mot soit lu et aboutisse à un état acceptant il faut

et il suffit qu’il débute par un a et se termine par un b ; on
dira que cet automate reconnait le langage des mots de aΣ∗ b .
La lecture du mot abbaabab fait passer l’automate par les états :
a b b a a b a b
q0 → q1 → q2 → q2 → q1 → q1 → q2 → q1 → q2 .

JP Becirspahic — Automates — 2015-2016 — Page 2/18

lycée louis-le-grand option informatique

Automates finis déterministes

Un automate est une machine abstraite qui peut prendre un nombre fini
d’états, qui reçoit en entrée un mot écrit sur un alphabet Σ, et qui change
d’état à la lecture des lettres de ce dernier.
Certains états sont acceptants ; à la fin de la lecture du mot passé en
entrée l’automate aura changé d’état ; on dira que le mot est accepté si
l’état final est un état acceptant, et rejeté dans le cas contraire.
a b
b
q0 a q1 q2

Le couple (q0 , b ) est un blocage de l’automate. Un automate sans blocage

est dit complet.

JP Becirspahic — Automates — 2015-2016 — Page 2/18

lycée louis-le-grand option informatique

Automates finis déterministes

Un automate est une machine abstraite qui peut prendre un nombre fini
d’états, qui reçoit en entrée un mot écrit sur un alphabet Σ, et qui change
d’état à la lecture des lettres de ce dernier.
Certains états sont acceptants ; à la fin de la lecture du mot passé en
entrée l’automate aura changé d’état ; on dira que le mot est accepté si
l’état final est un état acceptant, et rejeté dans le cas contraire.
a b
b
q0 a q1 q2

a
b

q3

a, b

Il est toujours possible de rendre un automate complet en ajoutant un

puit.
JP Becirspahic — Automates — 2015-2016 — Page 2/18
lycée louis-le-grand option informatique

Automates finis déterministes

Un second exemple

Σ = {0, 1} ; le mot lu par l’automate correspond à l’écriture binaire d’un

entier n. Cet automate reconnait les entiers n qui sont divisibles par 3 :
0 1
1 0
q0 q1 q2

1 0

JP Becirspahic — Automates — 2015-2016 — Page 2/18

lycée louis-le-grand option informatique

Automates finis déterministes

Un second exemple

Σ = {0, 1} ; le mot lu par l’automate correspond à l’écriture binaire d’un

entier n. Cet automate reconnait les entiers n qui sont divisibles par 3 :
0 1
1 0
q0 q1 q2

1 0

L’état final atteint est q0 si n ≡ 0 mod 3, q1 si n ≡ 1 mod 3 et q2 si n ≡ 2 mod 3.

JP Becirspahic — Automates — 2015-2016 — Page 2/18

lycée louis-le-grand option informatique

Automates finis déterministes

Un second exemple

Σ = {0, 1} ; le mot lu par l’automate correspond à l’écriture binaire d’un

entier n. Cet automate reconnait les entiers n qui sont divisibles par 3 :
0 1
1 0
q0 q1 q2

1 0

L’état final atteint est q0 si n ≡ 0 mod 3, q1 si n ≡ 1 mod 3 et q2 si n ≡ 2 mod 3.

• C’est vrai si n = 0 ;

JP Becirspahic — Automates — 2015-2016 — Page 2/18

lycée louis-le-grand option informatique

Automates finis déterministes

Un second exemple

Σ = {0, 1} ; le mot lu par l’automate correspond à l’écriture binaire d’un

entier n. Cet automate reconnait les entiers n qui sont divisibles par 3 :
0 1
1 0
q0 q1 q2

1 0

L’état final atteint est q0 si n ≡ 0 mod 3, q1 si n ≡ 1 mod 3 et q2 si n ≡ 2 mod 3.

• C’est vrai si n = 0 ;
• si n > 1 on pose n = 2p + r avec r ∈ {0, 1}.
Avant la lecture de r l’automate se trouve dans l’état qi avec p ≡ i mod 3.

JP Becirspahic — Automates — 2015-2016 — Page 2/18

lycée louis-le-grand option informatique

Automates finis déterministes

Un second exemple

Σ = {0, 1} ; le mot lu par l’automate correspond à l’écriture binaire d’un

entier n. Cet automate reconnait les entiers n qui sont divisibles par 3 :
0 1
1 0
q0 q1 q2

1 0

L’état final atteint est q0 si n ≡ 0 mod 3, q1 si n ≡ 1 mod 3 et q2 si n ≡ 2 mod 3.

• C’est vrai si n = 0 ;
• si n > 1 on pose n = 2p + r avec r ∈ {0, 1}.
Avant la lecture de r l’automate se trouve dans l’état qi avec p ≡ i mod 3.
• Si i = 0 alors n ≡ r mod 3 et si r = 0 l’automate reste à l’état q0 , si
r = 1 l’automate passe à l’état q1 ;

JP Becirspahic — Automates — 2015-2016 — Page 2/18

lycée louis-le-grand option informatique

Automates finis déterministes

Un second exemple

Σ = {0, 1} ; le mot lu par l’automate correspond à l’écriture binaire d’un

entier n. Cet automate reconnait les entiers n qui sont divisibles par 3 :
0 1
1 0
q0 q1 q2

1 0

L’état final atteint est q0 si n ≡ 0 mod 3, q1 si n ≡ 1 mod 3 et q2 si n ≡ 2 mod 3.

• C’est vrai si n = 0 ;
• si n > 1 on pose n = 2p + r avec r ∈ {0, 1}.
Avant la lecture de r l’automate se trouve dans l’état qi avec p ≡ i mod 3.
• Si i = 0 alors n ≡ r mod 3 et si r = 0 l’automate reste à l’état q0 , si
r = 1 l’automate passe à l’état q1 ;
• si i = 1 alors n ≡ 2 + r mod 3 et si r = 0 l’automate passe à l’état q2 , si
r = 1 l’automate passe à l’état q0 ;

JP Becirspahic — Automates — 2015-2016 — Page 2/18

lycée louis-le-grand option informatique

Automates finis déterministes

Un second exemple

Σ = {0, 1} ; le mot lu par l’automate correspond à l’écriture binaire d’un

entier n. Cet automate reconnait les entiers n qui sont divisibles par 3 :
0 1
1 0
q0 q1 q2

1 0

L’état final atteint est q0 si n ≡ 0 mod 3, q1 si n ≡ 1 mod 3 et q2 si n ≡ 2 mod 3.

• C’est vrai si n = 0 ;
• si n > 1 on pose n = 2p + r avec r ∈ {0, 1}.
Avant la lecture de r l’automate se trouve dans l’état qi avec p ≡ i mod 3.
• Si i = 0 alors n ≡ r mod 3 et si r = 0 l’automate reste à l’état q0 , si
r = 1 l’automate passe à l’état q1 ;
• si i = 1 alors n ≡ 2 + r mod 3 et si r = 0 l’automate passe à l’état q2 , si
r = 1 l’automate passe à l’état q0 ;
• si i = 2 alors n ≡ 1 + r mod 3 et si r = 0 l’automate passe à l’état q1 , si
r = 1 l’automate reste à l’état q2 .
JP Becirspahic — Automates — 2015-2016 — Page 2/18
lycée louis-le-grand option informatique

Définition formelle d’un automate

Un automate à états finis déterministe est défini par A = (Σ, Q , q0 , F , δ).
• Σ est un alphabet (fini) ;
• Q est un ensemble fini d’états de A ;
• q0 ∈ Q est l’état initial ;
• F ⊂ Q est l’ensemble des états acceptants (ou finaux) ;
• δ est une application d’une partie de Q × Σ dans Q , appelée fonction
de transition.
Lorsque δ est définie sur Q × Σ tout entier, l’automate A est dit complet.

JP Becirspahic — Automates — 2015-2016 — Page 3/18

lycée louis-le-grand option informatique

Définition formelle d’un automate

Un automate à états finis déterministe est défini par A = (Σ, Q , q0 , F , δ).
• Σ est un alphabet (fini) ;
• Q est un ensemble fini d’états de A ;
• q0 ∈ Q est l’état initial ;
• F ⊂ Q est l’ensemble des états acceptants (ou finaux) ;
• δ est une application d’une partie de Q × Σ dans Q , appelée fonction
de transition.
Lorsque δ est définie sur Q × Σ tout entier, l’automate A est dit complet.
a
Une transition δ(qi , a) = qj est représentée par qi −→ qj . Un chemin dans
a1 a2 an
A est une suite finie de transitions consécutives q0 −→ q1 −→ · · · −→ qn
débutant par l’état initial q0 . Le mot a1 a2 · · · an est appelé l’étiquette du
chemin.

JP Becirspahic — Automates — 2015-2016 — Page 3/18

lycée louis-le-grand option informatique

Définition formelle d’un automate

Un automate à états finis déterministe est défini par A = (Σ, Q , q0 , F , δ).
• Σ est un alphabet (fini) ;
• Q est un ensemble fini d’états de A ;
• q0 ∈ Q est l’état initial ;
• F ⊂ Q est l’ensemble des états acceptants (ou finaux) ;
• δ est une application d’une partie de Q × Σ dans Q , appelée fonction
de transition.
Lorsque δ est définie sur Q × Σ tout entier, l’automate A est dit complet.
a
Une transition δ(qi , a) = qj est représentée par qi −→ qj . Un chemin dans
a1 a2 an
A est une suite finie de transitions consécutives q0 −→ q1 −→ · · · −→ qn
débutant par l’état initial q0 . Le mot a1 a2 · · · an est appelé l’étiquette du
chemin.
Un chemin est acceptant lorsque l’état d’arrivée est un état acceptant ;
un mot de Σ∗ est reconnu par A lorsqu’il est l’étiquette d’un chemin ac-
ceptant. Le langage L (A ) reconnu par A est l’ensemble des mots recon-
nus par A .
JP Becirspahic — Automates — 2015-2016 — Page 3/18
lycée louis-le-grand option informatique

Définition formelle d’un automate

Exemple

• Σ = {a, b } ; δ a b
q0 q1 q0
• Q = {q0 , q1 , q2 } ; q1 q2 q0
• F = {q0 , q1 } ; q2 q2 q2
b a, b
a a
q0 q1 q2

On note Li l’ensemble des étiquettes des chemins débutant par qi et finis-

sant par un état acceptant.

L0 = ε + bL0 + aL1 , L1 = ε + bL0 et L2 = ∅.

JP Becirspahic — Automates — 2015-2016 — Page 3/18

lycée louis-le-grand option informatique

Définition formelle d’un automate

Exemple

• Σ = {a, b } ; δ a b
q0 q1 q0
• Q = {q0 , q1 , q2 } ; q1 q2 q0
• F = {q0 , q1 } ; q2 q2 q2
b a, b
a a
q0 q1 q2

On note Li l’ensemble des étiquettes des chemins débutant par qi et finis-

sant par un état acceptant.

L0 = ε + bL0 + aL1 , L1 = ε + bL0 et L2 = ∅.

On en déduit que L0 = ε + bL0 + a(ε + bL0 ) = (b + ab )L0 + (ε + a). D’après

le lemme d’Arden, L0 = (b +ab )∗ (ε+a). Le langage reconnu par cet auto-
mate est le langage des mots qui ne comportent pas deux a consécutifs.
JP Becirspahic — Automates — 2015-2016 — Page 3/18
lycée louis-le-grand option informatique

Émondage
Deux automates sont dits équivalents lorsqu’ils reconnaissent le même
langage :
b a, b b
a a a
q0 q1 q2 q0 q1

b b

Le premier est complet, le second ne l’est pas.

JP Becirspahic — Automates — 2015-2016 — Page 4/18

lycée louis-le-grand option informatique

Émondage
Deux automates sont dits équivalents lorsqu’ils reconnaissent le même
langage :
b a, b b
a a a
q0 q1 q2 q0 q1

b b

un état q qu’il est :

• accessible lorsqu’il existe un chemin menant de l’état initial q0 à q ;
• co-accessible lorsqu’il existe un chemin menant de q à un état
acceptant.

JP Becirspahic — Automates — 2015-2016 — Page 4/18

lycée louis-le-grand option informatique

Émondage
Deux automates sont dits équivalents lorsqu’ils reconnaissent le même
langage :
b a, b b
a a a
q0 q1 q2 q0 q1

b b

un état q qu’il est :

• accessible lorsqu’il existe un chemin menant de l’état initial q0 à q ;
• co-accessible lorsqu’il existe un chemin menant de q à un état
acceptant.
Un état accessible et co-accessible est dit utile. On obtient un automate
équivalent en supprimant tous les états inutiles ainsi que les transitions
qui les concernent.

JP Becirspahic — Automates — 2015-2016 — Page 4/18

lycée louis-le-grand option informatique

Émondage
Exemple a b
b
q0 a q1 q2

a
b
b

q3 q4
a

a, b

L’automate ci-dessus possède deux états inutiles : q4 n’est pas accessible

et q3 n’est pas co-accessible.

JP Becirspahic — Automates — 2015-2016 — Page 4/18

lycée louis-le-grand option informatique

Émondage
Exemple a b
b
q0 a q1 q2

a
b
b

q3 q4
a

a, b

L’automate ci-dessus possède deux états inutiles : q4 n’est pas accessible

et q3 n’est pas co-accessible. Il est équivalent à :
a b
b
q0 a q1 q2

et reconnait le langage dénoté par a(a + b )∗ b .

JP Becirspahic — Automates — 2015-2016 — Page 4/18
lycée louis-le-grand option informatique

Mise en œuvre
On utilise le type char pour représenter l’alphabet Σ, le type int pour l’en-
semble des états et un dictionnaire pour énumérer la liste des transi-
tions possibles. Pour simplifier, ce dictionnaire sera représenté par le type
( int * char) * int list .

JP Becirspahic — Automates — 2015-2016 — Page 5/18

lycée louis-le-grand option informatique

Mise en œuvre
On utilise le type char pour représenter l’alphabet Σ, le type int pour l’en-
semble des états et un dictionnaire pour énumérer la liste des transi-
tions possibles. Pour simplifier, ce dictionnaire sera représenté par le type
( int * char) * int list .

type dfa = {Start: int ;

Accept: int list ;
Delta: ((int * char) * int) list} ;;

let chemin a m =
let rec aux q = function
| k when k = string_length m −> q
| k −> aux (assoc (q, m.[k]) a.Delta) (k+1)
in aux a.Start 0 ;;

let reconnu a m =
try mem (chemin a m) a.Accept
with Not_found −> false ;;

JP Becirspahic — Automates — 2015-2016 — Page 5/18

lycée louis-le-grand option informatique

Automates non déterministes

Un NFA est défini par un quintuplet A = (Σ, Q , I , F , δ) où :
• Σ est un alphabet (fini) ;
• Q est un ensemble fini d’états de A ;
• I ⊂ Q est l’ensemble des états initiaux ;
• F ⊂ Q est l’ensemble des états acceptants ;
• δ est une application d’une partie de Q × Σ dans P (Q ) : la fonction
de transition.

JP Becirspahic — Automates — 2015-2016 — Page 6/18

lycée louis-le-grand option informatique

Automates non déterministes

Un NFA est défini par un quintuplet A = (Σ, Q , I , F , δ) où :
• Σ est un alphabet (fini) ;
• Q est un ensemble fini d’états de A ;
• I ⊂ Q est l’ensemble des états initiaux ;
• F ⊂ Q est l’ensemble des états acceptants ;
• δ est une application d’une partie de Q × Σ dans P (Q ) : la fonction
de transition.
Une transition est un triplet (qi , a, qj ) tel que qj ∈ δ(qi , a), représentée
a
par qi −→ qj . Un chemin est une suite finie de transitions consécutives
a1 a2 an
q0 −→ q1 −→ · · · −→ qn .

JP Becirspahic — Automates — 2015-2016 — Page 6/18

lycée louis-le-grand option informatique

Automates non déterministes

Un NFA est défini par un quintuplet A = (Σ, Q , I , F , δ) où :
• Σ est un alphabet (fini) ;
• Q est un ensemble fini d’états de A ;
• I ⊂ Q est l’ensemble des états initiaux ;
• F ⊂ Q est l’ensemble des états acceptants ;
• δ est une application d’une partie de Q × Σ dans P (Q ) : la fonction
de transition.
Une transition est un triplet (qi , a, qj ) tel que qj ∈ δ(qi , a), représentée
a
par qi −→ qj . Un chemin est une suite finie de transitions consécutives
a1 a2 an
q0 −→ q1 −→ · · · −→ qn .
Un mot de Σ∗ est reconnu par l’automate A s’il étiquette un chemin me-
nant d’un état initial à un état acceptant. Le langage des mots reconnus
par l’automate A est noté L (A ).

JP Becirspahic — Automates — 2015-2016 — Page 6/18

lycée louis-le-grand option informatique

Automates non déterministes

Un NFA est défini par un quintuplet A = (Σ, Q , I , F , δ) où :
• Σ est un alphabet (fini) ;
• Q est un ensemble fini d’états de A ;
• I ⊂ Q est l’ensemble des états initiaux ;
• F ⊂ Q est l’ensemble des états acceptants ;
• δ est une application d’une partie de Q × Σ dans P (Q ) : la fonction
de transition.
Exemple : l’automate ci dessous reconnait le langage dénoté par

a(a + b )∗ b .

a, b

q0 a q1 b q2

JP Becirspahic — Automates — 2015-2016 — Page 6/18

lycée louis-le-grand option informatique

Déterminisation
Considérons donc un automate non-déterministe A = (Σ, Q , I , F , δ) et po-
sons A 0 = (Σ, P (Q ), I , F 0 , δ0 ) avec :
n o [
F 0 = P ∈ P (Q ) P ∩F , ∅ et ∀(P , a) ∈ P (Q )×Σ, δ0 (P , a) = δ(q, a).
q∈P

Si A est un automate non-déterministe à n états, A 0 est un automate dé-

terministe à 2n états.

JP Becirspahic — Automates — 2015-2016 — Page 7/18

lycée louis-le-grand option informatique

Déterminisation
Considérons donc un automate non-déterministe A = (Σ, Q , I , F , δ) et po-
sons A 0 = (Σ, P (Q ), I , F 0 , δ0 ) avec :
n o [
F 0 = P ∈ P (Q ) P ∩F , ∅ et ∀(P , a) ∈ P (Q )×Σ, δ0 (P , a) = δ(q, a).
q∈P
a, b

q0 a q1 b q2

États et transitions de A 0 :
δ0 a b δ0 a b
∅ ∅ ∅ {q0 , q1 } {q1 } {q1 , q2 }
∗ {q0 } {q1 } ∅ ∗ {q1 , q2 } {q1 } {q1 , q2 }
{q1 } {q1 } {q1 , q2 } ∗ {q0 , q2 } {q1 } ∅
{q2 } ∅ ∅ ∗ {q0 , q1 , q2 } {q1 } {q1 , q2 }

* : état initial, * : états acceptants.

JP Becirspahic — Automates — 2015-2016 — Page 7/18

lycée louis-le-grand option informatique

Déterminisation
Considérons donc un automate non-déterministe A = (Σ, Q , I , F , δ) et po-
sons A 0 = (Σ, P (Q ), I , F 0 , δ0 ) avec :
n o [
F 0 = P ∈ P (Q ) P ∩F , ∅ et ∀(P , a) ∈ P (Q )×Σ, δ0 (P , a) = δ(q, a).
q∈P
a, b

q0 a q1 b q2

Dans la pratique on écrit que les états accessibles :

δ0 a b
∗ {q0 } {q1 } − → q00
{q1 } {q1 } {q1 , q2 } → q10
∗ {q1 , q2 } {q1 } {q1 , q2 } → q20

JP Becirspahic — Automates — 2015-2016 — Page 7/18

lycée louis-le-grand option informatique

Déterminisation
Considérons donc un automate non-déterministe A = (Σ, Q , I , F , δ) et po-
sons A 0 = (Σ, P (Q ), I , F 0 , δ0 ) avec :
n o [
F 0 = P ∈ P (Q ) P ∩F , ∅ et ∀(P , a) ∈ P (Q )×Σ, δ0 (P , a) = δ(q, a).
q∈P
a, b

q0 a q1 b q2

On obtient l’automate déterminisé suivant :

a b
b
a
q00 q10 q20
a

A 0 reconnait lui aussi le langage dénoté par a(a + b )∗ b .

JP Becirspahic — Automates — 2015-2016 — Page 7/18

lycée louis-le-grand option informatique

Déterminisation
Les automates A et A 0 reconnaissent le même langage.

JP Becirspahic — Automates — 2015-2016 — Page 7/18

lycée louis-le-grand option informatique

Déterminisation
Les automates A et A 0 reconnaissent le même langage.
On montre par récurrence sur |u| que pour tout mot u ∈ Σ∗ , il existe dans A un
chemin étiqueté par u menant à un état q si et seulement s’il existe dans A 0 un
chemin étiqueté par u menant à un état P contenant q.

JP Becirspahic — Automates — 2015-2016 — Page 7/18

lycée louis-le-grand option informatique

Déterminisation
Les automates A et A 0 reconnaissent le même langage.
On montre par récurrence sur |u| que pour tout mot u ∈ Σ∗ , il existe dans A un
chemin étiqueté par u menant à un état q si et seulement s’il existe dans A 0 un
chemin étiqueté par u menant à un état P contenant q.
• Dans A tout chemin étiqueté par ε mène à un élément de I ; dans A 0 tout
chemin étiqueté par ε mène à l’état I .

JP Becirspahic — Automates — 2015-2016 — Page 7/18

lycée louis-le-grand option informatique

Déterminisation
Les automates A et A 0 reconnaissent le même langage.
On montre par récurrence sur |u| que pour tout mot u ∈ Σ∗ , il existe dans A un
chemin étiqueté par u menant à un état q si et seulement s’il existe dans A 0 un
chemin étiqueté par u menant à un état P contenant q.
• Dans A tout chemin étiqueté par ε mène à un élément de I ; dans A 0 tout
chemin étiqueté par ε mène à l’état I .
• Si u , ε, supposons le résultat acquis pour tout mot de longueur strictement
inférieure, et posons u = a1 a2 · · · an .

JP Becirspahic — Automates — 2015-2016 — Page 7/18

lycée louis-le-grand option informatique

Déterminisation
Les automates A et A 0 reconnaissent le même langage.
On montre par récurrence sur |u| que pour tout mot u ∈ Σ∗ , il existe dans A un
chemin étiqueté par u menant à un état q si et seulement s’il existe dans A 0 un
chemin étiqueté par u menant à un état P contenant q.
• Dans A tout chemin étiqueté par ε mène à un élément de I ; dans A 0 tout
chemin étiqueté par ε mène à l’état I .
• Si u , ε, supposons le résultat acquis pour tout mot de longueur strictement
inférieure, et posons u = a1 a2 · · · an .
a1 a2 an
Considérons un chemin q0 −→ q1 −→ · · · −→ qn dans A .
a1 a2 an−1
Il existe dans A 0 un chemin I −→ P1 −→ · · · −→ Pn−1 tel que qn−1 ∈ Pn−1 .

JP Becirspahic — Automates — 2015-2016 — Page 7/18

lycée louis-le-grand option informatique

Déterminisation
Les automates A et A 0 reconnaissent le même langage.
On montre par récurrence sur |u| que pour tout mot u ∈ Σ∗ , il existe dans A un
chemin étiqueté par u menant à un état q si et seulement s’il existe dans A 0 un
chemin étiqueté par u menant à un état P contenant q.
• Dans A tout chemin étiqueté par ε mène à un élément de I ; dans A 0 tout
chemin étiqueté par ε mène à l’état I .
• Si u , ε, supposons le résultat acquis pour tout mot de longueur strictement
inférieure, et posons u = a1 a2 · · · an .
a1 a2 an
Considérons un chemin q0 −→ q1 −→ · · · −→ qn dans A .
a1 a2 an−1
Il existe dans A 0 un chemin I −→ P1 −→ · · · −→ Pn−1 tel que qn−1 ∈ Pn−1 .
qn ∈ δ(qn−1 , an ) donc qn ∈ δ0 (Pn−1 , an ). En posant Pn = δ0 (Pn−1 , an ) on établit un
a1 a2 an
chemin I −→ P1 −→ · · · −→ Pn tel que qn ∈ Pn .

JP Becirspahic — Automates — 2015-2016 — Page 7/18

lycée louis-le-grand option informatique

Déterminisation
Les automates A et A 0 reconnaissent le même langage.
On montre par récurrence sur |u| que pour tout mot u ∈ Σ∗ , il existe dans A un
chemin étiqueté par u menant à un état q si et seulement s’il existe dans A 0 un
chemin étiqueté par u menant à un état P contenant q.
• Dans A tout chemin étiqueté par ε mène à un élément de I ; dans A 0 tout
chemin étiqueté par ε mène à l’état I .
• Si u , ε, supposons le résultat acquis pour tout mot de longueur strictement
inférieure, et posons u = a1 a2 · · · an .
a1 a2 an
Réciproquement, considérons un chemin I −→ P1 −→ · · · −→ Pn dans A , et consi-
dérons un élément qn ∈ Pn .

JP Becirspahic — Automates — 2015-2016 — Page 7/18

lycée louis-le-grand option informatique

Déterminisation
Les automates A et A 0 reconnaissent le même langage.
On montre par récurrence sur |u| que pour tout mot u ∈ Σ∗ , il existe dans A un
chemin étiqueté par u menant à un état q si et seulement s’il existe dans A 0 un
chemin étiqueté par u menant à un état P contenant q.
• Dans A tout chemin étiqueté par ε mène à un élément de I ; dans A 0 tout
chemin étiqueté par ε mène à l’état I .
• Si u , ε, supposons le résultat acquis pour tout mot de longueur strictement
inférieure, et posons u = a1 a2 · · · an .
a1 a2 an
Réciproquement, considérons un chemin I −→ P1 −→ · · · −→ Pn dans A , et consi-
dérons un élément qn ∈ Pn .
Il existe un état qn−1 ∈ Pn−1 tel que qn ∈ δ(qn−1 , an ), et par hypothèse de récur-
a1 a2 an−1
rence il existe un chemin q0 −→ q1 −→ · · · −→ qn−1 dans A .

JP Becirspahic — Automates — 2015-2016 — Page 7/18

lycée louis-le-grand option informatique

Déterminisation
Les automates A et A 0 reconnaissent le même langage.
On montre par récurrence sur |u| que pour tout mot u ∈ Σ∗ , il existe dans A un
chemin étiqueté par u menant à un état q si et seulement s’il existe dans A 0 un
chemin étiqueté par u menant à un état P contenant q.
• Dans A tout chemin étiqueté par ε mène à un élément de I ; dans A 0 tout
chemin étiqueté par ε mène à l’état I .
• Si u , ε, supposons le résultat acquis pour tout mot de longueur strictement
inférieure, et posons u = a1 a2 · · · an .
a1 a2 an
Réciproquement, considérons un chemin I −→ P1 −→ · · · −→ Pn dans A , et consi-
dérons un élément qn ∈ Pn .
Il existe un état qn−1 ∈ Pn−1 tel que qn ∈ δ(qn−1 , an ), et par hypothèse de récur-
a1 a2 an−1
rence il existe un chemin q0 −→ q1 −→ · · · −→ qn−1 dans A .
a1 a2 an
Ceci prouve l’existence d’un chemin q0 −→ q1 −→ · · · −→ qn .

JP Becirspahic — Automates — 2015-2016 — Page 7/18

lycée louis-le-grand option informatique

Déterminisation
Les automates A et A 0 reconnaissent le même langage.
On montre par récurrence sur |u| que pour tout mot u ∈ Σ∗ , il existe dans A un
chemin étiqueté par u menant à un état q si et seulement s’il existe dans A 0 un
chemin étiqueté par u menant à un état P contenant q.
• Dans A tout chemin étiqueté par ε mène à un élément de I ; dans A 0 tout
chemin étiqueté par ε mène à l’état I .
• Si u , ε, supposons le résultat acquis pour tout mot de longueur strictement
inférieure, et posons u = a1 a2 · · · an .
a1 a2 an
Réciproquement, considérons un chemin I −→ P1 −→ · · · −→ Pn dans A , et consi-
dérons un élément qn ∈ Pn .
Il existe un état qn−1 ∈ Pn−1 tel que qn ∈ δ(qn−1 , an ), et par hypothèse de récur-
a1 a2 an−1
rence il existe un chemin q0 −→ q1 −→ · · · −→ qn−1 dans A .
a1 a2 an
Ceci prouve l’existence d’un chemin q0 −→ q1 −→ · · · −→ qn .
n o
Sachant que F 0 = P ∈ P (Q ) P ∩ F , ∅ ceci prouve qu’un mot est reconnu par A
si et seulement s’il est reconnu par A 0 .
JP Becirspahic — Automates — 2015-2016 — Page 7/18
lycée louis-le-grand option informatique

Un exemple de coût exponentiel

Considérons le langage L dénoté par (a + b )∗ a(a + b )n−1 . Il est facile
d’obtenir un automate non-déterministe à n + 1 états qui le reconnait :
a, b

a a, b a, b a, b
q0 q1 q2 ··· qn

JP Becirspahic — Automates — 2015-2016 — Page 8/18

lycée louis-le-grand option informatique

Un exemple de coût exponentiel

Considérons le langage L dénoté par (a + b )∗ a(a + b )n−1 . Il est facile
d’obtenir un automate non-déterministe à n + 1 états qui le reconnait :
a, b

a a, b a, b a, b
q0 q1 q2 ··· qn

Tout automate déterministe qui reconnait L possède au moins 2n états.

JP Becirspahic — Automates — 2015-2016 — Page 8/18

lycée louis-le-grand option informatique

Un exemple de coût exponentiel

Considérons le langage L dénoté par (a + b )∗ a(a + b )n−1 . Il est facile
d’obtenir un automate non-déterministe à n + 1 états qui le reconnait :
a, b

a a, b a, b a, b
q0 q1 q2 ··· qn

Tout automate déterministe qui reconnait L possède au moins 2n états.

Considérons un tel automate A et notons q0 son état initial. À tout mot u de n
lettres on associe l’état q(u) auquel aboutit le chemin étiqueté par u. On définit
ainsi une application q : {a, b }n → Q .

JP Becirspahic — Automates — 2015-2016 — Page 8/18

lycée louis-le-grand option informatique

Un exemple de coût exponentiel

Considérons le langage L dénoté par (a + b )∗ a(a + b )n−1 . Il est facile
d’obtenir un automate non-déterministe à n + 1 états qui le reconnait :
a, b

a a, b a, b a, b
q0 q1 q2 ··· qn

Tout automate déterministe qui reconnait L possède au moins 2n états.

Considérons un tel automate A et notons q0 son état initial. À tout mot u de n
lettres on associe l’état q(u) auquel aboutit le chemin étiqueté par u. On définit
ainsi une application q : {a, b }n → Q .
On considère deux mots u , v tels que q(u) = q(v) et le plus long suffixe w com-
mun à u et à v. Sans perte de généralité on peut poser u = u 0 aw et v = v 0 bw.

JP Becirspahic — Automates — 2015-2016 — Page 8/18

lycée louis-le-grand option informatique

Un exemple de coût exponentiel

Considérons le langage L dénoté par (a + b )∗ a(a + b )n−1 . Il est facile
d’obtenir un automate non-déterministe à n + 1 états qui le reconnait :
a, b

a a, b a, b a, b
q0 q1 q2 ··· qn

Tout automate déterministe qui reconnait L possède au moins 2n états.

Considérons un tel automate A et notons q0 son état initial. À tout mot u de n
lettres on associe l’état q(u) auquel aboutit le chemin étiqueté par u. On définit
ainsi une application q : {a, b }n → Q .
On considère deux mots u , v tels que q(u) = q(v) et le plus long suffixe w com-
mun à u et à v. Sans perte de généralité on peut poser u = u 0 aw et v = v 0 bw.
On complète w pour former un mot ww 0 de longueur n − 1.
Le mot uw 0 = u 0 aww 0 est reconnu par A mais pas vw 0 = v 0 bww 0 .

JP Becirspahic — Automates — 2015-2016 — Page 8/18

lycée louis-le-grand option informatique

Un exemple de coût exponentiel

Considérons le langage L dénoté par (a + b )∗ a(a + b )n−1 . Il est facile
d’obtenir un automate non-déterministe à n + 1 états qui le reconnait :
a, b

a a, b a, b a, b
q0 q1 q2 ··· qn

Tout automate déterministe qui reconnait L possède au moins 2n états.

Considérons un tel automate A et notons q0 son état initial. À tout mot u de n
lettres on associe l’état q(u) auquel aboutit le chemin étiqueté par u. On définit
ainsi une application q : {a, b }n → Q .
On considère deux mots u , v tels que q(u) = q(v) et le plus long suffixe w com-
mun à u et à v. Sans perte de généralité on peut poser u = u 0 aw et v = v 0 bw.
On complète w pour former un mot ww 0 de longueur n − 1.
Le mot uw 0 = u 0 aww 0 est reconnu par A mais pas vw 0 = v 0 bww 0 .
Mais A est déterministe et q(u) = q(v) donc les chemins étiquetés par uw 0 et vw 0
doivent mener au même état (ou être tous deux bloquants) ce qui est absurde.

JP Becirspahic — Automates — 2015-2016 — Page 8/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Si u ∈ Σ∗ est un mot donné, on souhaite un automate déterministe qui
reconnait le langage Σ∗ uΣ∗ .

JP Becirspahic — Automates — 2015-2016 — Page 9/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Si u ∈ Σ∗ est un mot donné, on souhaite un automate déterministe qui
reconnait le langage Σ∗ uΣ∗ .
Ce problème est aisément résolu à l’aide d’un automate non-déterministe :
si u = a1 a2 · · · an il suffit de considérer :
Σ Σ

a1 a2 a3 an
q0 q1 q2 ··· qn

Il reste ensuite à déterminiser cet automate.

JP Becirspahic — Automates — 2015-2016 — Page 9/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Si u ∈ Σ∗ est un mot donné, on souhaite un automate déterministe qui
reconnait le langage Σ∗ uΣ∗ .
Exemple : recherche du mot aba sur l’alphabet {a, b }.
a, b a, b

q0 a q1 b q2 a q3

JP Becirspahic — Automates — 2015-2016 — Page 9/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Si u ∈ Σ∗ est un mot donné, on souhaite un automate déterministe qui
reconnait le langage Σ∗ uΣ∗ .
Exemple : recherche du mot aba sur l’alphabet {a, b }.
a, b a, b

q0 a q1 b q2 a q3

δ0 a b
∗ {q0 } {q0 , q1 } {q0 } → q00
{q0 , q1 } {q0 , q1 } {q0 , q2 } → q10
{q0 , q2 } {q0 , q1 , q3 } {q0 } → q20
∗ {q0 , q1 , q3 } {q0 , q1 , q3 } {q0 , q2 , q3 } → q30
∗ {q0 , q2 , q3 } {q0 , q1 , q3 } {q0 , q3 } → q40
∗ {q0 , q3 } {q0 , q1 , q3 } {q0 , q3 } → q50

JP Becirspahic — Automates — 2015-2016 — Page 9/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Si u ∈ Σ∗ est un mot donné, on souhaite un automate déterministe qui
reconnait le langage Σ∗ uΣ∗ .
Exemple : recherche du mot aba sur l’alphabet {a, b }.
On obtient l’automate déterminisé suivant :
b a

a b
q00 q10 q20

b
a

b b

q50 q40 q30

a

b a
a

JP Becirspahic — Automates — 2015-2016 — Page 9/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Si u ∈ Σ∗ est un mot donné, on souhaite un automate déterministe qui
reconnait le langage Σ∗ uΣ∗ .
Exemple : recherche du mot aba sur l’alphabet {a, b }.
Les états q40 et q50 peuvent être supprimés :

b a a, b

a b a
q00 q10 q20 q30

JP Becirspahic — Automates — 2015-2016 — Page 9/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Algorithme KMP

On note P (u) l’ensemble des préfixes de u, et on note s(v) le plus long

suffixe de v qui soit dans P (u).
On considère l’automate déterministe A = (Σ, P (u), {ε}, {u}, δ) où la fonc-
tion de transition est définie par :
∀p ∈ P (u), ∀x ∈ Σ, δ(p, x) = s(px)

JP Becirspahic — Automates — 2015-2016 — Page 10/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Algorithme KMP

On note P (u) l’ensemble des préfixes de u, et on note s(v) le plus long

suffixe de v qui soit dans P (u).
On considère l’automate déterministe A = (Σ, P (u), {ε}, {u}, δ) où la fonc-
tion de transition est définie par :
∀p ∈ P (u), ∀x ∈ Σ, δ(p, x) = s(px)
Exemple. Le cas du mot u = aba.
δ a b
ε a ε
a a ab
ab aba ε
aba a ab
a
b a
a
a b
ε a ab aba

b
b
JP Becirspahic — Automates — 2015-2016 — Page 10/18
lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Algorithme KMP

On note P (u) l’ensemble des préfixes du mot u.

On note s(v) le plus long suffixe de v dans P (u).
On pose A = (Σ, P (u), {ε}, {u}, δ) avec δ(p, x) = s(px).

JP Becirspahic — Automates — 2015-2016 — Page 11/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Algorithme KMP

On note P (u) l’ensemble des préfixes du mot u.

On note s(v) le plus long suffixe de v dans P (u).
On pose A = (Σ, P (u), {ε}, {u}, δ) avec δ(p, x) = s(px).
Exemple : u = aba.
δ a b
ε a ε
a a ab
ab aba ε
aba a ab

a
b a
a
a b
ε a ab aba

b
b

JP Becirspahic — Automates — 2015-2016 — Page 11/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Algorithme KMP

L’automate A reconnait le langage Σ∗ u.

JP Becirspahic — Automates — 2015-2016 — Page 11/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Algorithme KMP

L’automate A reconnait le langage Σ∗ u.

Si p ∈ P (u) et v ∈ Σ∗ on prouve par récurrence sur |v| que le chemin qui part de
l’état p et qui est étiqueté par v mène à l’état s(pv).

JP Becirspahic — Automates — 2015-2016 — Page 11/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Algorithme KMP

L’automate A reconnait le langage Σ∗ u.

Si p ∈ P (u) et v ∈ Σ∗ on prouve par récurrence sur |v| que le chemin qui part de
l’état p et qui est étiqueté par v mène à l’état s(pv).
• Si v = ε on a s(p) = p puisque p ∈ P (u).

JP Becirspahic — Automates — 2015-2016 — Page 11/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Algorithme KMP

L’automate A reconnait le langage Σ∗ u.

Si p ∈ P (u) et v ∈ Σ∗ on prouve par récurrence sur |v| que le chemin qui part de
l’état p et qui est étiqueté par v mène à l’état s(pv).
• Si v = ε on a s(p) = p puisque p ∈ P (u).
• Si v , ε, on pose v = v 0 a et on suppose que le chemin qui part de p étiqueté
par v 0 mène à l’état s(pv 0 ). Celui étiqueté par v mène à l’état s(s(pv 0 )a).

JP Becirspahic — Automates — 2015-2016 — Page 11/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Algorithme KMP

L’automate A reconnait le langage Σ∗ u.

Si p ∈ P (u) et v ∈ Σ∗ on prouve par récurrence sur |v| que le chemin qui part de
l’état p et qui est étiqueté par v mène à l’état s(pv).
• Si v = ε on a s(p) = p puisque p ∈ P (u).
• Si v , ε, on pose v = v 0 a et on suppose que le chemin qui part de p étiqueté
par v 0 mène à l’état s(pv 0 ). Celui étiqueté par v mène à l’état s(s(pv 0 )a).
Soit w = s(s(pv 0 )a) et w 0 = s(pv 0 ). w est suffixe de w 0 a et w 0 suffixe de pv 0 donc
w est suffixe de pv 0 a = pv. De plus w ∈ P (u) donc w est suffixe de s(pv).

JP Becirspahic — Automates — 2015-2016 — Page 11/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Algorithme KMP

L’automate A reconnait le langage Σ∗ u.

Si p ∈ P (u) et v ∈ Σ∗ on prouve par récurrence sur |v| que le chemin qui part de
l’état p et qui est étiqueté par v mène à l’état s(pv).
• Si v = ε on a s(p) = p puisque p ∈ P (u).
• Si v , ε, on pose v = v 0 a et on suppose que le chemin qui part de p étiqueté
par v 0 mène à l’état s(pv 0 ). Celui étiqueté par v mène à l’état s(s(pv 0 )a).
Soit w = s(s(pv 0 )a) et w 0 = s(pv 0 ). w est suffixe de w 0 a et w 0 suffixe de pv 0 donc
w est suffixe de pv 0 a = pv. De plus w ∈ P (u) donc w est suffixe de s(pv).
Si s(pv) = ε alors w = ε. Si s(pv) , ε on pose s(pv) = xa. Alors x ∈ P (u) et x
est suffixe de pv 0 donc x est suffixe de s(pv 0 ) = w 0 et xa suffixe de w 0 a. Puisque
xa ∈ P (u) alors xa est suffixe de s(w 0 a) = w.
Dans les deux cas s(pv) est suffixe de w donc w = s(pv).

JP Becirspahic — Automates — 2015-2016 — Page 11/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Algorithme KMP

L’automate A reconnait le langage Σ∗ u.

Si p ∈ P (u) et v ∈ Σ∗ on prouve par récurrence sur |v| que le chemin qui part de
l’état p et qui est étiqueté par v mène à l’état s(pv).
• Si v = ε on a s(p) = p puisque p ∈ P (u).
• Si v , ε, on pose v = v 0 a et on suppose que le chemin qui part de p étiqueté
par v 0 mène à l’état s(pv 0 ). Celui étiqueté par v mène à l’état s(s(pv 0 )a).
Soit w = s(s(pv 0 )a) et w 0 = s(pv 0 ). w est suffixe de w 0 a et w 0 suffixe de pv 0 donc
w est suffixe de pv 0 a = pv. De plus w ∈ P (u) donc w est suffixe de s(pv).
Si s(pv) = ε alors w = ε. Si s(pv) , ε on pose s(pv) = xa. Alors x ∈ P (u) et x
est suffixe de pv 0 donc x est suffixe de s(pv 0 ) = w 0 et xa suffixe de w 0 a. Puisque
xa ∈ P (u) alors xa est suffixe de s(w 0 a) = w.
Dans les deux cas s(pv) est suffixe de w donc w = s(pv).
Ainsi le chemin qui part de l’état ε et étiqueté par un mot v mène à l’état s(v), et

s(v) = u ⇐⇒ v ∈ Σ∗ u.

JP Becirspahic — Automates — 2015-2016 — Page 11/18

lycée louis-le-grand option informatique

Recherche d’un mot dans un texte

Algorithme KMP

L’automate A reconnait le langage Σ∗ u.

Pour obtenir un automate qui reconnait le langage Σ∗ uΣ∗ il suffit de consi-
dérer l’automate A et de transformer l’état u en puit.

b a a, b

a b a
ε a ab aba

b
Un automate qui reconnait Σ∗ abaΣ∗ .

JP Becirspahic — Automates — 2015-2016 — Page 11/18

lycée louis-le-grand option informatique

Automates finis et langages rationnels

Théorème de Kleene

Un langage L sur un alphabet Σ est rationnel si et seulement s’il existe

un automate fini A tel que L (A ) = L .

JP Becirspahic — Automates — 2015-2016 — Page 12/18

lycée louis-le-grand option informatique

Automates finis et langages rationnels

Théorème de Kleene

Un langage L sur un alphabet Σ est rationnel si et seulement s’il existe

un automate fini A tel que L (A ) = L .

Deux étapes de la preuve :

• l’algorithme de Berry-Sethi construit explicitement l’automate de
Glushkov associé à une expression rationnelle ;

JP Becirspahic — Automates — 2015-2016 — Page 12/18

lycée louis-le-grand option informatique

Automates finis et langages rationnels

Théorème de Kleene

Un langage L sur un alphabet Σ est rationnel si et seulement s’il existe

un automate fini A tel que L (A ) = L .

Deux étapes de la preuve :

• l’algorithme de Berry-Sethi construit explicitement l’automate de
Glushkov associé à une expression rationnelle ;
• l’algorithme de Brzozowski et McCluskey fournit une expression
rationnelle qui dénote le langage reconnu par un automate.
(Ce deuxième point n’est pas explicitement au programme.)

JP Becirspahic — Automates — 2015-2016 — Page 12/18

lycée louis-le-grand option informatique

Algorithme de Berry-Sethi
Un automate déterministe A = (Σ, Q , q0 , F , δ) est local lorsque pour chaque
lettre x toutes les transitions étiquetées par x arrivent dans un même
état. Il est standard lorsqu’il n’existe pas de transition aboutissant à l’état
initial.

JP Becirspahic — Automates — 2015-2016 — Page 13/18

lycée louis-le-grand option informatique

Algorithme de Berry-Sethi
Un automate déterministe A = (Σ, Q , q0 , F , δ) est local lorsque pour chaque
lettre x toutes les transitions étiquetées par x arrivent dans un même
état. Il est standard lorsqu’il n’existe pas de transition aboutissant à l’état
initial.
Si L est un langage local, le langage L \ {ε} est reconnaissable par un
automate local standard.

JP Becirspahic — Automates — 2015-2016 — Page 13/18

lycée louis-le-grand option informatique

Algorithme de Berry-Sethi
Un automate déterministe A = (Σ, Q , q0 , F , δ) est local lorsque pour chaque
lettre x toutes les transitions étiquetées par x arrivent dans un même
état. Il est standard lorsqu’il n’existe pas de transition aboutissant à l’état
initial.
Si L est un langage local, le langage L \ {ε} est reconnaissable par un
automate local standard.
Considérons l’automate A = (Σ, Σ ∪ {ε}, ε, S , δ) avec :

∀x ∈ P , δ(ε, x) = x et ∀xy ∈ F , δ(x, y) = y.

u = a1 a2 · · · an est reconnu par A ssi a1 ∈ P , ai ai +1 ∈ F et an ∈ S .

JP Becirspahic — Automates — 2015-2016 — Page 13/18

lycée louis-le-grand option informatique

Algorithme de Berry-Sethi
Un automate déterministe A = (Σ, Q , q0 , F , δ) est local lorsque pour chaque
lettre x toutes les transitions étiquetées par x arrivent dans un même
état. Il est standard lorsqu’il n’existe pas de transition aboutissant à l’état
initial.
Si L est un langage local, le langage L \ {ε} est reconnaissable par un
automate local standard.
Exemple : L = (a +b )∗ c, P = {a, b , c}, S = {c} et F = {aa, ab , ba, bb , ac, bc}.
b
a b
b
a c
ε a b c

c
JP Becirspahic — Automates — 2015-2016 — Page 13/18
lycée louis-le-grand option informatique

Algorithme de Berry-Sethi
Construction de l’automate de Glushkov
On considère une expression rationnelle sans ∅ ni ε : e = (ab + b )∗ ba.

JP Becirspahic — Automates — 2015-2016 — Page 14/18

lycée louis-le-grand option informatique

Algorithme de Berry-Sethi
Construction de l’automate de Glushkov
On considère une expression rationnelle sans ∅ ni ε : e = (ab + b )∗ ba.
0 ∗
1 on linéarise e par marquage : e = (c1 c2 + c3 ) c4 c5 ;

JP Becirspahic — Automates — 2015-2016 — Page 14/18

lycée louis-le-grand option informatique

Algorithme de Berry-Sethi
Construction de l’automate de Glushkov
On considère une expression rationnelle sans ∅ ni ε : e = (ab + b )∗ ba.
0
1 on linéarise e par marquage : e = (c1 c2 + c3 ) c4 c5 ;
∗

2 P = {c1 , c3 , c4 }, S = {c5 }, F = {c1 c2 , c2 c1 , c2 c3 , c2 c4 , c3 c1 , c3 c3 , c3 c4 , c4 c5 } ;

JP Becirspahic — Automates — 2015-2016 — Page 14/18

lycée louis-le-grand option informatique

Algorithme de Berry-Sethi
Construction de l’automate de Glushkov
On considère une expression rationnelle sans ∅ ni ε : e = (ab + b )∗ ba.
0
1 on linéarise e par marquage : e = (c1 c2 + c3 ) c4 c5 ;
∗

2 P = {c1 , c3 , c4 }, S = {c5 }, F = {c1 c2 , c2 c1 , c2 c3 , c2 c4 , c3 c1 , c3 c3 , c3 c4 , c4 c5 } ;

3 on construit l’automate local associé ;

c2
c1 c2
c1
c1
c1
c3
c3
c0 c3 c3
c4
c4
c4

c4 c5
c5
JP Becirspahic — Automates — 2015-2016 — Page 14/18
lycée louis-le-grand option informatique

Algorithme de Berry-Sethi
Construction de l’automate de Glushkov
On considère une expression rationnelle sans ∅ ni ε : e = (ab + b )∗ ba.
0
1 on linéarise e par marquage : e = (c1 c2 + c3 ) c4 c5 ;
∗

2 P = {c1 , c3 , c4 }, S = {c5 }, F = {c1 c2 , c2 c1 , c2 c3 , c2 c4 , c3 c1 , c3 c3 , c3 c4 , c4 c5 } ;

3 on construit l’automate local associé ;
4 on supprime le marquage ;

b
c1 c2
a
a
a
b
c0 b c3 b
b
b
b

c4 c5
a
JP Becirspahic — Automates — 2015-2016 — Page 14/18
lycée louis-le-grand option informatique

Algorithme de Berry-Sethi
Construction de l’automate de Glushkov
On considère une expression rationnelle sans ∅ ni ε : e = (ab + b )∗ ba.
0
1 on linéarise e par marquage : e = (c1 c2 + c3 ) c4 c5 ;
∗

2 P = {c1 , c3 , c4 }, S = {c5 }, F = {c1 c2 , c2 c1 , c2 c3 , c2 c4 , c3 c1 , c3 c3 , c3 c4 , c4 c5 } ;

3 on construit l’automate local associé ;
4 on supprime le marquage ;
5 on déterminise l’automate.
b
q1 q3
a
δ0 a b a
a
∗ {c0 } {c1 } {c3 , c4 }
{c1 } − {c2 }
{c3 , c4 } {c1 , c5 } {c3 } q0 q5 b
{c2 } {c1 } {c3 , c4 }
b
∗ {c1 , c5 } − {c2 }
{c3 } {c1 } {c3 , c4 } b b
b

q2 q4
a
JP Becirspahic — Automates — 2015-2016 — Page 14/18
lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Un automate généralisé est un automate A = (Rat(Σ), Q , I , F , δ) dont les
états et les transitions sont en nombres finis et dont les transitions sont
étiquetées par des expressions rationnelles.

JP Becirspahic — Automates — 2015-2016 — Page 15/18

lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Un automate généralisé est un automate A = (Rat(Σ), Q , I , F , δ) dont les
états et les transitions sont en nombres finis et dont les transitions sont
étiquetées par des expressions rationnelles.
e1 e2 en
Un mot u est reconnu s’il existe un chemin q0 −→ q1 −→ · · · −→ qn menant
d’un état initial à un état acceptant tel que u appartienne au langage
dénoté par e1 e2 · · · en .

JP Becirspahic — Automates — 2015-2016 — Page 15/18

lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Un automate généralisé est un automate A = (Rat(Σ), Q , I , F , δ) dont les
états et les transitions sont en nombres finis et dont les transitions sont
étiquetées par des expressions rationnelles.
e1 e2 en
Un mot u est reconnu s’il existe un chemin q0 −→ q1 −→ · · · −→ qn menant
d’un état initial à un état acceptant tel que u appartienne au langage
dénoté par e1 e2 · · · en .
• Quitte à ajouter un état initial i et un état final f on peut supposer
qu’un automate généralisé ne possède qu’un seul état initial et un
seul état acceptant ;

JP Becirspahic — Automates — 2015-2016 — Page 15/18

lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Un automate généralisé est un automate A = (Rat(Σ), Q , I , F , δ) dont les
états et les transitions sont en nombres finis et dont les transitions sont
étiquetées par des expressions rationnelles.
e1 e2 en
Un mot u est reconnu s’il existe un chemin q0 −→ q1 −→ · · · −→ qn menant
d’un état initial à un état acceptant tel que u appartienne au langage
dénoté par e1 e2 · · · en .
• Quitte à ajouter un état initial i et un état final f on peut supposer
qu’un automate généralisé ne possède qu’un seul état initial et un
seul état acceptant ;
• on peut aussi supposer qu’entre deux états il n’existe qu’au plus une
transition.
e1
e1 + e2
qi qj ⇐⇒ qi qj

e2

JP Becirspahic — Automates — 2015-2016 — Page 15/18

lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Tout langage reconnu par un automate généralisé est rationnel.

JP Becirspahic — Automates — 2015-2016 — Page 15/18

lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Tout langage reconnu par un automate généralisé est rationnel.
On raisonne par récurrence sur le nombre d’états |Q |.

JP Becirspahic — Automates — 2015-2016 — Page 15/18

lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Tout langage reconnu par un automate généralisé est rationnel.
On raisonne par récurrence sur le nombre d’états |Q |.
• Si |Q | = 2 l’automate A est de la forme :
e
i f

et le langage reconnu par A est dénoté par e.

JP Becirspahic — Automates — 2015-2016 — Page 15/18

lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Tout langage reconnu par un automate généralisé est rationnel.
On raisonne par récurrence sur le nombre d’états |Q |.
• Si |Q | = 2 l’automate A est de la forme :
e
i f

et le langage reconnu par A est dénoté par e.

• Si |Q | > 2, on élimine un état q ∈ Q \ {i , f } en effectuant la transformation
suivante pour chaque couple d’états (qi , qj ) tel que qi , q et qj , q :
e4

e1 e2

e3 + e1 e4∗ e2
qi qj ⇐⇒ qi qj
e3

JP Becirspahic — Automates — 2015-2016 — Page 15/18

lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Exemple a

On considère l’automate suivant : q1

a b

q0 b q3
a
a
b
q2

JP Becirspahic — Automates — 2015-2016 — Page 16/18

lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Exemple a

On considère l’automate suivant : q1

a b

q0 b q3
a

On ajoute un état initial et un état final : a

b
a q2

q1

a b

ε q0 b q3 ε
i f
a
a
b
q2

JP Becirspahic — Automates — 2015-2016 — Page 16/18

lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Exemple a

On considère l’automate suivant : q1

a b

q0 b q3
a

On élimine l’état q2 : a
b
q2
a

q1

a b

ε b + a2 ε
i q0 q3 f

ba

JP Becirspahic — Automates — 2015-2016 — Page 16/18

lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Exemple a

On considère l’automate suivant : q1

a b

q0 b q3
a

On élimine l’état q1 : a
b
q2

ε b + a 2 + aa ∗ b ε
i q0 q3 f

ba

JP Becirspahic — Automates — 2015-2016 — Page 16/18

lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Exemple a

On considère l’automate suivant : q1

a b

q0 b q3
a

On élimine l’état q0 : a
b
q2

b + a 2 + aa ∗ b ε
i q3 f

ba

JP Becirspahic — Automates — 2015-2016 — Page 16/18

lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Exemple a

On considère l’automate suivant : q1

a b

q0 b q3
a

On élimine l’état q3 : a
b
q2

(b + a 2 + aa ∗ b )(ba )∗
i f

JP Becirspahic — Automates — 2015-2016 — Page 16/18

lycée louis-le-grand option informatique

Algorithme de Brzozowski et McCluskey

Exemple a

On considère l’automate suivant : q1

a b

q0 b q3
a

On élimine l’état q3 : a
b
q2

(b + a 2 + aa ∗ b )(ba )∗
i f

L’automate reconnait le langage dénoté par (b + a 2 + aa ∗ b )(ba)∗ .

JP Becirspahic — Automates — 2015-2016 — Page 16/18

lycée louis-le-grand option informatique

Propriétés des langages reconnaissables

Les langages reconnaissables sont clos par complémentation.

JP Becirspahic — Automates — 2015-2016 — Page 17/18

lycée louis-le-grand option informatique

Propriétés des langages reconnaissables

Les langages reconnaissables sont clos par complémentation.
Soit L un langage reconnu par un automate déterministe complet A = (Σ, Q , q0 , F , δ)
et L = Σ∗ \ L . Posons A 0 = (Σ, Q , q0 , Q \ F , δ) ; alors l’automate A 0 reconnait L .

JP Becirspahic — Automates — 2015-2016 — Page 17/18

lycée louis-le-grand option informatique

Propriétés des langages reconnaissables

Les langages reconnaissables sont clos par complémentation.
Soit L un langage reconnu par un automate déterministe complet A = (Σ, Q , q0 , F , δ)
et L = Σ∗ \ L . Posons A 0 = (Σ, Q , q0 , Q \ F , δ) ; alors l’automate A 0 reconnait L .

Les langages reconnaissables sont clos par intersection.

JP Becirspahic — Automates — 2015-2016 — Page 17/18

lycée louis-le-grand option informatique

Propriétés des langages reconnaissables

Les langages reconnaissables sont clos par complémentation.
Soit L un langage reconnu par un automate déterministe complet A = (Σ, Q , q0 , F , δ)
et L = Σ∗ \ L . Posons A 0 = (Σ, Q , q0 , Q \ F , δ) ; alors l’automate A 0 reconnait L .

Les langages reconnaissables sont clos par intersection.

Soient L1 et L2 deux langages reconnus par les automates déterministes com-
plets A1 = (Σ, Q1 , q1,0 , F1 , δ1 ) et A2 = (Σ, Q2 , q2,0 , F2 , δ2 ). On pose Q = Q1 × Q2 ,
q0 = (q1,0 , q2,0 ), F = F1 × F2 et δ((q1 , q2 ), a) = (δ1 (q1 , a), δ(q2 , a)). Alors A =
(Σ, Q , q0 , F , δ) reconnait le langage L1 ∩ L2 .

JP Becirspahic — Automates — 2015-2016 — Page 17/18

lycée louis-le-grand option informatique

Propriétés des langages reconnaissables

Les langages reconnaissables sont clos par complémentation.
Soit L un langage reconnu par un automate déterministe complet A = (Σ, Q , q0 , F , δ)
et L = Σ∗ \ L . Posons A 0 = (Σ, Q , q0 , Q \ F , δ) ; alors l’automate A 0 reconnait L .

Les langages reconnaissables sont clos par intersection.

Soient L1 et L2 deux langages reconnus par les automates déterministes com-
plets A1 = (Σ, Q1 , q1,0 , F1 , δ1 ) et A2 = (Σ, Q2 , q2,0 , F2 , δ2 ). On pose Q = Q1 × Q2 ,
q0 = (q1,0 , q2,0 ), F = F1 × F2 et δ((q1 , q2 ), a) = (δ1 (q1 , a), δ(q2 , a)). Alors A =
(Σ, Q , q0 , F , δ) reconnait le langage L1 ∩ L2 .
En effet, soit u ∈ Σ∗ et (q1 , q2 ) l’état auquel aboutit le chemin étiqueté par u.
• Si u < L1 alors q1 < F1 donc (q1 , q2 ) < S ;
• si u < L2 alors q2 < F2 donc (q1 , q2 ) < S ;
• si u ∈ L1 ∩ L2 alors q1 ∈ F1 et q2 ∈ F2 donc (q1 , q2 ) ∈ F .

JP Becirspahic — Automates — 2015-2016 — Page 17/18

lycée louis-le-grand option informatique

Propriétés des langages reconnaissables

Les langages reconnaissables sont clos par complémentation.
Soit L un langage reconnu par un automate déterministe complet A = (Σ, Q , q0 , F , δ)
et L = Σ∗ \ L . Posons A 0 = (Σ, Q , q0 , Q \ F , δ) ; alors l’automate A 0 reconnait L .

Les langages reconnaissables sont clos par intersection.

Soient L1 et L2 deux langages reconnus par les automates déterministes com-
plets A1 = (Σ, Q1 , q1,0 , F1 , δ1 ) et A2 = (Σ, Q2 , q2,0 , F2 , δ2 ). On pose Q = Q1 × Q2 ,
q0 = (q1,0 , q2,0 ), F = F1 × F2 et δ((q1 , q2 ), a) = (δ1 (q1 , a), δ(q2 , a)). Alors A =
(Σ, Q , q0 , F , δ) reconnait le langage L1 ∩ L2 .

Conséquence : Les langages rationnels sont clos par complémentation et

par intersection.

JP Becirspahic — Automates — 2015-2016 — Page 17/18

lycée louis-le-grand option informatique

Propriétés des langages reconnaissables

Les langages reconnaissables sont clos par complémentation.
Soit L un langage reconnu par un automate déterministe complet A = (Σ, Q , q0 , F , δ)
et L = Σ∗ \ L . Posons A 0 = (Σ, Q , q0 , Q \ F , δ) ; alors l’automate A 0 reconnait L .

Les langages reconnaissables sont clos par intersection.

Soient L1 et L2 deux langages reconnus par les automates déterministes com-
plets A1 = (Σ, Q1 , q1,0 , F1 , δ1 ) et A2 = (Σ, Q2 , q2,0 , F2 , δ2 ). On pose Q = Q1 × Q2 ,
q0 = (q1,0 , q2,0 ), F = F1 × F2 et δ((q1 , q2 ), a) = (δ1 (q1 , a), δ(q2 , a)). Alors A =
(Σ, Q , q0 , F , δ) reconnait le langage L1 ∩ L2 .

Les langages reconnaissables sont clos par passage au miroir.

JP Becirspahic — Automates — 2015-2016 — Page 17/18

lycée louis-le-grand option informatique

Propriétés des langages reconnaissables

Les langages reconnaissables sont clos par complémentation.
Soit L un langage reconnu par un automate déterministe complet A = (Σ, Q , q0 , F , δ)
et L = Σ∗ \ L . Posons A 0 = (Σ, Q , q0 , Q \ F , δ) ; alors l’automate A 0 reconnait L .

Les langages reconnaissables sont clos par intersection.

Soient L1 et L2 deux langages reconnus par les automates déterministes com-
plets A1 = (Σ, Q1 , q1,0 , F1 , δ1 ) et A2 = (Σ, Q2 , q2,0 , F2 , δ2 ). On pose Q = Q1 × Q2 ,
q0 = (q1,0 , q2,0 ), F = F1 × F2 et δ((q1 , q2 ), a) = (δ1 (q1 , a), δ(q2 , a)). Alors A =
(Σ, Q , q0 , F , δ) reconnait le langage L1 ∩ L2 .

Les langages reconnaissables sont clos par passage au miroir.

Considérons un automate non déterministe A = (Σ, Q , I , F , δ) et définissons l’au-
tomate A 0 = (Σ, Q , F , I , δ0 ) avec :

δ0 (q, x) = q 0 ⇐⇒ δ(x, q 0 ) = q

Alors le langage reconnu par A 0 est l’image miroir du langage reconnu par A .

JP Becirspahic — Automates — 2015-2016 — Page 17/18

lycée louis-le-grand option informatique

Lemme de l’étoile
Si L est un langage rationnel il existe un entier k tel que tout mot m ∈ L
de longueur supérieure ou égale à k se factorise sous la forme m = uvw
avec : (i ) |v| > 1 (ii ) |uv| 6 k (iii ) ∀n ∈ N, uv n w ∈ L .

JP Becirspahic — Automates — 2015-2016 — Page 18/18

lycée louis-le-grand option informatique

Lemme de l’étoile
Si L est un langage rationnel il existe un entier k tel que tout mot m ∈ L
de longueur supérieure ou égale à k se factorise sous la forme m = uvw
avec : (i ) |v| > 1 (ii ) |uv| 6 k (iii ) ∀n ∈ N, uv n w ∈ L .
Soit A = (Σ, Q , q0 , F , δ) et k = |Q |. Soit m un mot de L tel que |m| > k . Le chemin
a1 a2 ap
q0 −→ q1 −→ q2 · · · −→ qp reconnaissant m implique p + 1 états donc passe
nécessairement deux fois par le même état qi = qj avec 0 6 i < j 6 k :
a1 ai aj ap
q0 −→ · · · −→ qi · · · · · · −→ qj −→ · · · −→ qp
Posons u = a1 · · · ai , v = ai +1 · · · aj et w = aj +1 · · · ap . Alors pour tout n ∈ N le
chemin étiqueté par uv n w conduit à l’état acceptant qp donc uv n w ∈ L .

JP Becirspahic — Automates — 2015-2016 — Page 18/18

lycée louis-le-grand option informatique

Lemme de l’étoile
Si L est un langage rationnel il existe un entier k tel que tout mot m ∈ L
de longueur supérieure ou égale à k se factorise sous la forme m = uvw
avec : (i ) |v| > 1 (ii ) |uv| 6 k (iii ) ∀n ∈ N, uv n w ∈ L .
Soit A = (Σ, Q , q0 , F , δ) et k = |Q |. Soit m un mot de L tel que |m| > k . Le chemin
a1 a2 ap
q0 −→ q1 −→ q2 · · · −→ qp reconnaissant m implique p + 1 états donc passe
nécessairement deux fois par le même état qi = qj avec 0 6 i < j 6 k :
a1 ai aj ap
q0 −→ · · · −→ qi · · · · · · −→ qj −→ · · · −→ qp
Posons u = a1 · · · ai , v = ai +1 · · · aj et w = aj +1 · · · ap . Alors pour tout n ∈ N le
chemin étiqueté par uv n w conduit à l’état acceptant qp donc uv n w ∈ L .

Si L est un langage rationnel il existe un entier k tel que tout mot

m = uvw tel que |v| > k se factorise sous la forme m = u(v1 v2 v3 )w avec :

(i ) |v2 | > 1 (ii ) |v1 v2 | 6 k (iii ) ∀n ∈ N, u(v1 v2n v3 )w ∈ L .

JP Becirspahic — Automates — 2015-2016 — Page 18/18

lycée louis-le-grand option informatique

Lemme de l’étoile
Si L est un langage rationnel il existe un entier k tel que tout mot m ∈ L
de longueur supérieure ou égale à k se factorise sous la forme m = uvw
avec : (i ) |v| > 1 (ii ) |uv| 6 k (iii ) ∀n ∈ N, uv n w ∈ L .
Soit A = (Σ, Q , q0 , F , δ) et k = |Q |. Soit m un mot de L tel que |m| > k . Le chemin
a1 a2 ap
q0 −→ q1 −→ q2 · · · −→ qp reconnaissant m implique p + 1 états donc passe
nécessairement deux fois par le même état qi = qj avec 0 6 i < j 6 k :
a1 ai aj ap
q0 −→ · · · −→ qi · · · · · · −→ qj −→ · · · −→ qp
Posons u = a1 · · · ai , v = ai +1 · · · aj et w = aj +1 · · · ap . Alors pour tout n ∈ N le
chemin étiqueté par uv n w conduit à l’état acceptant qp donc uv n w ∈ L .

Si L est un langage rationnel il existe un entier k tel que tout mot

m = uvw tel que |v| > k se factorise sous la forme m = u(v1 v2 v3 )w avec :

(i ) |v2 | > 1 (ii ) |v1 v2 | 6 k (iii ) ∀n ∈ N, u(v1 v2n v3 )w ∈ L .

On applique la méthode décrite dans la preuve précédente uniquement après
avoir parcouru le chemin étiqueté par u.
JP Becirspahic — Automates — 2015-2016 — Page 18/18
lycée louis-le-grand option informatique

Lemme de l’étoile
Exemple
n o
• Le langage L = a n b n n ∈ N n’est pas rationnel.

JP Becirspahic — Automates — 2015-2016 — Page 18/18

lycée louis-le-grand option informatique

Lemme de l’étoile
Exemple
n o
• Le langage L = a n b n n ∈ N n’est pas rationnel.

Supposons les conclusions du lemme de l’étoile vérifiées et posons

u = ak , v = bk, w = ε.

D’après le lemme de l’étoile v se factorise en v = b k1 b k2 b k3 avec k2 > 1 et

on doit avoir : ∀n ∈ N, a k b k +nk2 ∈ L , ce qui est absurde.

JP Becirspahic — Automates — 2015-2016 — Page 18/18

lycée louis-le-grand option informatique

Lemme de l’étoile
Exemple
n o
• Le langage L = a n b n n ∈ N n’est pas rationnel.

Supposons les conclusions du lemme de l’étoile vérifiées et posons

u = ak , v = bk, w = ε.

D’après le lemme de l’étoile v se factorise en v = b k1 b k2 b k3 avec k2 > 1 et

on doit avoir : ∀n ∈ N, a k b k +nk2 ∈ L , ce qui est absurde.
n o
• Si Σ possède au moins deux lettres le langage L = m 2 m ∈ Σ∗ des
carrés parfaits n’est pas rationnel.

JP Becirspahic — Automates — 2015-2016 — Page 18/18

lycée louis-le-grand option informatique

Lemme de l’étoile
Exemple
n o
• Le langage L = a n b n n ∈ N n’est pas rationnel.

Supposons les conclusions du lemme de l’étoile vérifiées et posons

u = ak , v = bk, w = ε.

D’après le lemme de l’étoile v se factorise en v = b k1 b k2 b k3 avec k2 > 1 et

on doit avoir : ∀n ∈ N, a k b k +nk2 ∈ L , ce qui est absurde.
n o
• Si Σ possède au moins deux lettres le langage L = m 2 m ∈ Σ∗ des
carrés parfaits n’est pas rationnel.
Supposons les conclusions du lemme de l’étoile vérifiées et posons m =
ab k . Le mot m 2 se factorise en m 2 = uvw avec

u = a, v = bk, w = ab k .

Alors il existe j > 1 tel que pour tout n ∈ N, ab k +nj ab k ∈ L , ce qui est
absurde.
JP Becirspahic — Automates — 2015-2016 — Page 18/18