les langages réguliers, propriétés et

théorèmes
Équivalence entre automates, grammaires et expression
régulières
Plan

Le théorème de Kleene

Propriétés des langages réguliers

Théorème de Nerode

Lemme de l’étoile
 Le théorème de Kleene (Description)
Le théorème de Kleene établit l’équivalence entre les
expressions rationnelles (régulières) et les automates finis
dans le sens où ces deux notions définissent les même
langages. Ce résultat est remarquable car il relie deux
notions de natures différentes, combinatoire pour les
expressions rationnelles et opérationnelle pour les
automates.

3 W.SAADI
 Le théorème de Kleene (définition)
Soient Λreg l’ensemble des langages réguliers (générés par des
grammaires régulières), Λrat l’ensemble des langages décrits
par toutes les expressions régulières et ΛAEF l’ensemble de
tous les langages reconnus par un AEF. Nous avons, alors,
l’égalité suivante : Λreg = Λrat =ΛAEF
Le théorème annonce que l’on peut passer d’une
représentation à une autre en se basant sur l’équivalence
entre les trois représentations.
4 W.SAADI
 Passage de l’automate vers l’expression
régulière
Soit A = (V, Q, q0, F) un automate à états fini quelconque. On
note par Li le langage reconnu par l’automate si son état
initial était qi. Par conséquent, trouver le langage reconnu
par l’automate revient à trouver L0 étant donné que la
reconnaissance commence à partir de l’état initial q0.

5 W.SAADI
 Algorithme de Passage de AEF a ER
L’automate permet d’établir un système d’équations aux langages de
la manière suivante :
1. si (qi, a) = qj alors on écrit : Li = aLj ;

2. si qi ∈ F, alors on écrit : Li = ε

3. si Li = α et Li = β alors on écrit : Li = α | β;

Il suffit ensuite de résoudre le système en précédant à des

substitutions et en utilisant la règle suivante : la solution de
l’équation L = α L| β (ε∉α ) est le langage L = α∗ β

Attention:Si on obtient L=L alors il existe une faute de raisonnement.

6 W.SAADI
Exemple 1
Soit l’automate A suivant :

En appliquant l’algorithme précédant, on obtient l’expression

régulière L0 qui définit le langage reconnu par A.

L0 = (a∗b+a+b)∗a∗b+a+

7 W.SAADI
 Passage de l’expression régulière vers
l’automate
Il existe deux méthodes permettant de réaliser cette tâche :

La première fait appel à la notion de dérivée;

La deuxième construit un automate comportant des

ε-transitions en se basant sur les propriétés des langages

réguliers.

8 W.SAADI
Méthode basé sur les dérivés du langage
Dérivée d’un langage :

Soit w un mot défini sur un alphabet Σ. On appelle le mot

∈ ∗ dérivée de w par rapport à u ∈ Σ∗ tel que w = uv.
v∈Σ
On note cette opération par : v = w||u.

On peut étendre cette notion aux langages. Ainsi la dérivée

d’un langage par rapport à un mot u ∈ Σ∗ est le langage :

L||u = {v ∈ Σ∗ |∃w ∈ L : w = uv}.

9 W.SAADI
Exemple 2

L = {1, 01, 11},

L||1 = {ε, 1},

L||0 = {1},

L||00 = ∅
Propriétés des dérivées

ai||aj = ε si ai = aj ∅ sinon;

∪Li ||a= ∪(Li ||a);

(L1.L2 )||a= (L1 )||a.L2 si ε ∉ L1 sinon (L1||a).L2 ∪ L2||a

L*||a = (L||a) L*;

L||w1.w2 = (L||w1)||w2 ;

11
W.SAADI
 Construction de l’automate par la méthode
des dérivées(1)

Soit r une expression régulière (utilisant l’alphabet Σ) pour

laquelle on veut construire un AEF.

L’algorithme suivant donne la construction de l’automate :

1) Dériver r par rapport à chaque symbole de Σ ;

2) Recommencer 1) pour chaque nouveau langage obtenu

jusqu’à ce qu’il n’y ait plus de nouveaux langages ;

12 W.SAADI
 Construction de l’automate par la méthode
des dérivées(2)

3) Chaque langage obtenu correspond à un état de

l’automate. L’état initial correspond à r. Si ε
appartient à un langage obtenu alors l’état
correspondant est final ;

4) si Li||a = Lj alors on crée une transition entre l’état

associé à Li et l’état associé à Lj et on la décore par a.

13 W.SAADI
Exemple 3
Considérons le langage (a|b)∗a(a|b)∗. On sait que :
(a|b)||a = ε donc (a|b)∗||a = (a|b)∗
Commençons l’application de l’algorithme :
[(a|b)∗a(a|b)∗]||a = ((a|b)∗a(a|b)∗)|(a|b)∗ ;
[(a|b)∗a(a|b)∗]||b = (a|b)∗a(a|b)∗ ;
[((a|b)∗a(a|b)∗)|(a|b)∗]||a = ((a|b)∗a(a|b)∗)|(a|b)∗ ;
[((a|b)∗a(a|b)∗)|(a|b)∗]||b = ((a|b)∗a(a|b)∗)|(a|b)∗ ;
Il n’y a plus de nouveaux langages, on s’arrête alors.

14 W.SAADI
Suite…
L’automate comporte deux états q0 (associé à (a|b)∗a(a|b)∗)
et q1 (associé à ((a|b)∗a(a|b)∗)|(a|b)∗), il est donné par la
table suivante (l’état initial est q0 et l’état q1 est final) :

15 W.SAADI
Conséquences
La méthode des dérivée ne permet pas seulement de
construire l’AEF d’un langage, elle permet même de
vérifier si un langage est régulier ou non.

Un langage est régulier si et seulement si le nombre de

langages trouvés par la méthode des dérivées est fini. En
d’autres termes, l’application de la méthode des dérivées
à un langage non régulier produit un nombre infini des
langages (ou encore d’états).
16 W.SAADI
Méthode de Thompson (1)
La méthode de Thompson permet de construire un
automate en procédant à la décomposition de
l’expression régulière selon les opérations utilisées. Soit r,
s et t des E.R, alors l’algorithme à utiliser est le suivant :

Si r = a (un seul symbole) alors l’automate est le suivant :

Méthode de Thompson (2)
Si r = s.t alors il suffit de trouver l’automate As qui
reconnaît s et l’automate At qui reconnaît t. Il faudra,
ensuite relier chaque état final de As à l’état initial de At
par une ε-transition. Les états finaux de As ne le sont plus
et l’état initial de At ne l’est plus.

18 W.SAADI
Méthode de Thompson (3)
Si r = s|t alors il suffit de créer
un nouvel état initial et le relier
avec des ε-transitions aux états
initiaux de Ar et As qui ne le sont plus.

Si r = s+ alors il suffit de relier

les états finaux de As par
des ε-transitions à son
état initial.

19 W.SAADI
Méthode de Thompson (4)
Si r = s∗ alors il suffit de relier les états finaux de As par
des ε-transitions à son état initial puis relier ce dernier à
chacun des états finaux par des ε -transitions.

20 W.SAADI
Exemple 4
Soit à construire l’automate du langage L(R) tel que
R=(a|b)∗a(a|b)∗, la méthode de Thompson donne
l’automate suivant :

21 W.SAADI
 Passage de l’automate vers la grammaire
(principe)

Le principe de correspondance entre automates et

grammaires régulières correspond à l’observation
que chaque transition dans un automate produit
exactement un symbole, de même que chaque
dérivation dans une grammaire régulière
normalisée.

22 W.SAADI
Grammaire régulière normalisée
Elle est définie comme suit : soit G = (V, N, S, R) une
grammaire régulière à droite, elle est dite normalisée si
toutes les règles de production sont de l’une des formes
suivantes :

A→a tel que A ∈ N, a ∈ V ;

A → aB tel que A, B ∈ N, a ∈ V ;

A→ε tel que A ∈ N

23 W.SAADI
 Normalisation d’une grammaire régulière

1) Pour chaque règle de la forme A → wB (A, B ∈ N et w ∈ V∗)

tel que |w| > 1, créer un nouveau non-terminal B′ et éclater
la règle en deux :A → aB′ et B′ → uB tel que w = au et a ∈ V;

2) Pour chaque règle de la forme A → w (A ∈ N et w ∈ V∗) tel

que |w| > 1, créer un nouveau non-terminal B′ et éclater la
règle en deux :A → aB′ et B′ → u tel que w = au et a ∈ V ;

3) Recommencer 1) et 2) jusqu’à ce qu’il n’y ait plus de

nouveaux non terminaux ;

24 W.SAADI
Suite…
4) Enfin, l’élimination des règles A → B (A, B ∈ N), on
applique l’algorithme suivant :

1. Pour chaque règle A → B tel que B → β1|β2|...|βn

Rajouter une règle A → β1|β2|...|βn

Supprimer la règle A → B

2. Refaire l’étape 1) jusqu’à ce qu’il n’y ait plus de

règles de la forme A → B

25 W.SAADI
 Passage de l’automate vers la grammaire (1)
Soit A = (Σ,Q, q0, F, ) un AEF, la grammaire qui génère le
langage reconnu par A est G = (V, N, S, R) :

V = Σ;

On associe à chaque état de Q un non terminal. Ceci

permet d’avoir autant de non terminaux qu’il existe d’états
dans A;

L’axiome S est le non-terminal associé à l’état initial q0 ;

26 W.SAADI
Passage de l’automate vers la grammaire (2)
Soit A le non terminal associé à qi et B le non-terminal
associé à qj, si (qi, a) = qj alors la grammaire possède la
règle de production : A → aB ;

Si qi est final et A est le non-terminal associé à qi alors la

grammaire possède la règle de production : A → ε.

Il s’agit ici d’une grammaire régulière à droite normalisée

27 W.SAADI
Passage de la grammaire vers l’automate (1)
Soit G = (V,N, S, R) une grammaire régulière à droite, si
toutes les règles de production sont de la forme : A → aB
ou A → B (A, B ∈ N, a ∈ V ∪ {ε}) alors il suffit d’appliquer
l’algorithme suivant :
1) Associer un état à chaque non terminal de N;
2) L’état initial est associé à l’axiome ;
3) Pour chaque règle de production de la forme A → ε,
l’état qA est final ;

28 W.SAADI
Passage de la grammaire vers l’automate (2)
4) Pour chaque règle de production de la forme A → a (a
∈ V), alors créer un nouvel état final qf et une transition
partant de l’état qA vers l’état qf avec l’entrée a ;

5) Pour chaque règle A → aB alors créer une transition

partant de qA vers l’état qB en utilisant l’entrée a ;

6) Pour chaque règle A → B alors créer une ε-transition

partant de qA vers l’état qB ;

29 W.SAADI
Propriétés des langages réguliers

Soient L1 et L2 deux langages réguliers.

Les langages L1∪L2, L1∩L2, L1.L2, L1 et L1* sont des

langages réguliers.

30 W.SAADI
 Méthodes pour montrer qu’un langage est
régulier

On peut montrer la régularité d’un langage L, par l’une

des méthodes suivantes :

Tous les langages finis sont réguliers ;

Si on trouve un AEF qui reconnaît un langage L, alors L

est régulier;

Si on trouve une grammaire régulière générant L, alors

ce langage est régulier ;
31 W.SAADI
Suite…
On peut utiliser le théorème de Nerode pour
montrer qu’un langage est régulier ;

On peut exploiter les propriétés de fermeture pour

montrer qu’un langage est régulier.
Théorème de Nerode

Si L un langage sur un alphabet Σ, L est régulier si et

seulement si le nombre de ses dérivées par rapport

aux mots de Σ* est fini.

33 W.SAADI
Méthodes pour montrer qu’un langage n’est
pas régulier
Pour montrer l’irrégularité d’un langage L, il ne suffit pas de
ne pas pouvoir trouver un AEF le reconnaissant, on peut
utiliser les deux méthodes suivantes pour le faire :

Raisonnement par l’absurde pour le théorème de

l’étoile ;

Exploitation des propriétés de fermeture des langages

non réguliers.

34 W.SAADI
 Lemme de l’étoile (lemme de pompage ou
d’itération)

Il s’agit en fait d’une condition suffisante et non

nécessaire pour qu’un langage soit régulier.

Soit L un langage régulier (rationnel) infini. Il existe un

entier k tel que pour tout mot w de L plus long que
k, w se factorise en w=uvx, avec u,x ∈Σ* et v ∈Σ+
(i) |v| ≥1
(ii) |uv| ≤ k et
(iii) pour tout i > 0, uvix est également un mot de L.
35 W.SAADI
Remarque
Le lemme de l’étoile est utilisé pour démontrer qu’un
langage donné n’est pas régulier, soit en définissant la
contraposée du lemme ou en raisonnant par l’absurde.
On utilisant l’absurde, ainsi on suppose que le langage est
régulier et on trouve un mot du langage qui ne vérifie pas
la conclusion du lemme.
 Exemple 5
Soit le langage L1 = {anbn, n≥ 0} , on veut montrer que L1 n’est

pas régulier.

En appliquons le lemme de la pompe, on suppose que L1 est

régulier. Soit k la constante du lemme et soit w = akbk un

mot de L1.

Le lemme nous permet de déduire qu’il existe une

décomposition w=uvx tel que :

Suite…

|uv| ≤k et v≠ε uvix ∈ L1 et donc :

u = aj , v = al ,w = ambk (c’est le seul type de découpage

respectant la contrainte du lemme) avec j+l+m=k.

D’après le lemme pour tout i dans N, uviw appartient à L1.

On a : uvix = aj(al)iambk = aj(al)iak-j-lbk = ail+l+kbk= a(i+1)l+kbk

Suite…
donc on doit prouver que pour i=2, uv2x = a(i+1)l+kbk ∈L1

Alors que l>0 , ce qui signifie que le nombre de a est

différent du nombre de b. Contradiction. Donc L1 n’est

pas régulier.