Théorie des Langages et Compilation

Cours 4 : Les Automates à Etat Finis

(AEF)
 Plan du cours

II. Automates Finis

III. Déterminisation
IV. Minimisation
V. Automate vs Expressions Régulière

2
 Introduction

Objectif : Définir formellement (modéliser) un mécanisme qui peut

prendre une décision.

Quel type de décision ?

entrée : une séquence de symboles
sortie (réponse) : ”oui” ou ”non” (acceptation ou rejet)

3
 Introduction

Les automates sont des modèles mathématiques qui permettent de

déterminer si un mot donné appartient à un langage.

Classification des automates:

Comme les langages et les grammaires il y a quatre types d’automates:

• Automate à états finis : il reconnaît les langages de type 3
• Automate à pile : il reconnaît les langages de type 2
• Automate à bornes linéaires : il reconnaît les langages de types 1
• Machine de Turing : automate qui reconnaît les langages de type 0

4
 Automate Fini
Définition

Un automate d’états finis est défini par un quint-uplets A=(X, Q , I , 𝛿 , F)

Avec :
X : L’alphabet.
Q : L’ensemble fini des états.
I : L’ensemble des états initiaux (I⊆Q)
F : L’ensemble des états finaux (F⊆Q)
𝛿 : La relation de transition définie par l’ensemble fini de transitions de la
forme (i, 𝛿, j) où i et j sont des états et a est un symbole ∈ X.

On la note 𝛿(i,a)=j qui signifie la transition de l’état i vers l’état j en lisant

le symbole a .

5
 Automate Fini
Représentation Graphique

Elle consiste à représenter un automate d’états finis par un graphe

orienté comme suit :

▪ Chaque état est schématisé par un rond (un nœud).

▪ Chaque état initial est précédé d’une flèche.
▪ Chaque état final est entouré d’un cercle.
▪ Pour chaque transition 𝛿(qi, a)=qj on raccorde le noeud qi au nœud qj
par un arc étiqueté par le symbole a

6
 Automate Fini
Représentation Graphique

Soit l’automate d’états finis A=(X , Q , I , 𝛿 ,F)

avec:
• X = {a, b, c}

• Q = {q1, q2, q3, q4}

• I = {q1, q2}

• F = {q4}
• Les transitions:
𝛿 (q1,a)= {q1,q3}
𝛿 (q2,b)= {q2,q3}
𝛿 (q3,c)= {q3,q4}
𝛿 (q4,b)= q4

7
 Automate Fini
Représentation Matricielle

Elle consiste à représenter un automate d’états finis par une matrice dont :

▪ Les indices de lignes correspondent aux états de Q.

▪ Les indices de colonnes correspondent aux symboles de X.

▪ Chaque case de la matrice de ligne qi et de colonne xi correspond à la relation de

transition 𝛿 (qi, xi )

8
 Automate Fini
Représentation Matricielle

Soit l’automate d’états finis A=(X , Q , I , 𝛿 ,F)

avec:

• X = {a, b, c}

• Q = {q1, q2, q3, q4}

• I = {q1, q2}

• F = {q4}

• 𝛿 (q1,a)= {q1,q3}
𝛿 (q2,b)= {q2,q3}
𝛿 (q3,c)= {q3,q4}
𝛿 (q4,b)= q4

9
 Automate Fini
Langage Accepté par un automate

❑ Définition

Soit l’automate d’états finis A=(X , Q , I , 𝛿 ,F), on dit que:

Tout mot fini w = x0.x1.x2....xn de X est accepté par un automate A si et

seulement si il existe une séquence q0.q1.q2. . . . qn.qn+1 de Q telle que :

• Pour tout 0≤i≤n, (qi,xi,qi+1) ∈ δ.

• qn+1 appartient à l’ensemble F.
• Le langage accepté (ou reconnu) par un automate A, noté L(A) est
constitué de l’ensemble des mots acceptés par A.
• Le langage accepté par un automate d’état fini est un langage régulier.

10
 Automate Fini
Langage Accepté par un automate

❑ Exemple

1. Le langage accepté par cet automate est :

L(A1)={anbp / n>0, p>0 }. Les mots bbab,bba et aba ne aab est accepté par l’automate
sont pas acceptés par cet automate.

• 2. L(A2)={a, aba, ababa, abababa,…}

baa n’est pas accepté par l’automate

11
 Automate Fini
Automate Fini Non Déterministe

❑ Non Déterminisme

Un automate est dit indéterministe, car:

1. Il peut y avoir plusieurs états initiaux

2.Etant donné un état 𝛿i ∈ 𝛿 et un symbole a ∈ X ,

il peut exister plusieurs transitions possibles

(au niveau de la représentation graphique par un

graphe, ce non déterminisme correspond au cas
où il y a plusieurs arcs étiquetés par un même
symbole terminal qui partent
du même sommet)
12
 Automate Fini
Automate Fini Déterministe

Un automate est dit déterministe, si:

1. Il a un seul état initial

2. Etant donné un état 𝛿i ∈ 𝛿 et un symbole a ∈ X . Il existe une seule transition

possible

13
 Automate Fini
Automate avec ε –transition (ε-AFN)

❑ Définition

Les automates finis possédant des ε-transitions sont des automates pouvant faire
spontanément des transitions. Les arcs correspondants sont étiquetées par le
symbole ε et ne consomment aucun caractère de la chaîne d’entrée.

Exemple:

Un ε-AFN acceptant les mots clé ebay et web.

∑ebay , ∑web acceptés par l’automate

∑x n’est pas accepté

14
 Déterminisation d’un AFN

❑ Objectif

▪ Pour déterminer si un mot u de longueur n est accepté, un AFD effectue

exactement n transitions, tandis qu’un AFN en effectue de l’ordre de 2n .
L’exécution d’un AFD est donc nettement plus efficace que celle d’un AFN.
▪ En contrepartie, on peut se demander si les AFN sont plus généraux, c’est-à-dire
s’ils acceptent plus de langages que les AFD. La réponse, négative, est donnée par
le théorème suivant.

❑ Théorème (Rabin-Scott)
Tout langage reconnu par un AFN peut être reconnu par un AFD.

15
 Déterminisation d’un AFN

❑ En pratique:
Prenons l’automate suivant:

On construit ensuite les états de l’AFD et leur fonction de transition

16
 Déterminisation d’un AFN

❑ En pratique:
Au départ, l’AFD a un seul état qui est composé de l’ensemble des états initiaux de
l’AFN : sur notre exemple, l’état initial de l’AFD est {S1,S2}. A chaque fois qu’on ajoute
un nouvel état dans l’AFD, on détermine sa fonction de transition en faisant l’union des
lignes correspondantes dans la table de transition de l’AFN : sur notre exemple, pour
l’état {S1,S2}, on fait l’union des lignes correspondant à S1 et S2, et on
détermine la fonction de transition:

17
 Déterminisation d’un AFN

❑ En pratique:
On rajoute ensuite les états {S1,S3} et {S2,S3} à l’AFD et on détermine leur fonction de
transition selon le même principe. De proche en proche, on construit la table de transition
suivante pour l’AFD :

18
 Déterminisation d’un AFN

❑ En pratique:

L’ensemble des états de l’AFD est Q = {{S1, S2}, {S1, S3}, {S2, S3}, {S3, S4}}. Les
états de l’AFD contenant un état final de l’AFI sont des états finaux. Ici, l’AFN a un seul
état final S4 et l’ensemble des états finaux de l’AFD est F′ = {{S3,S4}}. Cet AFD
correspond au graphe suivant :

19
 Déterminisation d’un AFN

❑ En pratique:

AFN AFD

20
 Minimiser un Automate Fini
Déterministe

❑ Objectif:

La minimisation d'un automate fini déterministe est l'opération qui consiste à

transformer un automate fini déterministe donné en un automate fini déterministe
ayant le nombre minimal d'états et qui reconnaît le même langage régulier. La
minimisation a une importance pratique évidente par le gain d'espace qu'elle permet.

La minimisation s’effectue :

1. En éliminant les états dits inaccessibles

2. En regroupant les états congruents (appartenant à la même classe d’équivalence).

21
 Minimiser un Automate Fini
Déterministe
1. L’élimination des états inaccessibles:
• Un état est dit inaccessible s’il n’existe aucun chemin permettant de l’atteindre à
partir de l’état initial. c’est-à- dire qu’ils ne participeront jamais à l’acceptation d’un
mot. Ainsi, la première étape de minimisation d’un AEF consiste à éliminer ces
états.

Exemple

• Les états 7 et 3 sont inaccessibles. Donc nous les supprimons.

22
 Minimiser un Automate Fini
Déterministe

1. L’élimination des états inaccessibles en utilisant l’algorithme de marquage

• Pour des automates de taille importante, nous utilisons l’algorithme de marquage

pour supprimer les états inaccessibles .

• Le principe de cet algorithme est de commencer le marquage des états depuis l’état
initial et marquer les états atteints de bout en bout jusqu'à trouver des états non
marqués.

23
 Minimiser un Automate Fini
Déterministe
1. L’élimination des états inaccessibles en utilisant l’algorithme de marquage

Etats a b
1* 2 5
2* 2 4
3* 3 2
4* 5 3
5* 4 6
6* 6 1
7 5 7

24
 Minimiser un Automate Fini
Déterministe
1. L’élimination des états inaccessibles en utilisant l’algorithme de marquage

25
 Minimiser un Automate Fini
Déterministe
2. Regroupement des états équivalents

❑ Les états β-équivalents:

Deux états qi et qj sont dits β-équivalents s’ils permettent d’atteindre les états
finaux à travers les mêmes mots. On écrit alors : qi β qj.

❑ Remarque:
• La relation β-équivalence est une relation d’équivalence.
• Le nombre de classes d’équivalence de la relation β-équivalence est égale au
nombre des états de l’automate minimal car les états de chaque classe
d’équivalence acceptent le même langage (ils seront fusionnés).

26
 Minimiser un Automate Fini
Déterministe
2. Regroupement des états équivalents

❑ Exemple 1:

Soit AEF suivant (initial=0, finaux={2,3})

Etat a b Etat a b
0 1 0 0 1 0
1 1 2 1 1 2
2 3 2 2 2 2
3 3 2

27
 Minimiser un Automate Fini
Déterministe
2. Regroupement des états équivalents

❑ Exemple 2: Soit AEF suivant (initial=1, finaux={1,2})

1. Nous avons éliminé les états inaccessibles ( l’état 7)

2.Nous ne trouvons pas des états ayant la même fonction donc pour

réduire les états il faut construire des classes d’équivalence en suivant

l’algorithme de réduction des états Etats a b

1 2 5
2 2 4
3 3 2
4 5 3
5 4 6
6 6 1
28
 Minimiser un Automate Fini
Déterministe
2. Regroupement des états équivalents

❑ L’algorithme de réduction des états :

29
 Minimiser un Automate Fini
Déterministe
2. Regroupement des états équivalents

Exemple:

Etape 1: Créer deux classes d’états

1. A={1,2} ( les états finaux)

2. B={3,4,5,6} ( les états non finaux)

Etape 2: Vérifier la cohérence des classes

• On dit qu’une classe A est cohérente par rapport à un symbole

a si Toutes les transitions de A avec le symbole a mènent à la
même classe . Si une classe n’est pas cohérente il faut la
découper au moins en deux partie jusqu’à trouver des classes

30
 Minimiser un Automate Fini
Déterministe
2. Regroupement des états équivalents Etats a b
1 2 5
Nous allons procéder par itération
2 2 4
1 ère Itération: (A={1,2}, B={3,4,5,6}) 3 3 2
A a b 4 5 3
1 2∊ A 5∊ B 5 4 6
2 2∊ A 4∊ B 6 6 1

B a b
A est cohérente
3 3∊ B 2∊ A
4 5∊ B 3∊ B
5 4∊ B 6∊ B
6 6∊ B 1∊ A
B n’est pas cohérente. Il faut donc l’éclater en
deux classes B={3,6} et C={4,5} 31
 Minimiser un Automate Fini
Déterministe
2. Regroupement des états équivalents Etats a b
1 2 5
Nous allons procéder par itération
2 2 4
1 ère Itération: (A={1,2}, B={3,4,5,6}) 3 3 2
A a b 4 5 3
1 2∊ A 5∊ B 5 4 6
2 2∊ A 4∊ B 6 6 1

B a b
A est cohérente
3 3∊ B 2∊ A
4 5∊ B 3∊ B
5 4∊ B 6∊ B
6 6∊ B 1∊ A
B n’est pas cohérente. Il faut donc l’éclater en
deux classes B={3,6} et C={4,5} 32
 Minimiser un Automate Fini
Déterministe
2. Regroupement des états équivalents

Nous allons procéder par itération

2 ère Itération: (A={1,2}, B={3,6}, C={4,5})

A a b C a b
1 2∊A 5∊C 4 5∊C 3∊B
2 2∊A 4∊C 5 4∊C 6∊B
A est cohérente C est cohérente

B a b
3 3∊B 2∊A
6 6∊B 1∊A
B est cohérente

Donc l’AEFD contiendra trois états A,B et C 33

 Minimiser un Automate Fini
Déterministe
Résultat de l’algorithme: l’AEF contiendra trois états A,B et C
▪ Etat iniIal= la classe qui conIent l’ancien
état iniIal : A ( 1)
A a b ▪ Etats finaux= les classes qui conIennent des
1 2∊A 5∊C états finaux: {A}
2 2∊A 4∊C
Etat a b
B a b
A A C
3 3∊B 2∊A
B B A
6 6∊B 1∊A
C C B
C a b
4 5∊C 3∊B AFD minimal
5 4∊C 6∊B

34
 Minimiser un Automate Fini
Déterministe

Résultat de l’algorithme: l’automate obtenu est minimal et accepte le

même langage

Etat a b
A A C
B B A
C C B

35
 Exercice

Exercice 1:

Déterminiser et minimiser l’automate suivant:

36
 Solution
Exercice 1:
1. Déterminisation

a b a b

0 {0,1,2} - 0 1 -
{0,1,2} {0,1,2} {1,2} Réduction 1 1 2
{1,2} 1 {1,2} 2 3 2
1 - {1,2} 3 - 2

37
 Solution

Exercice 1:
1. Déterminisation

a b
0 1 -
1 1 2
2 3 2
3 - 2

AFD

38
 Solution

Exercice 1:

2. Minimisation:
1 ère itération

A={1,2}
B={0,3}

A a b B a b
1 1∊A - 0 1∊A -
2 3∊B 2∊A 3 - 2∊A

A n’est pas cohérente B n’est pas cohérente

Donc nous allons étaler A et B en deux classes. Cela fera 4 classes A={1}, B={2}, C={0}, D={3}
Puisque le nombre de classes est égal exactement au nombre des états de l’automate de base
alors l’automate de base est déjà minimal.

39
 Automates et Expression Régulières
Le passage d’un AEF vers une ER

❑ Principes

• Chaque mot accepté correspond à un chemin de l’état initial vers l’état final.

• L’expression régulière obtenue est l’union de tout les chemins possibles.

Exemples:

1.

ER: a*ba*ba*

40
 Automates et Expression Régulières
Le passage d’un AEF vers une ER

❑Exemples:

2.

Chemin 1: a*

Chemin 2: a*ba*

Chemin 3: a*ba*ba*b(ab)*

ER: a* |a*ba* | a*ba*ba*b(ab)*

41
 Automates et Expression Régulières
Le passage d’un AEF vers une ER
❑ L’algorithme des équations linéaires en utilisant le lemme d’Arden
Soit A = (X, Q, q0, F, δ) un automate à états finis quelconque. On désigne par Li le
langage accepté par l’automate si son état initial était qi. Par conséquent, trouver le
langage accepté par l’automate revient à trouver L0 étant donné que l’analyse
commence à partir de l’état initial q0. L’automate permet d’établir un système
d’équations aux langages de la manière suivante :

— si δ(qi,a)=qj alors on écrit: Li =aLj;

— si qi ∈F, alors on écrit: Li =ε
— 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 du lemme d’Arden suivante : la solution de l’équation L = αL|β est le langage
L = α∗β

(attention! si vous obtenez L = αL alors c’est la preuve d’une faute de raisonnement).

42
 Automates et Expression Régulières
Le passage d’un AEF vers une ER
❑ Exemple:
Trouvons le langage accepté par cet automate.

Le système d’équations est le suivant: :

1) L0 = aL0| bL1| ε

2) L1 = bL0| aL2

3) L2 = aL1| bL2

Ensuite on applique le lemme d’Arden:

La solution de l’équation L = αL|β est le langage L = α∗β

43
Automates et Expression Régulières

44
Solution

45