Université Mouloud MAMMERI de Tizi-Ouzou
Faculté de génie électrique et informatique
Département d’informatique
Module : Théorie des Langages – L2 – année : 2023/2024
Chapitre III
Les langages réguliers
Par : Par : Mme FERHAOUI-CHERIFI Chafia
(reprise des notes de cours de Mr HABET Md-Said et de Mr KHEMLICHE Salem)
Contenu du chapitre :
III.1/ Automate d’états finis
III.2/ Modification des automates d’états finis
III.3/ Automates d’états finis et grammaires régulières à droite
III.4/ Propriétés de fermeture des langages réguliers
III.5/ Critères de régularité des langages
Chapitre III : Les langages réguliers
III.1 / Automate d’états finis :
III.1.1/ Introduction :
On a vu que les langages formels peuvent être représentés par des grammaires formelles ; et que les
langages réguliers sont les langages de type 3 dans la hiérarchie de Chomsky ; c'est-à-dire qu’ils peuvent
être générés par des grammaires de type 3.
Il existe une autre manière pour représenter les langages. C’est l’utilisation des automates. En général,
un automate est un système de reconnaissance, c'est-à-dire une machine capable de lire des mots, et pour
chaque mot lu elle répondra "oui" si le mot appartient au langage défini par l’automate.
Pour les langages réguliers, ces systèmes de reconnaissance sont appelés : automates d’états finis ; ce
sont des machines capables de lire des mots, et de répondre par "oui" si le mot lu est dans le langage et
"non" sinon.
III.1.2/ Schéma d’un automate d’états finis :
Un automate d’états finis est composé par :
- une bande d’entrée finie, sur laquelle va s’inscrire le mot à lire, la lecture se faisant de gauche vers la
droite ;
- un organe de commande qui permet de gérer un ensemble fini d’états.
Schématiquement :
Bande en entrée
Organe de commande
Définition III.1.3:
Un automate d’états finis � est un quintuplait (système à cinq éléments) :
� = < �, �, �, S0 , � > ; où :
� (ou V) : alphabet d’entrée ;
� (ou S) : ensemble des états ;
� (ou F) : ensemble des états finaux (� ⊂ �) ;
S0 : état initial (S0 ∈ �) ;
� (ou I) : ensemble des instructions (� ⊂ � × � × �).
� et � sont des ensembles finis et non vides.
-2-
Chapitre III : Les langages réguliers
Exemple III.1.4 :
Soit A = < V, S, F, S0, I > défini par :
V = {a, b, c}
S = {S0, S1, S2, S3}
F = {S1}
S0 : état initial
I = { (a, S0, S0), (b, S0, S1), (c, S1, S1), (c, S0, S2), (a, S3, S1) }
III.1.5/ Représentation graphique :
L’automate d’états finis est représenté par un graphe orienté dans lequel les sommets correspondent
aux états de l’automate et les arcs correspondent aux instructions.
instruction représentation
(a, Si, Sj) Si a Sj
- L’état initial est distingué par une grosse flèche incidente.
- Les états finaux sont distingués par deux cercles concentriques.
Dans le cas de l’exemple III.1.4, on a la représentation suivante :
S3
a c
a
S0 b S1
S2
III.1.6 / Notation des transitions :
La notation de l’instruction (a, Si, Sj) ∈ I est remplacée par : Si ⊢�� Sj (*) qui veut dire que la lettre a fait
passer l’automate A de l’état Si vers l’état Sj.
La relation (*) est dite relation de transition directe.
Cette relation peut être prolongée sur l’ensemble des mots d’entrée.
On dit que le mot w = a1 a2 … an fait passer l’automate A de l’état Si à l’état Sj de manière indirecte à n
pas si et seulement si : il existe une séquence d’états S1, …, Sn-1 ∈ S tels que :
Si ⊢�1 S1 ⊢�2 S2 … ⊢��−1 Sn-1 ⊢�� Sj
-3-
Chapitre III : Les langages réguliers
La transition indirecte est notée par : Si ⊢�
�∗ Sj
Pour toute lettre a, si Si ⊢ Sj alors on peut écrire Si ⊢�∗ Sj ;
�
et de même pour ε : Si ⊢ε∗ Si (en 0 étape).
Définition III.1.7 :
Soit A = < V, S, F, S0, I > un automate d’états finis.
Le langage accepté par cet automate est :
L(A) = { w ∈ V* / ∃ Sk ∈ F et S0 ⊢� �∗ Sk }.
L’automate A accepte les mots qui peuvent le faire passer de l’état initial S0 vers l’un des états finaux Sk.
Pour le cas de l’exemple III.1.4, on a :
- aaabc ∈ L(A) car :
S0 ⊢� S0 ⊢� S0 ⊢� S0 ⊢� S1 ⊢� S1 et S1 ∈ F.
- aac ∉ L(A) car :
S0 ⊢� S0 ⊢� S0 ⊢� S2 et S2 ∉ F. Et il n’existe aucune autre transition indirecte menant l’automate
de S0 vers S1 avec le mot aac.
III.2/ Modification des automates d’états finis :
Définition III.2.1 :
Deux automates A et B sont dits équivalents, et on note : A ≈ B, si et seulement si L(A) = L(B).
III.2.2/ Simplification des automates :
- Un état Si est inaccessible si on ne peut pas l’atteindre à partir de l’état initial :
∄ w ∈ V* / S0 ⊢� �∗ Si
Pour l’exemple III.1.4, l’état S3 est inaccessible.
On peut supprimer les états inaccessibles d’un automate sans changer le langage accepté par celui-ci.
- Un état puits Sp est un état qui ne mène pas à un état final :
∄ w ∈ V* / Sp ⊢� �∗ Sk avec Sk ∈ F
Pour l’exemple III.1.4, l’état S2 est un état puits.
On peut supprimer les états puits d’un automate sans changer le langage accepté par celui-ci.
Exemple : Simplification de l’automate de III.1.4 : on élimine l’état inaccessible S3 et l’état puits S2.
On obtient :
a c
S0 b S1
-4-
Chapitre III : Les langages réguliers
III.2.3/ Déterminisation d’un automate simple :
Une remarque préliminaire : un automate simple est un automate dans lequel toute transition directe est
étiquetée par une seule lettre.
Définition III.2.3.1 :
Un automate simple A = < V, S, F, S0, I > est dit déterministe lorsque la relation I est une fonction, plus
exactement, définie sur : V×S → S.
En d’autres termes : pour tout (a, Si) ∈ V×S, il existe au plus un état Sj tel que (a, Si, Sj) ∈ I.
Exemple III.2.3.2 :
Voici un automate non déterministe :
S1 Par exemple, à partir de l’état S0,
a on peut aller avec la même lettre ‘a’,
a vers deux états différents (S0 et S1).
S0
b b
b S2
Définition III.2.3.3 :
Un automate A = < V, S, F, S0, I > est dit complet lorsque la fonction I : V×S → S est totale.
En d’autres termes : pour tout (a, Si) ∈ V×S, il existe un état Sj tel que (a, Si, Sj) ∈ I (on note aussi :
I(a, Si) = Sj).
Proposition III.2.3.4 :
Tout automate d’états finis simple A = < V, S, F, S0, I > est équivalent à un automate simple
déterministe.
Démonstration :
Construisons l’automate A’ = < V, S’, F’, S'0 , I’ > à partir de A comme suit :
● S’ = 2S (ensemble des parties de S) ;
● F’ = { S'k ∈ S’ / S'k ∩ F ≠ Ø } ;
● S'0 = { S0 } ;
● I’ est tel que :
S'i ⊢��' S'j ⇔ S'j = { Sj ∈ S / ∃ Si ∈ S'i tel que Si ⊢�� Sj }.
-5-
Chapitre III : Les langages réguliers
On va montrer à présent que A ≈ A’ c'est-à-dire L(A) = L(A’). Pour cela montrons la proposition
auxiliaire suivante :
Proposition III.2.3.5 :
Soit A’ tel que défini précédemment, on a :
∀ w ∈ V* : S'0 ⊢� ' ' �
�'∗ Sj ⇔ Sj = { Sj ∈ S / S0 ⊢�∗ Sj }.
Démonstration de la proposition auxiliaire :
Par récurrence sur |w|.
- si |w| = 0 ⇔ w = ε
S'0 ⊢ε�'∗ S'j ⇔ S'j = S'0 = { S0 }
d’où : S'j = S'0 = { S0 } = { Sj ∈ S / S0 ⊢��∗ Sj }.
- hypothèse de récurrence :
supposons que la propriété est vraie pour tout w ∈ V* tel que 0 ≤ |w| ≤ k et montrons qu’elle
reste vraie pour tout w tel que : w ∈ V* et |w| = k+1.
Si |w| = k+1 alors w peut s’écrire w = α.a où |α| = k et a ∈ V.
S'0 ⊢��
�'
' ' ' � ' � '
∗ Sj ⇔ ∃ Sn ∈ S’ / S0 ⊢�'∗ Sn ⊢�' Sj
S'0 ⊢��'∗ S'n avec |α| = k ⇔ par hypothèse de récurrence : S'n = { Sn ∈ S / S0 ⊢��∗ Sn } (1)
d’autre part :
S'n ⊢��' S'j ⇔ par construction de A’ : S'j = { Sj ∈ S / ∃ Sn ∈ S'n tel que Sn ⊢�� Sj } (2)
(1) et (2) ⇔ S'j = { Sj ∈ S / ∃ Sn ∈ S tel que S0 ⊢��∗ Sn ⊢�� Sj }
⇔ S'j = { Sj ∈ S / S0 ⊢��
�∗ Sj } CQFD.
Suite de la proposition III.2.3.4 : L(A) = L(A’) ?
Soit X ∈ L(A’) ⇔ ∃ S'j ∈ F’ tel que : S'0 ⊢��'∗ S'j
S'j ∈ F’ ⇔ S'j ∩ F ≠ Ø ⇔ ∃ Sj ∈ S'j ∩ F tel que S0 ⊢��∗ Sj
puisque Sj ∈ F et S0 ⊢��∗ Sj alors X ∈ L(A).
Exemple III.2.3.6 : Déterminisation de l’automate de l’exemple III.2.3.2.
Construction de la table de transition :
a b
<S0> = q0 <S0,S1> <S2>
<S0,S1> = q1 <S0,S1> <S2>
<S2> = q2 / <S0,S2>
<S0,S2> = q3 <S0,S1> <S0,S2>
Les états soulignés sont les états finaux (q1, q2, q3).
Remarque : Bien que dans la construction de l’automate déterministe, on stipule que S’ = 2S ; pour cet
exemple on obtient huit (8) états ; on construit la table de transition à partir de <S0>, de telle manière à
obtenir uniquement les états accessibles et non puits.
-6-
Chapitre III : Les langages réguliers
On obtient la représentation graphique de l’automate déterministe :
a
q0 a q1
a
b b
b
q2 q3
b
III.2.4/ Mise sous forme simple d’automates généralisés :
Définition III.2.4.1 :
Un automate d’états finis généralisé est un système à cinq éléments A = < V*, S, F, S0, I > dont
les éléments V, S, F S0 jouent le même rôle que dans l’automate simple et I est un sous-ensemble
fini de V* × S × S.
Remarques :
1) Dans un automate simple, toute transition est toujours causée par une seule lettre ; cependant, dans un
automate généralisé il y a des transitions causées par des mots de V*, en particulier les transitions
causées par le mot vide sont dites transitions spontanées.
2) Un automate dont les transitions sont causées uniquement par des lettres de V ou par ε est dit
automate partiellement généralisé.
Exemple III.2.4.2 :
ab
S0
g cd
ε
ε e
S2 S1
f
(*) automate généralisé
-7-
Chapitre III : Les langages réguliers
Proposition III.2.4.3 :
Pour tout automate généralisé Ag = <V*, Sg, Fg,S0, Ig > il existe un automate simple équivalent A.
Démonstration :
On va construire l’automate simple A.
Pour commencer, considérons une transition : Si ⊢w
Ag Sk où : n = |w|, (n>1), w = a1 a2 … an.
Introduisons de nouveaux états non terminaux S'1 , … , S'n−1 ∉ Sg et remplaçons la transition considérée
an
par l’ensemble des transitions { Si ⊢a1 ' ' a2 ' '
Ag S1 , S1 ⊢Ag S2 ,, … , Sn−1 ⊢Ag Sk }.
Dans le cas de l’exemple (*) et de la transition S0 ⊢�� S1, on obtient :
ab
S0
c S’
g
ε
d
ε e
S2 S1
f
Après avoir répété le remplacement pour toutes les transitions sur le mots w tels que |w|>1, on obtient
un automate partiellement généralisé Ap = < V ∪ {ε}, S, Fp, S0, Ip > ; où S est l’union de Sg avec tous
les états ajoutés.
Dans le but d’éliminer les transitions spontanées, on construit l’automate simple A = < V, S, F, S0, I >
où :
a) Si ∈ F ⇔ (∃ Sk ∈ Fp / Si ⊢ε��∗ Sk)
b) Si ⊢a� Sk ⇔ (∃ Sj ∈ S / Si ⊢ε��∗ Sj ⊢a�� Sk )
Un mot w = a1 … an appartient au langage défini par l’automate Ap lorsqu’il existe une suite de
transitions de la forme :
S0 ⊢ε��∗ Ŝ1 ⊢a1 ε a2 ε an ε
�� S1 ⊢��∗ Ŝ2 ⊢�� S2 … Sn-1 ⊢��∗ Ŝn ⊢�� Sn ⊢��∗ Ŝn+1 ∈ Fp
L’automate A peut alors effectuer la suite des transitions suivante :
S0 ⊢a1 a2 an
� S1 ⊢� S2 … Sn-1 ⊢� Sn , Sn ∈ F
On aura donc : A ≈ Ap ≈ Ag.
-8-
Chapitre III : Les langages réguliers
Ainsi pour l’exemple III.2.4.2, on obtient :
l’automate Ap :
S’’
b
S0
c S’
g
ε
d
ε e
S2 S1
f
et l’automate A :
S’’
b
a
a
S0 a
c S’
g
c
c d
g e, f
S2 S1
g f
-9-
Chapitre III : Les langages réguliers
III.3/ Automates d’états finis et grammaires régulières à droite :
Proposition III.3.1 :
Pour toute grammaire régulière à droite g = < π, N, S, P > il existe un automate généralisé
A = <V*, Sa, F,S0, I > équivalent.
Démonstration :
Soit V = π ;
Sa = N ∪ {Z} ; (Z ∉ π ∪ N)
F = {Z} ;
S0 = S ;
�
X ⊢� Y ⇔ X wY
�
X ⊢�
� Z ⇔ X w
�
À toute dérivation dans la grammaire g de la forme :
S ⊢� w1 A1 ⊢� w1 w2 A2 … ⊢� w1 w2 … wn-1 An-1 ⊢� w1 w2 … wn-1 wn
on peut associer une séquence de transitions de l’automate A comme suit :
S ⊢�1 �2
� A1 ⊢� A2 … ⊢�
��−1
An-1 ⊢��
� Z
On peut conclure que : w ∈ L(g) ⇒ w ∈ L(A).
Comme l’implication réciproque se déroule de la même manière, on obtient finalement :
L(g) = L(A).
Exemple III.3.2 :
Soit la grammaire g = < π, N, S, P >
π = {a, b, c} S
N = {S, A, B}
P : S → abA | S ⊢�� A ab
A → cS | A ⊢� S c
A → cb | A ⊢�� Z
A
A→B | A ⊢ε B
B→ε | B ⊢ε Z
cb ε
ε B
Z
- 10 -
Chapitre III : Les langages réguliers
Proposition III.3.3 :
Pour tout automate généralisé A = <V*, Sa, F,S0, I > il existe une grammaire régulière à droite
g = < π, N, S, P > équivalente.
Démonstration :
Soit π = V ;
N = Sa ;
S = S0 ;
Si w Sk ⇔ Si ⊢w� Sk
�
Si w ⇔ Si ⊢w
� Sk et Sk ∈ F
�
Conformément à la définition précédente, toute transition de la forme : Si ⊢w
� Sk correspond à la
production : Si w Sk ; et si Si ∈ F on ajoute à P la production : Si → ε.
�
Toute séquence de transition de l’automate de la forme :
S0 ⊢�1 �2
� S1 ⊢� S2 … ⊢�
��−1
Sn-1 ⊢��
� Sn ∈ F
peut être associé à la dérivation :
S0 ⊢� w1 S1 ⊢� w1 w2 S2 … ⊢� w1 w2 … wn-1 Sn-1 ⊢� w1 w2 … wn-1 wn
De cette manière, on arrive à la conclusion : w ∈ L(A) ⇒ w ∈ L(g).
Comme l’implication réciproque se démontre de la même manière, nous obtenons finalement :
L(A) = L(g).
Exemple III.3.4 :
À l’automate de l’exemple III.2.4.2 :
ab
S0
g cd
ε
ε e
S2 S1
f
on peut associer la grammaire g = < π, N, S, P >, avec :
π = {a, b, c, d, e, f, g } ; N = { S0, S1, S2 } ;
S = S0
P : S0 → ab S0 | cd S1 | g S2
S1 → e S1 | S2
S2 → S0 | f S1 | ε
- 11 -
Chapitre III : Les langages réguliers
III.4/ Propriétés de fermeture des langages réguliers :
Des propriétés de fermeture sont essentielles à tous les ensembles munis d’opérations mathématiques.
Dans la théorie des langages formels, l’étude de ces propriétés constitue le fondement des investigations
théoriques avancées.
Proposition III.4.1 :
La classe des langages réguliers est fermée par rapport à la réunion.
Démonstration :
Soient deux langages réguliers L1 ⊂ V∗1 et L2 ⊂ V∗2 .
Il existe deux automates d’états finis à savoir :
A1 = < V1, S1, F1, S01, I1 > tel que L1 = L(A1)
A2 = < V2, S2, F2, S02, I2 > et L2 = L(A2) avec S1 ∩ S2 = Ø
Considérons l’automate partiellement généralisé A suivant :
A = < V*, S, F, S0, I > tel que :
V = V1 ∪ V2 ;
S = S1 ∪ S2 ∪ {S0} (S0 ∉ S1 ∪ S2)
F = F1 ∪ F2
I = I1 ∪ I2 ∪ { S0 ⊢ε� S01 ; S0 ⊢ε� S02 }
On constate qu’après la transition S0 ⊢ε� S01, A fonctionne comme A1 ; et qu’après la transition
S0 ⊢ε� S02, A fonctionne comme A2. Un mot w est accepté par A si et seulement si il est accepté soit par
A1, soit par A2. On a alors :
L(A) = L(A1) ∪ L(A2) = L1 ∪ L2.
Donc la réunion de langages réguliers est un langage régulier.
Proposition III.4.2 :
La classe des langages réguliers est fermée par rapport à la complémentation.
Démonstration :
Soit un langage régulier L⊂ V*, il existe un automate d’états finis déterministe A = <V, S, F, S0, I > qui
accepte L. On suppose que cet automate est complet (voir définition III.2.3.3).
Considérons l’automate B = <V, S, S-F, S0, I > (B est obtenu en changeant tous les états finaux de A en
non-finaux et vice-versa).
Après avoir lu un mot quelconque de w ∈ V*, l’état final correspondant à w est soit l’état final de A
(auquel cas w ∈ L(A)), soit l’état final de B (auquel cas w ∈ L(B)) ; on a donc : L B = L(A).
Donc le complémentaire d’un langage régulier est régulier.
- 12 -
Chapitre III : Les langages réguliers
Proposition III.4.3 :
La classe des langages réguliers est fermée par rapport à l’intersection.
Démonstration :
D’après les formules de De Morgan, on peut exprimer l’intersection des langages L1 et L2 par la réunion
et la complémentation : L1 ∩ L2 = L1 ∪ L2 .
La proposition III.4.3 est donc la conséquence des propositions III.4.1 et III.4.2.
Proposition III.4.4 :
La classe des langages réguliers est fermée par rapport à l’opération miroir.
Démonstration :
Soit un langage régulier L ⊂ V*, il existe un automate d’états finis simple et déterministe A qui accepte
le langage L : A = <V, S, F, S0, I >.
Considérons l’automate partiellement généralisé B = <V, S’, F’, S'0 , I’ > ; où :
S’ = S ∪ S'0 (S'0 ∉ S)
F’ = {S0}
S'0 est l’état initial
I’ est construit comme suit :
Si ⊢a� Sk ⇒ Sk ⊢a� Si (on inverse le sens des "flèches") ;
Si ∈ F ⇒ S'0 ⊢ε� Si (on ajoute des ε-transitions du nouvel état initial S'0 vers les anciens
états finaux).
Ainsi, à toute séquence de transitions de l’automate A de la forme :
S0 ⊢�1 �2
� S1 ⊢� S2 … ⊢�
��−1
Sn-1 ⊢��
� Sn ∈ F peut être associée à la séquence :
' ε �� ��−1
S0 ⊢� Sn ⊢� Sn-1 ⊢� Sn-2 … ⊢�2 �1
� S1 ⊢� S0 ∈ F’.
On a donc : w = a1 a2 … an-1 an ∈ L(A) ⇒ wR = an an-1 … a2 a1 ∈ L(B).
Comme l’implication réciproque se démontre de la même façon, on obtient finalement : (L(A))R = L(B).
Donc le reflet miroir d’un langage régulier est un langage régulier.
Proposition III.4.5 :
La classe des langages réguliers est fermée par rapport à la concaténation.
Démonstration :
Soient deux langages réguliers L1 ⊂ V∗1 et L2 ⊂ V∗2 .
Il existe alors deux automates d’états finis simples A = < V1, S1, F1, S01, I1 > et B = < V2, S2, F2, S02, I2 >
qui acceptent respectivement L1 et L2.
Considérons l’automate partiellement généralisé C suivant : C = < V, S, F, S01, I > ; où :
F = F2 ;
V = V1 ∪ V2 ;
S = S1 ∪ S2 ;
I = I1 ∪ I2 ∪ { Sk ⊢ε S02 / Sk ∈ F1 }.
- 13 -
Chapitre III : Les langages réguliers
On a :
w1 ∈ L(A) ⇒ S01 ⊢�1�∗ Sn1 ∈ F1
�2
w2 ∈ L(B) ⇒ S02 ⊢�∗ Sn2 ∈ F2 donc : w1.w2 ∈ L(C).
Donc la concaténation de deux langages régulier est un langage régulier.
Proposition III.4.6 :
La classe des langages réguliers est fermée par rapport à l’itération positive.
Démonstration :
On définit l’itération positive d’un langage L comme étant égale à L+ (égale à : L1 ∪ L2 ∪ L3 ∪ …).
Soit un langage régulier L⊂ V*, il existe un automate d’états finis A = <V, S, F, S0, I > qui accepte L.
Considérons l’automate partiellement généralisé A’ = <V, S, F, S0, I’ > ; où :
I’ = I ∪ { Si ⊢ε S0 / Si ∈ F } (on ajoute des ε-transitions reliant tous les états finaux à l’état initial).
On a :
w1 ∈ L(A) ⇒ S0 ⊢�1 �∗ Sk, Sk ∈ F
w2 ∈ L(A) ⇒ S0 ⊢�2 �∗ Sk’, Sk’ ∈ F
.
.
.
wn ∈ L(A) ⇒ S0 ⊢�� �∗ St, St ∈ F
impliquent que le mot : w1.w2. … .wn ∈ L(A’) car :
S0 ⊢�1 S ⊢ε S ⊢�2 S … S0 ⊢��
�'∗ k �' 0 �'∗ k’ �'∗ St, St ∈ F
Donc l’itération positive d’un langage régulier est un langage régulier.
Proposition III.4.7 :
La classe des langages réguliers est fermée par rapport à l’itération.
Démonstration :
On définit l’itération d’un langage L comme L* étant égale à : L+ ∪ ε.
Si L est un langage régulier alors L* est aussi régulier, cela découle des propositions III.4.6 et III.4.2
(l’union de deux langages réguliers est un langage régulier : L+ et ε étant réguliers).
Donc l’itération d’un langage régulier est un langage régulier.
- 14 -
Chapitre III : Les langages réguliers
III.5/ Critères de régularité des langages :
Conformément à la définition, un langage L est régulier lorsqu’il possède une grammaire régulière qui
l’engendre. En vue de vérifier la régularité d’un langage donné de manière abstraite, il faut alors
construire la grammaire correspondante, ou montrer qu’une telle grammaire n’existe pas. Dans les deux
cas, on s’appuie sur les propriétés d’un langage régulier dites caractéristiques algébriques des langages
réguliers. Le théorème de Nerode (1957) a été utilisé par Rabbin et Scott (1959) et par Brzozowski (1964).
Il existe aussi un lemme de caractérisation des langages réguliers dit lemme de pompage.
III.5.1/ Dérivées de langages et théorème de Nerode :
Définition III.5.1.1 :
Soit un langage L ⊂ V* et soit w ∈ V*. Une dérivée (à droite) du langage L par rapport au mot w est le
langage : L || w = { z ∈ V* / wz ∈ L }.
Exemple III.5.1.2 :
- Soit L = {0100, 110, 0001, 01, 1}, on a :
L || 0 = {100, 001, 1}
L || 1 = {10, ε}
L || 01 = {00, ε}
- Soit L = { ai.bj / i, j ≥ 0 }, on a :
L || a = { ai.bj / i, j ≥ 0 } = L
L || b = { bj / j ≥ 0 }
L || ab = L || b
III.5.1.3/ Propriétés :
La dérivation des langages vérifie les propriétés suivantes :
1) ε si ai = aj
ai || aj = Ø si ai ≠ aj
n n
2) i=0 Li || a = i=0 (Li || a)
3) (L1.L2) || a = (L1 || a). L2 ∪ φ(L1).(L2 || a)
où : ε si ε ∈ L1
φ(L1) = Ø si ε ∉ L1
4) (L*) || a = (L || a).L*
5) L || w1.w2 = (L || w1) || w2
Démonstration :
1) ε si ai = aj
ai || aj = Ø si ai ≠ aj évident
n n
2) i=0 Li || a = i=0 (Li || a) :
- 15 -
Chapitre III : Les langages réguliers
n
Soit z ∈ i=0 Li || a ⇔ a.z ∈ ni=0 Li ⇔ ∃ j / a.z ∈ Lj ⇔ z ∈ Lj || a
n
⇔ z∈ i=0 (Li || a) d’où l’égalité.
3) (L1.L2) || a = (L1 || a). L2 ∪ φ(L1).(L2 || a) :
où : ε si ε ∈ L1
φ(L1) = Ø si ε ∉ L1
Soit z ∈ (L1.L2) || a ⇔ a.z ∈ L1.L2 ⇔ ∃ w1 ∈ L1 et ∃ w2 ∈ L2 tel que a.z = w1.w2.
- si ε ∉ L1 ⇔ w1 ≠ ε ⇔ w1 = a.w1’ ⇔ w1’ ∈ L1 || a ⇔ z = w1’.w2 ∈ (L1 || a).L2.
- si w1 = ε ⇔ a.z = w2 ⇔ z ∈ L2 || a et ε ∈ L1.
⇔ z ∈ (L1 || a). L2 ∪ φ(L1).(L2 || a) où :
ε si ε ∈ L1
φ(L1) = Ø si ε ∉ L1
4) (L*) || a = (L || a).L* :
On utilise le lemme suivant :
Lemme : Pour tout langage L, on a : L* = (L ∪ ε)*.
Démonstration du lemme : pour tout n ≥ 0, w ∈ V* / w ∈ (L ∪ ε)n ⇔ w est une concaténation
de n mots de (L ∪ ε) parmi lesquels k sont non vides (0 ≤ k ≤ n) donc w ∈ Lk ; d’où :
w ∈ (L ∪ ε)* ⇒ w ∈ L*.
D’autre part : pour tout n, w ∈ Ln ⇒ w ∈ (L ∪ ε)n ; d’où :
w ∈ L* ⇒ w ∈ (L ∪ ε)*.
D’où finalement : L* = (L ∪ ε)*.
Dans le cas de la propriété 4) :
- si ε ∉ L :
(L*) || a = (ε ∪ L.L*) || a = (ε || a) ∪ (L || a).L* ∪ φ(L).(L* || a) = (L || a).L*
- si ε ∈ L :
on pose : Ł = L – { ε }.
On a :
(L*) || a = (Ł*) || a = (Ł || a).Ł* = (L || a).L*
5) L || w1.w2 = (L || w1) || w2 :
Soit z ∈ (L || w1.w2) ⇔ w1.w2.z ∈ L ⇔ w2.z ∈ (L || w1) ⇔ z ∈ ((L || w1) || w2).
Proposition III.5.1.4 :
- 16 -
Chapitre III : Les langages réguliers
Pour tout langage régulier, le nombre de ses dérivées par rapport aux mots sur V est fini.
Démonstration :
Soit A = < V, S, F, S0, I > un automate d’états finis déterministe et complet qui accepte L.
Considérons deux mots w1, w2 ∈ V* au même état Sj :
S0 ⊢�1 �2
�∗ Sj et S0 ⊢�∗ Sj
Ainsi pour tout mot z ∈ V*, on a : S0 ⊢�1.� �1 � �2
�∗ Sk ⇔ S0 ⊢�∗ Sj ⊢�∗ Sk ⇔ S0 ⊢�∗ Sj ⊢�∗ Sk
�
⇔ S0 ⊢�2.�
�∗ Sk ; l’état Sk peut appartenir à F ou non ; dans les deux cas : w1.z ∈ L ⇔ w2.z ∈ L
Autrement dit : z ∈ L || w1 ⇔ z ∈ L || w2
D’où : L || w1 = L || w2.
Alors le nombre de dérivées de L par rapport aux différents mots sur V ne peut pas être supérieur au
nombre d’états de l’automate A ; comme ce nombre est fini donc le nombre de dérivées est aussi fini.
Proposition III.5.1.5 : (Réciproque de III.5.1.4)
Tout langage L avec un nombre fini de dérivées par rapport aux mots sur V fini est régulier.
Démonstration :
Considérons l’automate d’états finis : A = < V, S, F, S0, I > construit comme suit :
S = { L || w / w ∈ V* } ;
F = { St ∈ S / ε ∈ St } ;
S0 = L ;
Si ⊢�� Sk ⇔ Sk = Si || a.
Avant tout, on va démontrer par récurrence sur |w| que pour tout mot w et tous les états Si, Sk, on a :
Si ⊢��∗ Sk ⇔ Sk = Si || w
- pour w = ε (|w| = 0) : l’équivalence est évidente, car : Si ⊢ε�∗ Sk ⇔ Si = Sk ⇔ Sk = Si || ε.
- supposons que l’équivalence considérée est vraie pour une longueur n ≥ 0 ; i.e |w| = n ≥ 0.
Considérons le mot w’ = w.a, on a :
Si ⊢wa � �
�∗ Sk ⇔ (∃ Sj ∈ S) (Si ⊢�∗ Sj ⊢� Sk) ⇔ (∃ Sj ∈ S) (Sj = Si || w et Sk = Sj || a)
⇔ Sk = Si || wa.
D’où :
L(A) = { w ∈ V* / (∃ Sk ∈ F), S0 ⊢� �∗ Sk } = { w ∈ V / (L || w) ∈ F } = { w ∈ V / ε ∈ (L || w) } = L.
* *
THÉORÈME III.5.1.6 :
Le théorème de Nerode s’énonce comme la conjonction des deux propositions III.5.4 et III.5.5 :
Un langage L, défini sur un alphabet V, est régulier si et seulement si le nombre de ses dérivées par
rapport aux mots de V* est fini.
Exemple III.5.1.7 :
Considérons le langage : L = { ai.bj / i, j ≥ 0 }.
Soit S0 = L, calculons les dérivées de S0 :
S0 || a = L = S0 ⇒ S0 ⊢�� S0
S0 || b = { bj / j ≥ 0 } = S1 ⇒ S0 ⊢�� S1
S1 || a = Ø = S2 ⇒ S1 ⊢�� S2
- 17 -
Chapitre III : Les langages réguliers
S1 || b = S1 ⇒ S1 ⊢�� S1
S2 || a = Ø = S2 ⇒ S2 ⊢�� S2
S2 || b = Ø = S2 ⇒ S2 ⊢�� S2
L possède un nombre fini de dérivées donc il est régulier. Il peut être accepté par l’automate suivant :
a b a, b
S0 b S1 a S2
Remarque : L’état S2 est un état puits, on peut le supprimer sans changer le langage L(A).
Exemple III.5.1.8 :
Soit L = {an.bn / n ≥ 0 }.
On va démontrer que L n’est pas régulier, par deux méthodes :
1) Calculons les dérivées de L par rapport à ak, pour k ≥ 1 ; pour cela on pose S0 = L ; et on note :
Sk = S0 || ak (pour k ≥ 1).
On peut remarquer déjà que Sk = Sk-1 || a, pour k ≥ 1 ;
on a donc :
S1 = S0 || a = {an-1.bn / n ≥ 1} = {an-1.bn-1 / n ≥ 1 }.{b} = {an.bn / n ≥ 0 }.{b} = S0.{b}
S2 = S1 || a = (S0.{b}) || a = (S0 || a).{b} ∪ ({b} || a) = (S0 || a).{b} = (S0.{b}).{b} = S0.{bb}
S3 = S2 || a = (S0.{bb}) || a = (S0 || a).{bb} = (S0.{b}).{bb} = S0.{bbb} = S0.{b3}
…
On peut généraliser en démontrant par récurrence que :
Sk = Sk-1 || a = (S0.{bk-1}) || a = (S0 || a).{bk-1} = (S0.{b}).{bk-1} = S0.{bk}, pour tout k ≥ 1.
Pour chaque valeur de k dans ℕ (entiers naturels), on a un langage Sk différent des autres langages
Si (pour i≠k). On peut donc conclure qu’il y a une infinité de langages (Sk)k≥1, tous différents les uns des
autres et par conséquent il y a une infinité de dérivées du langage S0, donc celui-ci n’est pas régulier.
2) Démonstration par l’absurde : On suppose que L est régulier, donc d’après le théorème de Nerode, le
nombre de ses dérivées par rapport aux mots sur V ={a, b} est fini. Donc il existe deux entiers p et q tels
que p ≠ q et L || ap = L || aq. De plus, on sait que : ap.bp ∈ L ⇒ bp ∈ L || ap ⟹ bp ∈ L || aq ⟹ aq.bp ∈ L
avec p ≠ q ⟹ contradiction. D’où L n’est pas régulier.
Exercice III.5.1.9 :
De la même manière que l’exemple précédent, montrer que le langage {an.b2.n / n ≥ 0 } n’est pas régulier.
III.5.2/ Lemme de pompage (ou lemme de l’étoile) :
- 18 -
Chapitre III : Les langages réguliers
Soit L un langage défini sur un alphabet fini V. Si L est régulier alors il existe un entier N tel que tout
mot w de L de longueur |w| ≥ N possède une factorisation w = x.y.z telle que :
a) 0 < |y| ≤ N et
b) ∀ k ≥ 0, x.yk.z ∈ L.
Démonstration :
Soit L un langage régulier. Il existe un automate d’états finis A = < V, S, F, S0, I > qui accepte L.
On suppose que A est simple. Soit N le nombre d’états de A.
Soit w un mot de L tel que |w| ≥ N. Comme w est dans L, il existe un chemin S0 ⊢w A∗ Sf où Sf ∈ F.
Soient a1, a2, …, aN les N premières lettres de w, posons w = a1a2…aN.w' ; et soient S1, S2,…, SN les états
successifs atteints après la lecture de chacune de ces lettres. On a :
S0 ⊢a1 S1 ⊢a2 S2 … SN-1 ⊢aN SN ⊢w' ∗ Sf.
Parmi les N+1 états S0, S1, S2,…, SN il y a forcément deux qui sont égaux. Il existe donc deux entiers n
et m tels que 0 ≤ n < m ≤ N et Sn = Sm. Posons s = Sn = Sm et : x = a1…an, y = an+1…am,
y
et z = am+1…aN. w'. On a donc : S0 ⊢xA∗ s ⊢A∗ s ⊢zA∗ Sf.
yk
Il en résulte que : s ⊢A∗ s pour tout k ≥ 0 ; donc x.yk.z ∈ L pour tout k ≥ 0.
Remarque III.5.2.1 :
Le lemme de pompage donne une condition nécessaire pour qu’un langage soit régulier.
Exemple III.5.2.2 :
À l’aide du lemme de pompage, on va montrer que le langage L = { an.bn / n ≥ 0 } n’est pas régulier.
En effet, supposons que L est régulier. Soit N > 0 la constante associée à L.
Soit w un mot de L. Donc w = an.bn (avec 2.n≥N).
Soit la factorisation w = x.y.z avec 0 < |y| ≤ N. Il y a trois cas possibles :
a ……………….. a b ………………… b
1 2
3
Cas 1 : y = a , 0 < i ≤ N ; dans ce cas w s’écrit w = an-i.ai.bn et x.yk.z = an-i.ak.i.bn ∉ ℒ car :
i
n-i+k.i ≠ n si k ≠ 1.
Cas 2 : y = bj, 0 < j ≤ N ; dans ce cas w s’écrit w = an.bj.bn-j et x.yk.z = an.bk.j.bn-j ∉ ℒ car :
n-j+k.j ≠ n si k ≠ 1.
Cas 3 : y = ai.bj, 0 < i + j ≤ N ; dans ce cas w s’écrit w = an-i.ai.bj.bn-j et x.yk.z = an-i.(ai.bj)k.bn-j ∉ ℒ
car : an-i.(ai.bj)k.bn-j n’est pas de la forme am.bm si k > 1 (il y a alternance de séries de ‘a’
suivie de série de ‘b’ suivie de série de ‘a’,…).
On en déduit que la condition nécessaire d’existence de la factorisation d’un mot w de L vérifiant les
conditions données n’est pas vérifiée ; donc L n’est pas régulier.
----------–––––---------- Fin du chapitre III ----------–––––----------
- 19 -
