U n i ve r s i t é d e S o u s s e

Ecole Supérieure des Sciences

et des Technologies de Hammam Sousse

Cours : Théorie des Langages

Chapitre 4 :
Les Automates

SI 2

Dr. Olfa FAKHFAKH

[email protected]

A.U. 2020-2021
 Sommaire

1. Langage reconnu par un automate

2. Construction d’un AEF à partir d’une ER

3. Automates à états finis déterministes AFD

4. Automates à états finis non déterministes AFN

5. Équivalence entre AFN et AFD

Dr. Olfa Fakhfakh 2

03/12/2020
 Motivations des automates
● Problèmes
▶ Est-ce qu’une chaîne w appartient à un langage L ?
▶ Peut-on décrire une petite "machine" qui acceptera ou rejettera une
chaîne w de * selon qu'elle appartient, ou non, au langage L ?
● Reconnaisseur d’un langage
▶ Machine permettant de reconnaître tous les mots du langage
● Domaines d’application des automates
▶ Modélisation des neurones et des circuits logiques (années ’50-’60),
▶ analyse lexicale en compilation,
▶ traitement du texte (ex. reconnaissance de motifs),
▶ modélisation de mécanismes de contrôle, …

Dr. Olfa Fakhfakh 3

03/12/2020
 Introduction

● Les expressions régulières permettent de générer les langages

réguliers.

● Les automates sont des « machines » permettant de reconnaître

exactement ces langages.

● En d'autres termes, l'ensemble des langages acceptés par un

automate fini coïncide avec l'ensemble des langages réguliers.

Dr. Olfa Fakhfakh 4

03/12/2020
 Définitions

● Un automate est une procédure effective (un algorithme)

permettant de déterminer si un mot donné appartient à un
langage.
● À la classe des langages réguliers correspond une classe
particulière d’automates (reconnaissant les langages réguliers
et seulement ceux-ci) : la classe des automates finis.

● Un automate fini A = (Q, , , I, F) sur l’alphabet  est

composé d’un ensemble fini d’états Q, d’une relation de
transitions   Q ×  × Q, d’un ensemble I  Q d’états
initiaux, et d’un ensemble F  Q d’états finaux (ou terminaux).

Dr. Olfa Fakhfakh 5

03/12/2020
 Définitions

Un automate fini est défini par un 5-uplet A = (Q, , , I, F) , où

●  est l’ensemble fini des symboles
● Q est un ensemble fini : l’ensemble des états
● I  Q est le sous-ensemble des états initiaux
● F  Q est le sous-ensemble des états finaux
●  est un ensemble fini de transitions :
▶une transition est un triplet (i, a, j ) , où i et j sont des états et a est
un symbole.
▶une fonction de transition qui prend comme argument un état et
un symbole d'entrée et qui retourne un état.  :  × Q  Q.
● Une transition (i, a, j ) se représente par une flèche de i à j ,
munie d'une étiquette a :
Dr. Olfa Fakhfakh 6
03/12/2020
 Convention graphique

● État initial

● État intermédiaire

● État final

● Transition

Dr. Olfa Fakhfakh 7

03/12/2020
 Exemple d’automate à états fini

● Représentation matricielle

Dr. Olfa Fakhfakh 8

03/12/2020
 Exemple d’automate à états fini

● Soit un automate A = (Q, , , I, F) où :

▶ ={a,b}
▶Q={1.2.3}
▶I=1
▶F ={1,2}
▶La fonction de transition est donnée par

Dr. Olfa Fakhfakh 9

03/12/2020
 Langage reconnu par un automate

● Définition. Une chaîne w * est reconnue par un automate A

s'il y a un cheminement, c’est-à-dire une suite de transitions,
partant d'un état initial, aboutissant à un état final, et dont la
suite des étiquettes est w .

● Définition. Le langage reconnu par un automate A est

l'ensemble de toutes les chaînes reconnues. Il est noté L(A ) .

Ainsi, le rôle fondamental d'un automate est d'accepter ou de

rejeter des mots.
 Un automate partitionne l'ensemble des mots sur en deux sous-
ensembles L(A) et * \ L(A)

Dr. Olfa Fakhfakh 10

03/12/2020
 La fonction de transition étendue

● La fonction de transition étendue appelée ˆ décrit ce qui se

passe lorsqu’on se positionne dans un état quelconque de
l’automate et que l’on suit une séquence quelconque d’entrées.
● ˆ : Q  *  Q est définie par induction sur la longueur de la
chaîne de symboles d’entrée par :
▶ ˆ(q,  )  q

▶Soit w = xa, a le dernier symbole de w et x la chaîne

début de w,

▶ si ˆ (q, x)  p , alors ˆ(q, w)   ( p, a)   (ˆ(q, x), a)

Dr. Olfa Fakhfakh 11

03/12/2020
 Langage engendré par un automate

● Le langage d’un automate à états finis déterministe

A = (Q, , , I, F) est défini par :

▶l’ensemble des chaînes obtenues sur tout chemin du graphe

partant du nœud initial et s’achevant sur un nœud final.

▶ L ( A)  w 
/ ˆ ( q, w)  F 

Dr. Olfa Fakhfakh 12

03/12/2020
 Exemple

● Les mots « abbab » et « bba » sont ils acceptés par cet

automate ?

● L'automate A accepte le mot « abbab » car on a, partant de

l‘état initial, le parcours suivant au sein de A est :

● Par contre « bba » n’est pas accepté par A.

Dr. Olfa Fakhfakh 13

03/12/2020
 Exemple

● Langage construit sur {0,1} dont les chaînes ont un nombre pair
de 0 et un nombre pair de 1.

Dr. Olfa Fakhfakh 14

03/12/2020
 Exemple : Table de transition

Chemins

Dr. Olfa Fakhfakh 15

03/12/2020
 Exercice

● Représenter l’automate A qui accepte exactement le langage

formé des mots sur l'alphabet ={a,b} et contenant un nombre
impair de a.

● L(A) ={w  / |w|a mod 2 =1}

Dr. Olfa Fakhfakh 16

03/12/2020
Construction d’un AEF à partir
d’une ER
 Construction d’un AEF à partir d’une ER
● Théorème :
● Un langage est régulier si et seulement si il est accepté par un
automate fini (AEF).
● Tout langage défini par un automate est aussi défini par une
expression régulière
● Si L(A) est le langage défini par un AFD, A, alors il existe une
expression régulière R telle que : L(R) = L(A)
● Tout langage défini par une expression régulière est aussi
défini par un automate
● Si L(R) est le langage défini par une expression régulière, alors
il existe un automate A tel que : L(A) = L(R)
● Pour construire un AEF à partir d’une ER, on utilise la
représentation de Thompson qui se base sur la récursivité des
expressions régulières. 18
03/12/2020 Dr. Olfa Fakhfakh
 Des expressions aux automates
● A toute expression régulière ER, on peut associer un automate
fini A de telle sorte que L(ER) = L(A). On procède par
récurrence sur la longueur de ER.
● Si ER = , Automate acceptant le langage {} (la chaîne vide)


● Si ER = , Automate reconnaissant l’ensemble vide (le vide)


● Si ER = a, Automate acceptant le langage {a} (la chaîne vide)
a
L(A)
Dr. Olfa Fakhfakh 19
03/12/2020
 Automate construit à partir de la disjonction

● Soit R et S deux expressions régulières

● L(R|S) = L(R)  L(S)
● L’AEF présentant l’expression régulière R|S

 

 

Dr. Olfa Fakhfakh 20

03/12/2020
 Automate construit à partir de la concaténation

● Soit R et S deux expressions régulières

● L(R.S) = L(R) . L(S)
● L’AEF présentant l’expression régulière R . S

Dr. Olfa Fakhfakh 21

03/12/2020
 Automate construit à partir de la fermeture de Kleen

● Soit R une expression régulière

● L(R*) = L(R)*
● L’AEF présentant l’expression régulière R *

 

● R *=  | R +

Dr. Olfa Fakhfakh 22

03/12/2020
 Exemple de construction d’AEF à partir d’une ER

● Soit l’expression régulière E = ( a | b ) * a b b

● Étape 1

● Étape 2

a|b

Dr. Olfa Fakhfakh 23

03/12/2020
 Exemple de construction d’AEF à partir d’une ER

● Étape 3

(a|b)*

Dr. Olfa Fakhfakh 24

03/12/2020
 Exemple de construction d’AEF à partir d’une ER

● Étape 4
(a|b)* abb

Dr. Olfa Fakhfakh 25

03/12/2020
 Exercice 1

● Représenter l’AEF de l’expression régulière b * a b * a b *

● Représenter l’AEF de l’expression régulière ((a*|b*)c)*

Dr. Olfa Fakhfakh 26

03/12/2020
Automates à états finis
déterministes AFD
 AFD : Définition

● Un automate est déterministe si et seulement si les deux

conditions suivantes sont vérifiées :
1. L’automate possède un et un seul état initial ;
2. Pour chaque état q et pour chaque lettre , il existe au plus une
transition issue de q d’étiquette .
● Un automate fini est déterministe si et seulement si la relation 
est une fonction de transition :  : Q    Q

 D’un état donné, il part au plus une seule flèche étiquetée par
une lettre donnée.
 On n’autorise plus les ε-transitions

Dr. Olfa Fakhfakh 28

03/12/2020
 AFD - Complet : Définition

 Un automate fini déterministe est complet ssi  est une fonction

totale définie sur l’ensemble (Q × Σ) tout entier.
● C.à.d.  est définie pour tout couple (q,  )  Q × Σ

 De chaque état et pour chaque symbole de l’alphabet Σ, il

part exactement une flèche étiquetée de la lettre.
 Il y a exactement une transition pour chaque symbole de
l’alphabet

Dr. Olfa Fakhfakh 29

03/12/2020
 De AFD non complet vers AFD complet

● Tout AFD non complet peut être transformé en AFD complet par
l’ajout d’un état spécial qui est ni initial ni final et vers lequel se
dirigent toutes les transitions qu'on ajoute,
● De telle sorte que de chaque état de l’automate parte
exactement une transition sur chaque symbole de l’alphabet.
● En plus, cet état comportera aussi des flèches vers lui-même qui
sont étiquetés par tous les symboles de l'alphabet

● Remarque : La complétion ne change ni le langage reconnu, ni

le déterminisme éventuel de l’automate.

Dr. Olfa Fakhfakh 30

03/12/2020
 AFD : Exercice

● Les automates suivants sont ils déterministes ? Si oui sont ils

complets ?

Non déterministe Non déterministe Oui déterministe

Non complet

Dr. Olfa Fakhfakh 31

03/12/2020
 AFD Complet : Exercice

● Donner l’AFD complet correspondant à cet automate

● Attention : P n’est pas un état d’acceptation ! !

● Remarque : un automate peut être non déterministe mais
complet.

Dr. Olfa Fakhfakh 32

03/12/2020
 AFD : Exemple 1
● Soit A = (Q, , , q0, q1)  0 1
● Σ = {0,1}
q0 q0 q1
● Q = {q0 , q1}
● La fonction de transition  est définie par : q1 - q1
● q0 est l’état initial,
● q1 est l’état final.
0 1 A est
déterministe
q0 q1 non complet

● A accepte les mots du langage L(A) décrit par l’expression

régulière : 0*11*
Dr. Olfa Fakhfakh 33
03/12/2020
 AFD – Complet : Exemple 1
● Soit A’ = (Q, , , q0, q1)  0 1
● Σ = {0,1} q0 q0 q1
0,1
● Q = {q0 , q1, q2} q1 q2 q1
●  est définie par : q2 q2 q2 q2
● q0 est l’état initial, 0
0 A’ est
● q1 est l’état final.
1 déterministe
q0 q1
complet
1
● A’ reconnait le langage L(A’)=L(A) décrit par 0*11*
● L’état q2 de cet automate correspond à un état d’erreur : l’automate va
dans cet état dès lors qu’il reconnait que le mot ne fait pas partie du
langage, et y reste jusque la fin de l’analyse.
● Dans un souci de simplification, on ne représente généralement pas cet état,
et on représente l’automate par le graphe de A.
Dr. Olfa Fakhfakh 34
03/12/2020
 AFD : Exercice

● Représenter un automate acceptant tous les mots se terminant

par b

● Expression régulière correspondante : (a|b)* b

Dr. Olfa Fakhfakh 35

03/12/2020
 AFD : Exemple 2

● Représenter l’AFD du langage L= { a n b p / n > 0 , p > 0 }

● L’AFD complet correspondant :

Dr. Olfa Fakhfakh 36

03/12/2020
Automates à états finis non
déterministes AFN
 AFN : Définition

● Dans un automate fini non-déterministe (A.F.N) il peut y avoir le

choix entre plusieurs chemins lors de la lecture d’un mot.
● Pour qu’un mot soit accepté, il suffit que ses lettres étiquettent
un chemin de l’état initial à un état final (même s’il existe
d’autres chemins non réussis).
● Informellement, les AFN sont obtenus en enrichissant le
fonctionnement des AFD de deux nouvelles capacités :
▶on autorise des transitions sur le mot vide 
▶on permet qu’à une lettre et un état fixés correspondent plusieurs
transitions. Ainsi, lorsqu’il est dans un état p et qu’il lit une lettre
a, l’automate peut choisir de manière non déterministe d’évoluer
vers différents nouveaux états.

Dr. Olfa Fakhfakh 38

03/12/2020
 Définition formelle de AFN vs AFD

● Formellement, les définitions des AFN et des AFD sont similaires.

● Dans les deux cas, il faut préciser un alphabet, un ensemble
d’états, une fonction de transition, un état initial et un ensemble
d’états finaux.
● Elles diffèrent cependant dans la nature de la fonction de
transition :
▶Dans un AFD, la fonction de transition associe à tout couple
constitué d’un état et d’une lettre, un unique état q  Q accessible
en une transition.
▶Dans un AFN, la fonction prend un couple constitué d’un état et
d’une lettre ou du mot vide et lui associe un ensemble d’états q 
Q accessibles en une transition.
Autrement dit :  : Q  (  )  (Q)
Dr. Olfa Fakhfakh 39
03/12/2020
 AFN : Exemple

● le langage des mots acceptés par l’automate est

L= { a n b p / n > 0 , p > 0 }

Dr. Olfa Fakhfakh 40

03/12/2020
 AFN avec  - transitions

● L’AFN décrivant l’expression aa* | bb*

Dr. Olfa Fakhfakh 41

03/12/2020
 AFN : exemple

● Soit le langage dénoté par l’expression régulière (a|b)*abb

● Ce langage peut être reconnu par l’AFN suivant :

● Représentation sous forme d’une table de transition

Dr. Olfa Fakhfakh 42

03/12/2020
 Equivalence AFN et AFD

● Pour déterminer si un mot u de longueur n est accepté,

▶ un AFD effectue exactement n transitions,
▶ tandis qu’un AFI 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, est non !
● En effet :
● Théorème (équivalence entre AFD et AFN) : La famille des
langages acceptés par un AFD est identique à la famille des
langages acceptés par un AFN

Dr. Olfa Fakhfakh 43

03/12/2020
 Equivalence AFN et AFD
Théorème
● Si un langage est reconnu par un automate fini non déterministe
alors il est aussi reconnu par un automate fini déterministe
● Démonstration
▶si l’automate fini du départ A est déterministe, c’est évident

▶si l’automate de départ n’est pas déterministe,

on se propose de construire un automate fini déterministe B qui
intègre tous les choix existant dans l’automate de départ (cf.
algorithme de déterminisation)

▶il resterait à prouver formellement que le nouvel automate B

accepte exactement les mots acceptés par A
Dr. Olfa Fakhfakh 44
03/12/2020
Construction d’un AFD à partir d’un AFN …