Langages et automates

Définitions générales

Alphabet : Un alphabet est un ensemble fini, non vide, de symboles (appelés aussi lettres ou
caractères). On le note généralement Σ. Le nombre de symboles qu’il contient est appelé sa
cardinalité et dénoté par |Σ|.
Exemple : Le langage machine est basé sur l’alphabet Σ = {0, 1}. |Σ|=2

Mot (ou chaîne) : Un mot sur un alphabet Σ est une suite finie de symboles de Σ.
Exemple :
- Le mot 1011 est défini sur l’alphabet {0, 1}
- Le mot 6.1239 est défini sur l’alphabet {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, .}

Longueur : La longueur d’un mot w notée |w| est le nombre de symboles de ce mot.
Exemple :
- Le mot w = 010 est de longueur |w| = 3.
- Le mot u = 01110 est de longueur |u| = 5.
- Le mot vide noté ε est le seul mot de longueur nulle, |ε|=0.
On note :
- Σ* l’ensemble de tous les mots (y compris le mot vide ε) définis sur Σ.
- Σ+ représente l’ensemble des mots sur l’alphabet Σ de longueur ≥ 1.
- Σn représente l’ensemble des mots sur l’alphabet Σ de longueur n.

Opérations sur les mots

Concaténation : La concaténation de deux mots u et v de Σ* est un mot noté u.v ou uv et défini

par : u = u1u2…un, v = v1v2…vn , w =u.v=uv= u1…unv1…vn , |uv|=|u|+|v|
Cette opération est associative, non commutative, et ε est l’élément neutre.

Propriété de la concaténation
Soient w, w1 et w2 trois mots définis sur l’alphabet Σ :
- |w1.w2| = |w1| + |w2|
- (w1.w2).w3 = w1.(w2.w3) (la concaténation est associative)
- w. ε = ε.w = w (ε est un élément neutre pour la concaténation)

Exposant (puissance)
La puissance n-ième d’un mot est définie par : wn=w…w (n fois), w0 = ε, wn+1 = wnw.

Mot miroir
Soit w = a1a2...an un mot définit sur l’alphabet Σ. On appelle mot miroir de w et on le note par
wR le mot obtenu en écrivant w à l’envers, c’est-à-dire : wR = an...a2a1. Il est donc facile de voir
que (wR)R = w.

Mots conjugués
Les mots w1 et w2 sont dits conjugués s’il existe deux mots u et v tels que : w1 = uv et w2 = vu.

Préfixe et suffixe
Un mot u ∈ Σ* est préfixe du mot w ∈ Σ* s’il existe v ∈ Σ* tel que w = uv. Le mot v est dit
suffixe du mot w.

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−1
Projection
Soit le mot u ∈ Σ* et un alphabet Σ ⊆ Σ. La projection de u sur Σ , notée u ↑ Σ , est la suite
obtenue de u en gardant les symboles qui appartiennent à Σ et effaçant les autres symboles.
Exemple : Soit Σ = {a, b, c} et Σ = {a, b}. On considère le mot u = cacbcca, sa projection sur
Σ est obtenue en gardant les a et b et en effaçant tous les c et donc u ↑ Σ = aba.

Langage
Un langage L sur Σ est un sous-ensemble de Σ*, c’est-à-dire, L ∈ P(Σ*) ou L ⊆ Σ*. Sa cardinalité,
à savoir le nombre de mots qu’il contient, est notée |L|.
Exemple :
- Langage des nombre binaires définies sur l’alphabet Σ ={0, 1} (langage infini)
- Langage des mots de longueur 2 défini sur l’alphabet Σ ={a, b}, L={aa, ab, ba, bb}
- L= ∅ est le langage vide, il ne contient aucun mot

Opérations sur les langages

Soit L, L1 et L2 trois langages définis sur l’alphabet Σ.
- Union (somme) : L1 ∪ L2 = L1 + L2 = {w ∈ Σ* | w ∈ L1 ou w ∈ L2}
- Intersection : L1 ∩ L2 = {w ∈ Σ* |w ∈ L1 et w ∈ L2}
- Concaténation (produit) : L = L1.L2 = L1L2 = {w ∈ Σ*| ∃ w1∈ L1 et ∃ w2∈ L2 : w = w1w2}
- Différence : L1-L2 = {w ∈ Σ* | w ∈ L1 et w ∉ L2}
- Complément : Le complémentaire d’un langage L est noté Σ*\ L = {w ∈ Σ* | w ∉ L}
- Puissance : Ln +1 = Ln L avec L0 = ε
- Clôture de Kleene (Kleene star) ou étoile de L : La clôture de Keene d’un langage L est
l’ensemble des mots construits par une concaténation finie des mots de L notée :
+∞
L* =  Lk = L0 ∪ L1 ∪ L2 ∪  ∪ Ln ∪ 
k =0
L = {w ∈ Σ* | ∃ k ∈ N, ∃ w1, w2, …, wk ∈ L : w = w1w2…wk}.
*

Ce langage contient un nombre infini de mots, qui sont les répétitions indéfinies de mots
du langage L.
+∞
- Fermeture plus : L+ =  Lk = L1 ∪ L2 ∪  ∪ Ln ∪ 
k =1

- Préfixe-clôture : on appelle la préfixe-clôture de L le langage L contenant tous les

préfixes des mots de L : L = {w1 ∈ Σ*| ∃ w2∈Σ* : w1w2 ∈L}. On a par définition
L ⊆ L . Un langage L est dit préfixe-clos si L = L .
Exemple : Soient les langages L1 = {ab,ba} , L2 = {c,cc} et L3 = {ac} . Nous avons :
- L1L2 = {abc,abcc,bac,bacc}
- L1L2L3 = {abcac,abccac,bacac,baccac}
- L12 = {abab,abba,baab,baba}
- L1 = {ε, a, ab, b, ba}

Propriétés des opérations sur les langages

Soit L, L1, L2 et L3 quatre langages définis sur l’alphabet Σ :
- L* = L+ + { ε }
- L+ = L* L = L L*
- L1.(L2.L3) = (L1.L2).L3
- L1.(L2 + L3) = (L1.L2) + (L1.L3)
- L.L ≠ L

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−2
 - L1.(L2 ∩ L3) ≠ (L1 ∩ L2).(L1 ∩ L3)
- L1.L2 ≠ L2.L1
- (L*)* = L*
- L*.L* = L* ;
- L1.(L2.L1)* = (L1.L2) *.L1
- (L1 + L2) * = (L1* L2*)*
- L1* + L2* ≠ (L1 + L2) *

Langages réguliers (rationnels)

En théorie des langages, les langages rationnels ou langages réguliers ou encore langages
reconnaissables peuvent être décrits de plusieurs façons équivalentes :

– Ce sont les langages décrits par les expressions régulières ou rationnelles, d’où le nom de
langages réguliers ;
– Ce sont les langages obtenus, à partir des lettres et de l’ensemble vide, par les opérations
rationnelles (union, produit et l’étoile de Kleene), d’où le nom de langages rationnels ;
– Ce sont les langages reconnus par des automates finis, d’où le nom de langages
reconnaissables.

Les expressions régulières (ou rationnelles) sont une notation qui indique comment un
ensemble régulier est construit à partir des ensembles réguliers élémentaires.

Remarque :
– Tout langage fini est rationnel.
– Si L est rationnel, alors L* est rationnel.
– Si L1 et L2 sont rationnels, alors L1 + L2 et L1L2 sont rationnels

Expressions régulières
Les expressions régulières (ER) pour un alphabet Σ sont les expressions formées par les règles
suivantes :
- Règle 1 : ∅ et chaque lettre de Σ est une ER
- Règle 2 : si α et β sont des ER, alors (αβ), (α+β) et α* sont des ER
- Règles 3 : On ne peut obtenir des expressions régulières qu’en appliquant de manière
finie les règles 1 et 2 énoncées ci-dessus.

Le langage L(ER) représenté par l’expression régulière ER est défini ainsi :

- L(∅) = ∅, L(ε) = {ε}
- L(a) = {a} pour tout a ∈ Σ
- L(αβ) = L(α).L(β)
- L(α+β) = L(α)+L(β)
- L(α*) = L(α)*

Exemple :
Soit l’alphabet Σ = {a, b, c}
(a + b + c)* : L’ensemble de tous les mots définis à partir de l’alphabet Σ
(a + b + c)*a : L’ensemble de tous les mots finissant par le symbole a
(a + b + c) (a + b + c)* : L’ensemble de tous les mots non vides définis à partir de l’alphabet Σ
(a + b)*b(a + b)* : Définit l’ensemble des mots composés par a et b contenant au moins un b.
0 + 10* : C’est le langage formé du mot 0 et des mots composés d’un 1 suivi d’un nombre
quelconque de 0 : {0, 1, 10, 100, . . .}.

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−3
Remarque :
Ordre de priorité sur les opérations : priorité (étoile) > priorité (concaténation) > priorité
(union). L’expression 0 + 10* est donc équivalente à (0 + (1(0)*)).

Quelques équivalences utiles :

(ab)*a = a(ba)* ; a+=aa*=a*a ; a*=(ε + a)* =a*a*=(a*)* ;
(a + b)* = (a*b*)* = (a*+b*)* = (a*b)*a* ;

Automates Finis
On rencontre couramment des automates finis (ou automates à états finis) dans de nombreux
appareils qui réalisent des actions déterminées en fonction des évènements qui se présentent.
Exemples :
- Un distributeur automatique de boissons qui délivre l’article souhaité quand le montant
introduit est approprié,
- Les ascenseurs qui savent combiner les appels successifs pour s’arrêter aux étages
intermédiaires,
- Les feux de circulation capables de s’adapter aux voitures en attente,
- Des digicodes qui analysent la bonne suite de chiffres,
On distingue deux types d’automates finis :
- AFD : automate fini déterministe
- AFN : automate fini non déterministe

Automate fini déterministe

Un automate fini déterministe (AFD) est définit par un quintuplet A = (∑, Q, δ, q0, F) où :
- ∑ est un ensemble fini de symboles appelé alphabet.
- Q est un ensemble fini dont les éléments sont appelés états.
- δ est une relation de Q × ∑ → Q appelée fonction de transition ou ensemble des
transitions de A.
- q0 est un état de Q appelé état initial.
- F est un sous-ensemble de Q appelé ensemble des états finaux (ou états marqués) de A.

Un automate fini peut être représenté de deux manières : soit par une table définissant la
fonction de transition soit par un graphe orienté.

Représentation par table de transition

Le nombre de ligne de la table est égale au nombre d’états dans l’automate de telle sorte que
chaque ligne correspond à un état. Les colonnes correspondent aux différents symboles de
l’alphabet. Si l’automate est dans l’état qi et que le symbole a est le prochain à lire, alors l’entrée
(qi, a) de la table donne l’état auquel l’automate passera après avoir lu a. Notons qu’il faut
préciser l’état initial et les états finaux (l’état initial est précédé d’une flèche « → », l’état final
d’une étoile « * »)

Représentation graphique
Un automate fini peut être représente graphiquement comme un graphe orienté dont les
sommets (des cercles) sont les états et les arcs sont les transitions. Une transition δ(qi, a)=qj est
représentée par un arc reliant les sommets qi et qj, étiqueté par a. L’état initial est désigné par
une flèche entrante au sommet correspondant tandis que les états finaux sont marqués par un
double cercle.

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−4
Exemple :

a b
→ q0 q1 q2
q1 q1 q3
*q2 q1 q2
q3 q2 q3

Exemple :
a b
→0 1 0
1 1 2
2 1 3
*3 1 0

Exemple : Distributeur de café

Le café coûte 40 DA et les pièces acceptées sont celles de 10 et 20 DA. Il n’y a pas de retour
de monnaie.
L’alphabet Σ = {10, 20} ; Ensemble des états : Q = {0,1, 2,3, 4} ; Ensemble des états finaux :
F = {4} ; Etat initial : 0.

Remarque : Dans un AFD, les conditions suivantes sont vérifiées :

- ∀qi ∈ Q, ∀a ∈ ∑, il existe au plus un état qj tel que δ(qi, a) = qj. C’est-à-dire, pour chaque
état, il existe au maximum une transition issue de cet état possédant le même symbole.
- L’automate ne comporte pas des ε-transitions (epsilon-transitions)
- Il existe un seul état initial
Remarque : Un AFD ne comportant pas d’états finaux est appelé accepteur : A = (∑, Q, δ, q0).

Automate fini complet – complétion

Un automate fini est complet si δ est défini sur tout Q × ∑, i.e., on peut transiter depuis chaque
état vers un autre état sur tous les symboles de ∑.
Si un automate n’est pas complet, on peut le compléter en lui ajoutant un nouvel état, qui n’est
pas un état final, appelé état puits dans lequel aboutirons toutes les transitions manquantes.
Exemple : Soit l’automate fini incomplet suivant :

On peut construire l’automate fini complet suivant (l’état 3 est l’état puits) :

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−5
Langage reconnu (accepté) par un AFD
Le langage L(A) reconnu par l’automate A est l’ensemble des mots permettant d’atteindre un
) {ω ∈ Σ* | δ ( q0 , ω ) ∈ F }
état final à partir de l’état initial : L ( A=

Exemple : On considère l’automate fini déterministe suivant :

Calcul sur le mot baba : 1 

b
→1  a
→ 2  b
→ 3  → 3 ( accepté ) ce mot est accepté parce
a

que le calcul se termine sur l’état 3 qui est un état final.

Calcul sur le mot bba : 1 
b
→1  b
→1  a
→ 2 ( rejeté ) ce mot n’est pas accepté parce que le
calcul se termine sur l’état 2 qui n’est pas un état final.
Calcul sur le mot abab : 1  a
→ 2  b
→ 3 a
→ 3 ( impasse ) ce mot n’est pas accepté parce
que l’automate se bloque.
Remarque : Si l’automate se bloque pendant la lecture d’un mot ou n’atteint pas l’état final, ce
mot n’est pas reconnu par l’automate

Langage généré par un AFD

Le langage généré par un automate A = (∑, Q, δ, q0) contient tous les mots qui permettent de
passer de l’état initial de l’automate à n’importe quel état :
) {ω ∈ Σ* | δ ( q0 , ω ) ∈ Q} , i.e. δ ( q0 , ω ) est définie.
Lg ( A=
Le langage généré par un automate est toujours préfixe-clos.

Propriété d’un automate fini déterministe

Un automate fini déterministe est :
- Accessible (ou réalisable) si tous ses états sont accessibles. Un état q est accessible s’il
existe un chemin partant de l’état initial qui arrive dans l’état q .
- Co-accessible (ou co-réalisable) si tous ses états sont co-accessibles. Un état q est co-
accessible s’il existe un chemin partant de q et qui arrive dans un état final.
- Non-bloquant si tous ses états sont non bloquants. Un état q est bloquant s’il est
accessible mais pas co-accessible.
- Emondé (utile) s’il est accessible et co-accessible.

Automates finis non déterministes (AFN)

Un automate fini non déterministe (AFN) est définit par un quintuplet A = (∑, Q, δ, I, F) où :
- ∑ est un ensemble fini de symboles appelé alphabet.
- Q est un ensemble fini dont les éléments sont appelés états.
- δ est une relation de Q × (∑ ∪ {ε}) → P(Q) (l’ensemble des parties de Q) appelée fonction
de transition ou ensemble des transitions de A.

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−6
 - I est un sous-ensemble de Q appelé ensemble des états initiaux de A.
- F est un sous-ensemble de Q appelé ensemble des états finaux de A.
Un AFN admet des transitions étiquetées par ε et des états dont plus d’une transition sortante
ont la même étiquette. Un mot w est reconnu par un AFN s’il existe un état final dans δ(q0,w).

Exemple : On considère l’AFN suivant

0 1 ε
→ q1 {q1} {q1, q2} ∅
q2 {q3} ∅ {q3}
q3 ∅ {q4} ∅
*q4 {q4} {q4} ∅

Est-ce que cet automate accepte le mot 011 ?

1 ε
 q2  → q3 (rejeté)
0 1 1
q1  → q1 → q1 → q1 (rejeté)
ε 1
1 q2  → q3  → q4 (accepté)
Le mot 011 est accepté parce que l’un des chemins aboutit à l’état final q4.

Exemple : Soit l’AFN suivant

a b
→ q0 {q0, q1} {q0}
q1 {q2} ∅
*q2 {q2} {q2}

Est ce que cet automate accepte le mot abaa ?

Le mot abaa est accepté parce que l’un des chemins aboutit à l’état final q2.

Remarque : Il est important de comprendre qu’un AFN évalue simultanément tous les chemins
possibles. Si au moins l’un de ces chemins conduit à un état final, l’automate déclare avoir
reconnu le mot.

Langage reconnu (accepté) par un AFN

Le langage L(A) reconnu par un AFN A est l’ensemble des mots permettant d’atteindre un état
) {ω ∈ Σ* | δ ( q0 , ω ) ∩ F ≠ ∅}
final à partir d’un état initial : L ( A=
Remarque :
- Pour tout automate fini A, il existe une expression régulière dénotant le langage L(A).
- Pour toute expression régulière ER, il existe un automate fini qui reconnaît le langage
défini par ER.

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−7
Passage de l’automate fini vers l’expression régulière
Etant donné un automate fini A, on veut construire une expression régulière dénotant le langage
L(A). Le principe est d’exprimer les langages de chaque état q dans un système d’équations
d’inconnues Lq. Pour chaque état, on écrit une équation de la forme :
- Si l’état q n’est pas un état final : Lq = Σ a L p
 a 
 q → p ∈δ
 

- à Lq : Lq
Si l’état q est un état final, alors ε appartient= Σ
 a 
a Lp + ε
 q → p ∈δ
 

On obtient un système de N équations avec N inconnues (N est le nombre d’états de l’automate).

On cherche une expression régulière pour Lq0.
Lemme d’Arden
L’équation récursive suivante : L = X L + M, où L est le langage cherché et X et M sont deux
langages connus, a une unique solution qui est : L = X*M
Exemple :
1) Langage reconnu par cet AFD.
L0 = a L0 + b L1 + ε ;
L1 = a L0 + ( b + c ) L2 ;
L2 b L0 + c L2 ;
=
Ce qui donne :
L2 = c * b L0
( a + (b + c ) c * b) L
L1 = a L0 + ( b + c ) L2 = a L0 + ( b + c ) c * b L0 = 0

L = a L + b ( a + (b + c ) c * b ) L + ε = ( a + b ( a + (b + c ) c * b )) L + ε
0 0 0 0

⇒ L = ( a + b ( a + (b + c ) c * b ))*
0

Alors, le langage reconnu par cet AFD est donné par l’expression régulière :
( a + b ( a + (b + c ) c * b ))*
2) Langage reconnu par cet AFD.
L0 b L0 + a L1 ;
=
L1 a L1 + b L2 ;
=
L2 a L1 + b L3 ;
=
L3 = a L1 + b L0 + ε
Ce qui donne :
L2 = ( a + ba ) L1 + bb L0 + b
L1 =( a + b ( a + ba ) ) L1 + bbb L0 + bb ⇒ L1 =( a + b ( a + ba ) ) * ( bbb L0 + bb )
(
L0 = b L0 + a ( a + b ( a + ba ) ) * ( bbb L0 + bb ) )
( )
=b + a ( a + b ( a + ba ) ) * bbb L0 + a ( a + b ( a + ba ) ) * bb

( )
⇒ L0 =b + a ( a + b ( a + ba ) ) * bbb * a ( a + b ( a + ba ) ) * bb
Alors, le langage reconnu par cet AFD est donné par l’expression régulière :
( b + a ( a + b ( a + ba ) ) * bbb ) * a ( a + b ( a + ba ) ) * bb

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−8
Remarques sur les AFN
- Un mot est accepté par un automate non déterministe s’il existe une dérivation qui
accepte ce mot. Nous laissons l’automate « choisir » la bonne dérivation.
- Si un langage L est accepté par un AFND alors il existe un AFD acceptant L.
- Un langage est régulier ssi il est accepté par un automate fini.
- Le non déterminisme permet de construire facilement des automates utilisant la
disjonction et l’itération, mais ne reconnaît pas plus de langages que les automates
déterministes.
- Les automates finis déterministes et non déterministes reconnaissent la même classe de
langages.
- Ce résultat est à la fois surprenant et pratique.
o Il est surprenant car les automates non déterministes semblent plus puissants que
les automates déterministes.
o Il est pratique car il est souvent plus simple de décrire un langage à l’aide d’un
automate non déterministe.

Passage de l’expression régulière vers l’automate fini

Tout langage défini par une expression régulière est aussi défini par un automate fini.

Algorithme de Glushkov
C’est un algorithme qui permet de construire un automate fini (pas nécessairement déterministe
et sans ε-transitions) à partir d’une expression régulière.
Entrée : une expression régulière : (aba + b)* + a*

Etape 1 : Linéariser l’expression régulière.

On remplace toutes les lettres de l’expression par des symboles distincts ( xi pour la lettre en i-
ème position) : ( x1 x2 x3 + x4 ) + x5* .
*

Etape 2 : Déterminer
- Premier : l’ensemble des symboles pouvant commencer un mot.
- Dernier : l’ensemble des symboles pouvant terminer un mot.
- Suivant : pour tout symbole xi , l’ensemble des symboles pouvant suivre xi .

Etape 3 : Construction de l’AFN

• L’ensemble des états :
- un état initial q0 .
- un état qi par symbole xi .
• L’ensemble des états finaux :
- l’état initial q0 si ε appartient au langage.
- un état qi pour tout xi appartenant à Dernier.
• La fonction de transition :
- une transition de l’état initial q0 vers l’état qi pour tout xi appartenant à Premier et
étiquetée par la lettre correspondant à xi (δ(q0, xi ) = qi si xi ∈ Premier).

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−9
 - une transition de l’état qi vers l’état q j pour tout x j appartenant à Suivant( xi ) et
étiquetée par la lettre correspondant à x j (δ(qi , xj ) = qj , pour
tout xj ∈ Suivant(xi )). suivant
- Puis remplacer les symboles xi par les lettres d’origine de x1 x2
l’expression régulière. x2 x3
x3 x1 , x4
Remarque : L’automate obtenu est souvent non déterministe.
Exemple : x4 x1 , x4
Construction un AFN qui reconnait le langage : (aba + b)* + a* x5 x5
Linéarisation de l’expression régulière : ( x1 x2 x3 + x4 ) + x5*
*

Premier = { x1 , x4 , x5 }
Dernier = { x3 , x4 , x5 }
Ensemble des états de l’automate fini
Q = {q0 , q1 , q2 , q3 , q4 , q5 }
Etat initial : q0
Etats finals : {q0 , q3 , q4 , q5 }
(ε appartient au langage ⇒ l’état initial est un état final).

Déterminisation d’un automate

Théorème : pour tout automate fini non déterministe, il existe un automate fini déterministe
équivalent (« équivalent » signifie qu’il reconnaît le même langage).
Procédure de déterminisation :
- Etape 1 : calculer l’ε-fermeture (clôture, étoile) de chaque état.
L’ε-fermeture d’un état q est l’ensemble des états qui peuvent être atteints à partir
de q en ne faisant que des ε-transitions, auquel on ajoute q lui-même.
- Etape 2 : Créer la table de transition du nouvel automate comme suit
1. Commencer par l’ε-fermeture de l’état initial (ou par l’union des ε-fermetures
des états initiaux en cas de plusieurs états initiaux). Ce sera l’état initial du
nouvel automate.
2. Pour chaque lettre, ajouter dans la table les états produits, avec leurs ε-
fermetures. Chacun de ces ensembles d’états devient un état dans le nouvel
automate.
3. Recommencer 2 à partir de chaque nouvel état produit, jusqu’à ce qu’on ne crée
plus de nouvel état.
4. Tous les états contenant au moins un état final deviennent finaux.
5. Pour plus de clarté, renommer éventuellement les états.
Exemple : Déterminiser l’AFN suivant :

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−10
Dans cet automate, on n’a pas de ε-transitions, alors l’ε-fermeture de chaque est l’état lui-
même.
La table de transition de l’automate fini déterministe résultant est :
a b a b
→0 {0, 1} {2} → q0 q1 q2
Après renommage des états,
*{0, 1} {0,1,3} {2} * q1 q3 q2
*{2} {1} {2} on obtient : * q2 q4 q2
*{0,1,3} {0,1,3} {2,3} * q3 q3 q5
*{1} {1,3} {2} *q4 q6 q2
*{2,3} {1,3} {2,3} * q5 q6 q5
*{1,3} {1,3} {2,3} *q6 q6 q5

Exemple : Construire un AFD équivalent à l’AFN suivant.

Calcul de l’ε-fermeture (clôture, étoile) de chaque état

état ε-fermeture
q0 {q0}
q1 {q1, q3}
q2 {q1, q2, q3}
q3 {q3}
q4 {q1, q2, q3, q4}
q5 {q5}

Table de transition de l’automate fini déterministe

état a b a b
→ q0 {q1, q2, q3} {q1, q3} → s0 s1 s2
{q1, q2, q3} {q1, q2, q3, q4, q5} ∅ s1 s3 ∅
{q1, q3} {q1, q2, q3, q4, q5} ∅ s2 s3 ∅
* {q1, q2, q3, q4, q5} {q1, q2, q3, q4, q5} {q5} * s3 s3 s4
* q5 ∅ ∅ * s4 ∅ ∅

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−11
Minimisation d’un AFD
La minimisation d’un automate fini déterministe (AFD) vise à transformer un AFD donné en
un AFD équivalent comportant le nombre minimal d’états, tout en reconnaissant le même
langage régulier.

Théorème de Myhill-Nérode : Soit L un langage régulier. Parmi tous les AFD reconnaissant
L, il en existe un et un seul qui a un nombre minimal d’états.

En partant de n’importe quel AFD complet, une façon élémentaire pour obtenir l’automate
minimal équivalent est :
- de supprimer les états inaccessibles à partir de l’état initial (et de compléter
l’automate).
- d’identifier les états équivalents (indistinguables).
- Construire l’automate minimal en regroupant ensemble les états dans chaque classe
d’équivalence.

Définition. Deux états q1 et q2 sont équivalents (indistinguables) si aucun mot ne les sépare :
q1 ~ q2 ssi pour tout mot u, on a : δ(q1, u) ∈ F implique δ(q2, u) ∈ F et réciproquement.

Procédure de minimisation

Etape 1 : Supprimer les états inaccessibles à partir de l’état initial (et de compléter l’automate).

Etape 2 : Identifier les états équivalents (indistinguables).

- On commence avec un tableau de taille N × N (N est le nombre d’états de notre
automate). Chaque case dans ce tableau correspond à un couple d’états ( p, q ) . Pour ne
pas avoir deux fois le même couple ( p, q ) et ( q, p ) ni les couples inutiles ( p, p ) , on
supprime alors ces cases (on obtient un tableau de taille (N-1) × (N-1)). Notre but final
est de marquer toutes les cases ( p, q ) pour des états p et q non-équivalents ou
distinguables.
- Au départ, les paires ( p ∈ F , q ∉ F ) , i.e. ( p état final, q état non final), sont marquées
par D.
- Pour chaque case ( p, q ) et lettre a , on calcule δ ( p, a ) = p′ et δ ( q, a ) = q′ . On
marque ( p, q ) si et seulement si la case ( p′, q′ ) est déjà marquée.
- On itère jusqu’à ce que le tableau ne se modifie pas.

Etape 3 : Construire l’automate fini minimal (réduit)

- On détermine d’abord les classes d’équivalence. Pour chaque état q , la classe
d’équivalence de q se compose de tous les états p pour lesquels la paire ( p, q ) n’est

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−12
 pas marquée à l’étape 2 (dans le tableau). Les états de l’automate minimal sont les
classes d’équivalence. L’état initial est la classe d’équivalence qui contient q0 . Les états
finaux de l’automate minimal sont les classes d’équivalence qui se composent des états
finaux de l’automate à minimiser. La fonction de transition est définie comme suit :
Pour déterminer δ ′ ( X , a ) , pour une classe d’équivalence X , choisissez n’importe quel
q ∈ X et déterminer δ ′ ( X , a ) = Y , où Y est la classe d’équivalence qui contient
δ ( q, a ) .
- Supprimer tous les états non accessibles et tous les états non co-accessibles. Toutes les
transitions vers ces états depuis d’autres états deviennent indéfinies.

Exemple : Minimiser l’AFD suivant

En premier lieu, on supprime l’état q3 parce que cet état n’est pas accessible à partir de l’état
initial. Ensuite, on construit la table d’équivalence (sans q3)
q1
q2 D D
q4 D D D
. q5 D D D D
q6 D D D D
q7 D D D D D D
q0 q1 q2 q4 q5 q6
On regroupe les états dans des classes d’équivalence. A partir du tableau, q0 et q1 sont
équivalents, et q5 et q6 sont équivalents. Alors, les classes d’équivalences sont : {q0, q1}, {q2},
{q4}, {q5, q6}, et la table de transitions de l’automate minimale est la suivante :

a b
→ q0q1 q7 q0q1
q2 q4 q5q6
q4 q5q6 q5q6
* q5q6 q5q6 q5q6
q7 q2 q2

Exemple : Minimiser l’AFD suivant

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−13
En premier lieu, Il n’y a pas d’état inaccessible. On construit alors la table d’équivalence.
q1
q2 D D
q3 D D
q4 D D
q5 D D D D D
q0 q1 q2 q3 q4

On regroupe les états dans des classes d’équivalence. A partir du tableau, q0 et q1 sont
équivalents, et q2 , q3 et q4 sont équivalents. Alors, les classes d’équivalences sont : q01={q0,
q1}, q234={q2, q3, q4} et {q5}. La table de transitions de l’automate résultant est la suivante :

0 1
→ q01 q01 q234
q234 q234 q5
q5 q5 q5
Le graphe de l’automate obtenu est :
On remarque que l’état q5 n’est pas co-accessible, alors on supprime cet état, et l’automate
minimal devient :

Opérations sur les automates (les langages)

On considère des automates finis déterministes.

Complément
Soit un automate déterministe A reconnaissant le langage L . L’automate complémentaire
reconnaissant le langage inverse (c’est-à-dire LC ou Σ∗-L) peut être obtenu comme suit :
− Compléter l’automate A s’il n’est pas complet.
− L’automate complémentaire peut être obtenu en transformant les états non finaux à des
états finaux et vice-versa.

Exemple :

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−14
Concaténation
Soit les deux automates déterministes A1 = ( Σ1 , Q1 , δ1 , q10 , F1 ) et A2 = ( Σ 2 , Q2 , δ 2 , q20 , F2 )
reconnaissant les langages L1 et L2 . Pour construire l’automate A qui reconnaît le langage
L = L1.L2 , on peut procéder de la manière suivante:
− L’ensemble des états du nouveau automate A est Q = Q1 ∪ Q2 .
− L’état initial de l’automate A est l’état initial du premier automate A1 .
− Les états finaux de l’automate A sont les états finaux du deuxième automate A2 .
− Chaque transition des deux automates A1 et A2 est une transition dans l’automate A .
− On ajoute de nouvelles ε-transitions entre chaque état final de A1 (qui n’est plus final
dans le nouvel automate A ) et l’état initial de A2 .

Union (Somme des automates)

Soit les deux automates déterministes A1 = ( Σ1 , Q1 , δ1 , q10 , F1 ) et A2 = ( Σ 2 , Q2 , δ 2 , q20 , F2 )
reconnaissant les langages L1 et L2 . L’union de deux langages permet de construire un langage
dont les mots sont issus soit d’un mot du premier langage soit d’un mot du second langage.
L’automate fini reconnaissant le langage L= L1 ∪ L2 peut être construit comme suit :
− L’état de départ est l’état composé du couple des deux états initiaux (l’état initial du
nouvel automate).
− Pour chaque état créé ( p, q ) et pour chaque lettre a de l’alphabet Σ = Σ1 ∪ Σ 2 , ajouter
dans la table de transition les états produits calculés de la manière suivante :
δ ( ( p, q ) , a ) = ( p′, q′ ) , avec
δ ( p, a ) , si δ1 ( p, a ) est définie
p′ =  1
∅, sinon
δ ( q, a ) , si δ 2 ( p, a ) est définie
q′ =  2
∅, sinon
− Chacun des nouveaux états produits devient un état dans le nouvel automate.
− Recommencer les deux étapes précédentes à partir de chaque nouvel état produit,
jusqu’à ce qu’on ne crée plus de nouvel état.
− Tous les états contenant au moins un état final de A1 ou de A2 deviennent finaux.
− Pour plus de clarté, renommer éventuellement les états.

Intersection (Produit des automates)

Soit les deux automates déterministes A1 = ( Σ1 , Q1 , δ1 , q10 , F1 ) et A2 = ( Σ 2 , Q2 , δ 2 , q20 , F2 )
reconnaissant les langages L1 et L2 . L’automate fini reconnaissant le langage L= L1 ∩ L2 peut
être construit comme suit :

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−15
 − L’état de départ est l’état composé du couple des deux états initiaux (l’état initial du
nouvel automate).
− Pour chaque état créé ( p, q ) et pour chaque lettre a de l’alphabet Σ = Σ1 ∩ Σ 2 , ajouter
dans la table de transition les états produits calculés de la manière suivante :
=δ ( ( p, q ) , a ) ( p′, q′ )=
, si δ1 ( p, a ) p=
′ et δ 2 ( q, a ) q′
− Chacun des nouveaux états produits devient un état dans le nouvel automate.
− Recommencer les deux étapes précédentes à partir de chaque nouvel état produit,
jusqu’à ce qu’on ne crée plus de nouvel état.
− Chaque nouvel état composé d’un état final de A1 et d’un autre état final de A2 devient
état final dans le nouvel automate.
− Pour plus de clarté, renommer éventuellement les états.

Exemple : Soit A1 l’automate de gauche et A2 l’automate de droite. Soient L1 et L2 leurs

langages respectifs

− Construire l’automate reconnaissant le langage L1.L2 .

− Construire l’automate reconnaissant le langage L1 ∪ L2 .
− Construire l’automate reconnaissant le langage L1 ∩ L2 .

o Automate pour le langage L1.L2

o Automate reconnaissant le langage L1 + L2

a b
→ q04 → (q0,q4) (q1,q4) q5
q14 (q1,q4) (q2,q4) q5
q5 q5 q6 q5
q24 (q2,q4) (q3,q4) (q2,q5)
*q6 *q6 q6 q6
*q34 *(q3,q4) (q3,q4) (q2,q5)
q25 (q2,q5) (q3,q6) (q2,q5)
*q36 *(q3,q6) (q3,q6) (q2,q6)
*q26 *(q2,q6) (q3,q6) (q2,q6)

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−16
 o Automate reconnaissant le langage L1 ∩ L2

a b
→ q04 → (q0,q4) (q1,q4) -
q14 (q1,q4) (q2,q4) -
q24 (q2,q4) (q3,q4) (q2,q5)
q34 (q3,q4) (q3,q4) (q2,q5)
q25 (q2,q5) (q3,q6) (q2,q5)
*q36 *(q3,q6) (q3,q6) (q2,q6)
q26 (q2,q6) (q3,q6) (q2,q6)

Composition d’automates
L’opération de composition des automates permet l’obtention du modèle global d’un système
à partir des modèles de ses sous-systèmes. On peut distinguer deux sortes de compositions :
− Composition synchrone, qui est effectuée quand les alphabets associés aux automates
considérés ont au moins un événement en commun.
− Composition asynchrone, qui est réalisée quand les alphabets associés aux automates
considérés n’ont aucun événement en commun.
Soient deux automates A1 = ( Σ1 , Q1 , δ1 , q10 , F1 ) et A2 = ( Σ 2 , Q2 , δ 2 , q20 , F2 ) . La composition
entre A1 et A2 est l’automate A = A1  A2 = ( Σ, Q, δ , q0 , F ) , où :
– Q= Q1 × Q2 est l’ensemble d’états,
– Σ = Σ1 ∪ Σ 2 est l’alphabet,
– q0 = ( q10 , q20 ) est l’état initial,
– F= F1 × F2 est l’ensemble des états finaux,
– δ est une relation de Q × Σ qui définit la fonction de transition d’état. Elle associe à
chaque état ( p, q ) et à tout événement σ ∈ Σ un état calculé de la façon suivante :
 Pour σ ∉ Σ1 ∩ Σ 2

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−17
 δ ( ( p, q ) , σ ) = ( p′, q ) si σ ∈ Σ1 et δ1 ( p, σ ) = p′ ,
δ ( ( p, q ) , σ ) = ( p, q′ ) si σ ∈ Σ 2 et δ 2 ( q, σ ) = q′ ,
 Pour σ ∈ Σ1 ∩ Σ 2 :
δ ( ( p, q ) , σ ) = ( p′, q′ ) si δ1 ( p, σ ) = p′ et δ 2 ( q, σ ) = q′

Remarque : Si un événement σ ∈ Σ1 ∩ Σ 2 , il doit se produire de manière synchrone dans les

deux automates. Par contre, s’il n’appartient qu’à un ensemble, il se produit de manière
asynchrone.
Exemple : Considérons deux automates pour modéliser le fonctionnement d’un distributeur de
jetons. On a Σ1 ={ p, j} et Σ 2 ={b, j}
Pour A1 , on suppose que le symbole p modélise l’événement « introduction d’une pièce » dans
la machine et que j modélise l’événement « libération d’un jeton ». Pour A2 , le symbole b
modélise l’événement « pression d’un bouton » et le symbole j a la même signification que
dans A1 .

A1 : A2 :

p b j
→ *(q0,s0) (q1,s0) (q0,s1) -
(q1,s0) - (q1,s1) -
(q0,s1) (q1,s1) - -
(q1,s1) - - (q0,s0)

M2 – AII – Cours SED – Département d’Automatique – FST – Université MSBY – Jijel 2−18