1

Automates finis
Automates finis non déterministe
Propriétés des langages acceptés par un automate fini
Automate déterministe minimal
Automates finis et langages réguliers
Transformation d’un DFA en ER
Lemme de pompage

Chap2 : Automates finis

 Chapitre 2 2
Automates finis

Les automates à états finis sont utilisés comme modèle

pour :

• Conception des circuits logiques

• Analyse lexicale de compilateurs
• La recherche de mots clés dans le Web.
• …….

Chap2 : Automates finis

 Exemples 3

• Automate fini modélisant un système de On/Off

Push

début Off On

Push

• Automate fini reconnaissant la chaîne then

début t h e n
t th the then

Chap2 : Automates finis

 Motivation 4

Problème: est ce qu’une chaîne w appartient à un langage

L?
Quels sont les ressources nécessaires pour répondre
à cette question.
Reconnaisseur d’un langage
Programme qui prend en entrée une chaîne x et répond
par oui ou non. (x appartient ou non au langage)

On peut résonner pour les problèmes non pas comme

une réponse Oui /non mais comme transformation des
entrées en des sorties.

Chap2 : Automates finis

 5
Automate à états finis déterministe
définition formelle

• Ensemble fini d’états Q

• Alphabet de symboles d’entrées 
• Un état initial (un élement de Q) q0
• Zéro ou plus d’états d’accepatation ou finaux (sous F
ensemble de Q)
• Une fonction de transition 

Chap2 : Automates finis

 6
Automate à états finis déterministe
définition formelle

Une fonction de transition 

• Arguments : état et un symbole d’entrée
• Retourne un état

 : Q   Q
 
 q ,a q
i j

• Intuitivement; si un automate fini AF est dans

un état qi et reçoit l’entrée a (reconnaît), alors
l’AF passe à l’état qj

Chap2 : Automates finis

 7
Automate à états finis déterministe
définition formelle

Un Automate à états Finis Déterministe (DFA)

M  Q, ,  , q0 , F 

Chap2 : Automates finis

 Alphabet d’entrées 8


  a, b

a, b
Diagramme de
transition
q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4

Chap2 : Automates finis

 Ensemble d’entrées 9

Q
Q  q0 , q1, q2 , q3 , q4 , q5 

a, b

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

Chap2 : Automates finis

 État initial 10
q0

a, b

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

Chap2 : Automates finis

 Ensemble d’états finaux 11

F  q4 

a, b

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

Chap2 : Automates finis

 Fonction de transition 12


 a b
q0 q1 q5
q1 q5 q2
Mécanisme de calcul
q2 q5 q3 sans mémoire
q3 q4 q5 a, b
q4 q5 q5
q5 q5 q5 q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4
Chap2 : Automates finis
 Mot accepté par un automate 13

Un automate Fini accepte une chaîne w = a1a2…an S’il

existe un chemin dans le diagramme de transition qui :
1. Commence à l’état initial.
2. Finie à un états d’acceptation (ou final)
3. Possède la séquence libellé par a1a2…an
a, b

Exemple
q5
abbbaa
b a a, b
a b
q0 a q1 b q2 b q3 a q4
Chap2 : Automates finis
 Extension de la fonction de 14
transition

 *  q, w q
Elle nous dit dans quel état on arrive en partant de l’état qi
et en analysant la chaîne w

 * : Q *  Q

q w q
w  1 2  k
1 2 k
q q
Chap2 : Automates finis
 Extension de la fonction de 15
transition

Exemple : Il y a un chemin de q0 à q5
libellé abbbaa

 *  q0 , abbbaa  q5
a, b

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

Chap2 : Automates finis

 Définition récursive 16

Base :  * q,  q

Induction :  * q, w    (  * (q, w),  )

q w q1  q

Une chaîne w est accepté par l’automate M dont l’état

initial est q0 si  * q0, w appartient aux états
finaux de M

Chap2 : Automates finis

 Langage accepté 17

Considérons DFA M

Définition:
Le langage L(M)contient toutes les chaînes acceptés par
M

L(M) = { toutes les chaînes menant l’automate M vers un

état final}

M  Q, ,  , q0 , F 

L M   w  * :  *  q0 , w  F 
Chap2 : Automates finis
 Langage rejeté par M 18

L M   w  * :  *  q0 , w  F 

q0 w q q F

Chap2 : Automates finis

 Exemples 19

n
L M  {a b : n 0}

a a, b

q0 b q1 a, b q2

accepté État mort

Chap2 : Automates finis

 Exemples 20

L M  = { toutes les chaînes avec prefixe ab }

a, b

q0 a q1 b q2

b a accepté

q3 a, b
Chap2 : Automates finis
 Exemples 21

L  M  = { toutes les chaînes sauf celles qui

contiennent par 001 }

1 0 0,1
1
0 1
 0 00 001

0
Chap2 : Automates finis
 Exemples 22

L  M  = {w contient un nombre pair de b}

a a

q0 q1

b
q0 : Est à la fois état initial et final

Chap2 : Automates finis

 Exemples 23

• Tout les mots sur l’alphabet {a,b}

* a,b

q0

Chap2 : Automates finis

 Exemples 24

L = {w {a,b}* | w contient un nombre pair de a et

un nombre pair de b}

L = {w {0,1,2,3,4,5,6,7,8,9}* | somme des chiffres

est divisible par 3}

L = {w {a,b}* | | w |b =3k+1;k>=0}

Chap2 : Automates finis

 Configuration 25

Configuration initiale : 0(q0,w)

Configuration finale d’acceptation :  f (q f ,) q f F

Configuration finale de non acceptation :  f (q f ,) q f F

Configuration Successeur après n transition

n '
Q* M
ssi ' pour n=0
n-1 ' pour n0
"/  " et "

*
Notation : Fermeture réflexive et transitive
M
Chap2 : Automates finis
 Configuration 26

L M  w*/(q0,w) * (q f ,),q f F

M

Exemple : M Q,,,q0,F   a b

 a,b q0 q0 q1

q1 q1 q0
Q q0,q1

F q0

• (q0,ababa)
• (q0,aba)

Chap2 : Automates finis

 Automates finis complets 27

• Un automate fini déterministe est complet si  et une

fonction totale sur Q

• De chaque état il part exactement une flèche

étiqueté par chacune des lettres de l’alphabets 

Exemple
1 0,1

0 0,1
q0 q1 q2

Chap2 : Automates finis

 Erreurs 28

• Ne pas confondre un automate M avec L(M). En fait M

est un programme et L(M) est un ensemble de chaînes.

• L’état initial q0 est de type état tan disque F est de

type ensemble d’états (représente l’ensemble des états
finaux)
• Est ce que a est un symbole ou une chaîne de longueur 1.
• Ca dépend du contexte par exemple si a est utilisé
comme entrée de la fonction  ou *

Chap2 : Automates finis

 Chapitre 2 29
Automates finis non déterministe NFA

Alphabet = {a}

q1 a q2
a
q0
a
q3

Chap2 : Automates finis

 Automates 30
finis non déterministe
Premier choix

a a
Tous les entrées sont consommées
q1 a q2 “accepté”
a
q0
a
q3

Chap2 : Automates finis

 Automates 31
finis non déterministe
Deuxième choix

a a

q1 a q2
a
q0
a
Pas de transition:
q3
L’automate se bloque
Rejet
Chap2 : Automates finis
 32
Acceptation par un NFA

un NFA accepte une chaîne:

Lorsqu’il existe un calcul dans le NFA

Qui accepte la chaîne

ET
Toutes les entrées sont consommées et
l’automate est dans un état d’acceptation

Chap2 : Automates finis

 Non acceptation par un 33
NFA

Un NFA rejète une chaîne:

Lorsqu’il n’ya aucun calcul dans l’NFA qui
accepte la chaîne:

• Toutes les entrées sont consommées

et l’automate n’est pas dans un état
d’acceptation
OU
• L’entrée ne peut pas être consommée
Chap2 : Automates finis
 Transition étiqueté par  34

a a

q0 a q1 
q2 a q3

(La lecture ne bouge pas)

a a

q0 a q1 
q2 a q3
Chap2 : Automates finis
 Transition étiqueté par  35

NFA M1 DFA M2 a
q2
q0 a q1
a
q0 a q1

L( M1 ) = {a} L( M 2 ) = {a}
Chap2 : Automates finis
 36
Automates fini non déterministe
Définition formelle

M  Q, ,  , q0 , F 

Q: Ensembles d’états,  q0 , q1, q2 

: Alphabet d’entrées,  a, b
: Relation de transition

q0 : Etat initial

F: Ensembles d’états finaux

Chap2 : Automates finis
 Exemples 37

(q1,0){q0,q2}

0
q0 q1 0, 1 q
2
1


(q0,){q0,q2}

Chap2 : Automates finis

 Extention de la relation 38
de transition

 *  q0 , ab   q2 , q3 , q0 

q4 q5
a a
q0 a q1 b q2 
q3


Chap2 : Automates finis

 Extension de la relation 39
de transition

w L M   * (q0 , w)
qi
w
qk qk  F
q0 w
w qj

Chap2 : Automates finis

 40
Exemple

Language((a b)*abb)

q0 a q1 b q2 b q3

Chap2 : Automates finis

 41
Équivalence de machines

La machine M1 est équivalente à la machine M2 si

L(M1)=L(M2)

Théorème : Pour chaque automate fini non déterministe

correspond un automate fini déterministe qui lui est
équivalent.

Chap2 : Automates finis

 Preuve 42

Algorithme de transformation d’un NFA A en un DFA B

• AQ,,,q0,F 
• BQ',,,'q'0,F'

E(q)= {pQ | (q,) * (p,)}

A
Q
Q'2 Puissance de l’ensembles (ensemble des parties de Q)

q'0 E(q0) : -fermeture de q0

F' q': q'F 

Chap2 : Automates finis

 Preuve 43

Algorithme de transformation d’un NFA A en un DFA B

• AQ,,,q0,F 
• BQ',,,'q'0,F'

E(q)= {pQ | (q,) * (p,)}

A
Q
Q'2 Puissance de l’ensembles (ensemble des parties de Q)
La construction de Q’ est on-line un sous ensemble de 2Q

q'0 E(q0) : -fermeture de q0

F' K Q: QF 

Chap2 : Automates finis

 Preuve 44

Construction ’ pour tout  faire :

'(K,) E(p) : pQ;qK,(q,)p

'(K,) Possible

M a
NFA
q0 a q1 
q2
b

Chap2 : Automates finis

 Preuve 45

Construction ’ pour tout  faire :

'(K,) E(p) : pQ;qK,(q,)p

'(K,) Possible

M a
NFA
q0 a q1 
q2
b

Chap2 : Automates finis

 Preuve 46

M a
NFA
q0 a q1 
q2 q1  F
b
a
DFA M b

 q0  a
 q1, q2 
b  q1, q2   F 
 a, b
Chap2 : Automates finis
 Exemple 47

a
q2 q3
 
a b
q0 
q1 q6

q7 q8 b
q9 q10
b
 q4 q5 

Construire le DFA équivalent

Chap2 : Automates finis

 Exemple 48

• A = {q0,q1,q2,q4,q7} ' a b
• B = {q1,q2,q3,q4,q6 ,q7,q8} A B C
• C = {q1,q2,q4,q5 ,q6,q7} B B D
• D = {q1,q2,q4,q5,q6 ,q7,q9} C B C
• E = {q1,q2,q4,q5,q6 ,q7,q10} D B E

E B C

'(A,a)E(q3)E(q8)
'(A,a) q1,q2,q3,q4,q6 ,q7 , q8

Chap2 : Automates finis

 Chapitre 2 49
Propriétés des langages acceptés par
un automate fini
La classe des langage acceptés par un automate fini est
fermé par :
• Union;
•Concaténation;
•Kleen star;
•Complémentation;
•Intersection.

Dans chaque cas, on montrera comment construire

l’automate qui accepte le langage approprié

Chap2 : Automates finis

 Union 50

M1Q1,,1,q01,F1 L1 langage accepté par M1

M 2Q2,,2,q02,F2 L2 langage accepté par M2

Soit M le NFA qui accepte L(M1)L(M2)

M Q,,,q0,F 
QQ1Q2 q0
F F1F2
 12 (q0,,q01),(q0,,q02)

Chap2 : Automates finis

 Union 51
M1 M2
q01 q02

F1 F2

M
q0
q01   q02

Chap2 : Automates finis

 Concaténation 52

M1Q1,,1,q01,F1 L1 langage accepté par M1

M 2Q2,,2,q02,F2 L2 langage accepté par M2

Soit M le NFA qui accepte L(M1).L(M2)

M Q,,,q01,F 
QQ1Q2
FF2
 12 F1  F2{q
 02}

Chap2 : Automates finis

 Kleen star 53

M1Q1,,1,q01,F1 L1 langage accepté par M1

Soit M le NFA qui accepte L(M1)*

M Q,,,q0,F 
QQ1 q0
F F1 q0
 1 F   q01 

Chap2 : Automates finis

 Complémentation 54

M Q,,,q0,F  L langage accepté par M1

Soit M’ le NFA qui accepte *-L(M1)

M'Q,,,q0,Q F 

Construction directe pour L(M1)L(M2) ?

Chap2 : Automates finis

 Chapitre 2 55
Automate déterministe minimal

Définition (séparation)
Soit (q1,q2) Q2 : on dit que q1,q2 sont séparé par w  * si
*(q1,w) F ou bien *(q2,w) F mais pas les deux en même
temps.
Définition
q1,q2 sont inséparables si aucun mot de * ne les sépare
*(q1,w) F ssi *(q2,w) F
Définition (équivalence de nerode)
q1 est équivalent à q2 si q1,q2 sont inséparables (noté q1q2)

Chap2 : Automates finis

 Chapitre 2 56
Automate déterministe minimal

Définition (langage associé à un état)

Soit un DFA A=(,Q,,q0,F), on appelle langage associé à q et on
note Lq(A), le langage suivant :
Lq(A)={w* : *(q,w) F}

L(A)=Lq0(A)

Chap2 : Automates finis

 Chapitre 2 57
Automate déterministe minimal

Problème :
Soit A un automate fini déterministe complet dont chaque état
accessible depuis l’état initial. Construire un DFA minimal qui
reconnaisse le même langage que A.
Idée : fusionner les états équivalents

Chap2 : Automates finis

 Chapitre 2 58
Automate déterministe minimal

Définition (équivalence d’état) :

• Etant donné A un DFA, deux états p et q (noté pq)sont
équivalent si Lp(A)=Lq(A).
• Ainsi (pq)  (pour tout mot w*)

 *(p,w)F et  *(p,w)F

 ou
 *(p,w)F et  *(p,w)F

Notation : si q est un état, on note [q] sa classe d’équivalence.

L’ensemble des états qui lui sont équivalents.
Chap2 : Automates finis
 Chapitre 2 59
Automate déterministe minimal

Définition
Soit le DFA A=(,Q,,q0,F), l’automate minimal associé à A est
Amin =(,Q’,’,[q0],F’)
• Q’={[q] : qQ}
• F’ ={[f] : fF}
• ’ ={([p],a,[q]) tels que  p’ [p] et q’[q] et (p’,a,q’)}

Chap2 : Automates finis

 Chapitre 2 60
Automate déterministe minimal

Propriété
• Amin reconnaît le même langage que A.
• Pour tout DFA B tel que L(B)=L(A), le nombre d’états de B est
supérieur ou égal à celui de A.
• Bmin est le meme que Amin, On peut parler d’unicité à un
renommage près.

Chap2 : Automates finis

 Chapitre 2 61
Automate déterministe minimal

Algorithme de minimisation
• Itération i = 0 (construire deux classes d’équivalence : les états
d’acceptation F et les états de non acceptation Q-F).
p 0 q (pF, qF) ou (pF, q  F)
• Itération i >0
p i q si :

• p i-1 q Et
• pour tout a   : (p,a) i-1 (q,a)
Arrêt de l’algorithme quand i est identique à i-1
Supprimer tous les états morts et ceux non accessible depuis l’état
de :départ
Chap2 Automates finis
 Chapitre 2 62
Transformation d’un DFA en ER

Théorème :
Un langage est régulier si et seulement si il est accepté par un
automate fini
Preuve :
if : Soit M Q,,,q0,F  un automate, on doit trouver un
langage régulier R tel que R =L(M).

On représente L(M) comme l’union « fini »

de plusieurs langages simples

Chap2 : Automates finis

 Chapitre 2 63
Transformation d’un DFA en ER

M  Q, ,  , q0 , F 

Langage régulier R : R=L(M).

R : Union d’un nombre fini de simples langages.
Système d’équations associé à un automate :
qi  Q, Li  aL j  Bi  (qi , a ) q j , Bi  si qi  F .
a

Chap2 : Automates finis

 64
Exemple

Construction d’une expression régulière pour le langage accepté par le DFA suivant.

b
2 4
a
c a
1

b
c
a 5
3

Chap2 : Automates finis

 65

 L1 aL 2  bL 3
 L bL  cL
 2 4 5

 L 3 aL5
 L aL  
 4 5

 L 5 cL5  

Solution du système L1 associé a l’état initial de M

Chap2 : Automates finis

 66

Théorème:
Soit (L1,L2,….Ln) un système d’équations associé a un automate M. Ce système admet une
solution unique et L(M)=L1

Lemme d’arden
Soient A, B   * tq   B alors l’équation L=ABL admet une solution
unique : L=B*A
Et L=ALB admet une solution unique : L=AB*.
Preuve:
B*A solution,
L= A BL , B*A= A BB*A= A B+A=(εB+)A= B*A

B*AL, inclus dans toute solution. L= A BL AL,

BL L
BA BL L, par récurrence, BiA BL L i,
B*AL,

Chap2 : Automates finis

 67

B*A Solution unique:

Lemme ( Claim)
Si KBK, K,B * , εB alors K= .

Preuve

K  BK 

BK  B2 K   K  B n K n  0
Bn -1K  Bn K 
Soit u K avec |u|=p, u K alors u Bp+1K , donc  w1, w2, tq u=w1w2 avec w1Bp+1.
w2 K, donc |w1|p+1 car εB. Contradiction avec |u|=p.

Chap2 : Automates finis

 68

Soit L une solution.

Posons L=B*AK, avec B*AK=. L=ABL
B*A K = A B(B*AK)
= A B+A BK
= (εB+)A BK

B*A K =B*A BK

K BK
εB  K = ,

Donc L=B*A

Chap2 : Automates finis

 69
Exemple
b

b 2

c
c
3

 L1 aL1  bL2  cL3


 L2 bL2  aL1
 L cL  
 3 3

Chap2 : Automates finis

 70
Exemple (suite)

D’après l’équation 3 on obtient:

L3=c*

L2=b*aL1

L1=aL1+b+aL1+cc*
= b*aL1+c+
L1=(b*a)*c+

Chap2 : Automates finis

 71
Théorème de Pumping

On l’utilise pour prouver qu’un langage n’est pas régulier .

Soit L un langage régulier infini, pour chaque w  L avec |w| |Q|

alors  x,u,y * avec u ε tels que

w=xuy (1)
|xu|  |Q| (2)
|u|  0 (3)
xuny L  n 0. (4)

Chap2 : Automates finis

 72
Preuve

w L, |w|  n, w = xuy tel que 1. uε 2. |xu| n 3. xuiy  L

Soit le DFA ayant m états. Soit |w| > m. Considérons le chemin de l’état initial à
l’état final. L’exécution de l’automate sur w doit passer par un même état au moins
deux fois avec une partie non vide du mot séparant ces deux passages.

On peut écrire w=opqr, avec p correspond à une boucle , et |opq| = m (le préfixe de taille
m). Soit x=o, u = p, et y = qr.

1) Chaque boucle possède au moins un arc, |p| >0, uε

2) |xu| m car xu = op et |opq| = m

3) xuiy  L car si p est une boucle elle commence de l’état si et (si,p) = si, et (si,qr)
= sfinal.. (sstart,x) = si, et pour tout i (si,ui) = si c.q.f.d.

Chap2 : Automates finis

 73

u = q

x = p y = rs
start qi final
r | s

m étapes

Chap2 : Automates finis

 74

Preuve de non régularité

Pour prouver qu’un langage est non régulier on utilise le

théorème de pumping comme suit:

On suppose que L est régulier ( raisonnement par l’absurde ),

soit wL tel que |w|n.

w=xuy, une décomposition de w en 3 sous chaînes, on suppose

que u ε et |xu|  n.

On doit démontrer que pour un certain i le mot xuiy

n’appartient pas à L.

Chap2 : Automates finis

 75

Exemple
Soit L={anbn | n0 }, L est non régulier.

Il n’existe pas x, u, y tels que xuky  L  k.

Supposons qu’il existe x,u,y.

3 cas sont possibles.
1er cas. u dans an. On suppose que u=ap, x=ar et y=asbt avec p+r+s=t
w= arap+sbt, d’après le théorème, aranp+sbt L  n. contradiction r+np+st.

2ème cas. u dans bn symétrique.

3ème cas. u=apbm , un=(apbm)n . xuny= ak-p (apbm)nbk-m L.

Il n’existe pas x,u,y avec uε, tel que xuny  L donc L n’est pas régulier.

De même on peut montrer que les langages suivants ne sont pas reguliers.
L={w {0,1}* | w contient le même nombre de 0s et de 1s}
L={ w {a,b,c}* | |w|= k2}
L = { uu | u{a,b}* }

Chap2 : Automates finis