21/09/2022

Automates à Etats Fini

Automates à états finis;

Paradigme déterministe (AFD) et
non déterministe (AFN);
Equivalence d’automates;
Algorithme de déterminisa@on;
Automate AFD canonique
Algorithme de minimisa@on

Turc m écanique
Auteur : Olivier Raynaud
Version de travail : rentrée 2022
Sensibilité : Référence :

[Link]

Automate à états fini

qAutomate
Ø Un automate à états fini est un
modèle mathéma@que de calcul
u@lisé pour de nombreuses
applica@ons.

Citons la linguistique, la biologie ou

Machine de
Edward F. Moore
l‘informatique pour la concep@on de
programmes par exemple.

Défini/on intui%on (automate à états fini déterministe): Un A.F.D. est une

machine abstraite suscep@ble d‘être dans un nombre fini d‘états mais étant à
un moment donné dans un seul état appelé état courant. Le passage d‘un
état à un autre s‘appelle une transi@on.

Automate à états fini déterministe - AFD

qL’exécution de l’automate sur un mot d’entrée peut être décrite de la façon suivante :
Ø mettre l‘automate dans l‘état initial q0 , et lire la première lettre w0 du ruban;
Ø tant que la dernière lettre wn de l‘entrée n‘est pas lue, répéter la transition:

Ø si, à la fin de l‘exécution, l‘état qn est un état d‘accéptation alors le mot w est dit accepté
par l‘automate.

w0 w1 wn $ w0 w1 wn $ w0 w1 wn $

accès en lecture
transition
q0 q1 qn

1
 21/09/2022

Automate à états fini déterministe – AFD

Défini/on (Automate à états fini déterministe – AFD) :

Remarque :
Par soucis de simplification, dans un diagramme de transitions, une transition entre
deux états peut porter plusieurs symboles.

Automate à états fini déterministe - AFD

Diagramme de transitions de A
Table de transitions

A DFA (drawn in JFLAP) for the example language

Applica9on

qProblème de passage de rivière

Problème (le loup, la chèvre et les choux) : Un fermier doit passer la

rivière dans une barque juste assez grande pour lui et son loup, ou lui et
sa chèvre ou encore lui et ses choux.
Les choux seront mangés s‘il les laisse seuls avec la chèvre, et la chèvre
sera mangée s‘il la laisse seule avec le loup.
Comment faire passer la rivière à tout ce pe<t monde sans dégât?

//[Link]/wolf-schaf-und-kohl-sind-sinnlos/

2
 21/09/2022

Résolution de problème

qProblème de passage de rivière - Interprétation

Ø Un automate permet de caratériser l‘ensembles des états du système
atteints en fonction des actions entreprises.

Ø Un automate n‘est donc pas seulement un outil de résolution d‘un problème,

mais aussi un outil de description de l‘ensemble des solutions acceptables pour
le résoudre.
Il est en cela du même niveau abstrait qu‘un algorithme.

Diagramme de transi@ons

Fonc9on de transi9on étendue d’un AFD.

Ø La fonction de transition étendue est une fonction prenant en entrée un état q

et une chaîne w et retourne un état p. p est l‘état atteint par l‘automate en
partant de l‘état q et en lisant la chaîne w.

Défini/on (fonc@on de transi@on étendue d‘un AFD) :

Exemple : Soit w la chaîne 0010 alors la chaîne x vaut 001 et a est le symbole 0.

Langage des mots contenant un nombre pair de symboles

Diagramme de transitions de A

3
 21/09/2022

Mot accepté par un AFD

Ø Un mot w est accepté si le chemin étiqueté par les symboles de w dans

l‘automate part de l‘état initial et termine dans un état final.

Défini/on (mot accepté par un AFD) :

Diagramme de transitions

10

Langage reconnu par un AFD

Ø Le langage reconnu par un automate est le langage composé de tous les

mots qu’il accepte.
Définition (langage reconnu par un AFD) :

Table de transi@on

Diagramme de transi%ons

Cet automate reconnaît le langage des mots contenant le facteur 01.

11

Automate à états fini non déterministe – AFN

Définition (automate à états fini non déterministe – AFN) :

Diagramme de transitions d’un AFN

12

4
 21/09/2022

Fonc9on de transi9ons étendue d’un AFN

qFonc:on de transi:on étendue

Ø La fonc@on de transi@on étendue est une fonc@on prenant en entrée un état q
et une chaîne w et retourne l‘ensemble des états que l‘on aVeint en suivant la
chaîne w.

Défini/on (fonc@on de transi@on étendue d‘un AFN) :

13

Exemple de fonction de transitions étendue

Table de transition

Diagramme de transitions de A

14

Langage reconnu par un AFN

Ø Un mot w est accepté par un AFN s’il existe une suite de choix permeVant de
terminer la lecture de w sur un état d’accepta@on.

Définition (langage reconnu par un AFN) :

Table de transi@ons

Diagramme de transi%ons

Cet automate reconnaît le langage des mots contenant le facteur 01.

15

5
 21/09/2022

Equivalence d’automates

Définition (équivalence) : Soient A et A‘ deux automates à états fini, on dit

que A est équivalent à A‘, et on note A ~ A‘ si L(a) est égal à L(A‘).

hCps://w w [Link]/2009/02/[Link] l

16

Equivalence de langage

qExemples
Table de transi@ons de A
Diagramme de transitions de A

Table de transitions de A’ Diagramme de transitions de A’

Deux automates différents qui reconnaissent le même langage.

Les deux automates A et A’ sont équivalents.

17

Construc9on par sous-ensembles

Ø Pour tout A.F.N. nous pouvons appliquer une méthode appelée construction
par sous-ensembles permettant de construire un A.F.D. reconnaissant le
même langage.

Défini/on (construc@on par sous-ensembles) :

18

6
 21/09/2022

Exemple de construction

Cet automate reconnaît le langage des mots terminant le facteur 01.

Table de transitions

Automate AFN A

Automate AFD A’
tel que L(A) = L(A’)

19

Cas difficile

AFD pour n=2

[Link]

20

Algorithme de déterminisation

21

7
 21/09/2022

Théorème d’équivalence

Théorème (construc@on par sous-ensembles) :

Théorème (équivalence AFD et AFN) :

22

AFN avec 𝜀-transition

Ø Nous pouvons rajouter au modèle des AFN la possiblité de transitions portant

le symbole 𝜀. Dans un AFN-𝜀, il est autorisé de suivre spontannément une
transition portant le symbol 𝜀 sans recevoir de symbol d‘entrée.

Définition (AFN-𝜀) :

23

AFN-𝜀 reconnaissant les nombres décimaux AFN avec 𝜀-transition

24

8
 21/09/2022

𝜖-fermeture

Définition (𝜀-fermeture d‘un état):

25

𝜀-fermeture

Définition (𝜀-fermeture d‘un ensemble d‘états):

26

Déterminisa9on pour AFN-𝜀

27

9
 21/09/2022

AFD minimum

Théorème (AFD canonique) :

Soit L un langage rationnel, il existe un automate à états fini déterministe
minimum qui reconnait L. Cet automate dit canonique admet un nombre
minimum d‘états et est unique.

[MN 74, HMU 1979]

28

Minimisation d’un AFD

Ø Minimisa@on par le principe algorithmique d‘éclatement de par@@on

Principe algorithmique d‘éclatement (ou affinage) de partition:

o Le processus est initialisé à partir d‘une ou plusieurs classes
o On applique un critère qui permet de partitionner une classe en
plusieurs classes plus restreintes.
o Le processus se termine lorsque aucune des classes de la partition ne
peux plus être partitionner.

29

Algorithme de minimisa9on

30

10
 21/09/2022

Mise en application

31

Pour résumer

qQuelques points essentiels de l’exposé

ü Définitions : Automate à états fini (AFD), fonction de transition, mot et langage

accepté par un AFD.
ü Définition : Automate à états fini non déterministes (AFN), fonctions de
transition, mot et langage reconnus par un AFN;
ü Définition : Equivalence d’automate;
ü Algorithme : Déterminisation d’un AFN par la méthode des sous-ensembles.
ü Définition : AFN avec epsilon-transition

ü Théorème : Existence d’un automate (AFD) canonique

ü Algorithme : Algorithme de minimisation par affinage de partition

32

Bibliographie
• [HMU] Introduc*on to Automata Theory, Langage and Computa*on
J.E. HopcroJ, R. Motwani, J.D. Ullman Edi@on Adison Wesley 2001;

• [Berry 00] Support de cours de Théorie des Langages

A. Berry – Université Clermont-Auvergne 2000 – 2016

• [Wikipedia] Mul/ples références dans le texte.

33

11