4ème Année G.

Info
Année 2013-2014

Support de cours

Théorie des Langages

&
Techniques de Compilation

Unité 2 : Analyse Lexicale

Prof. Redouane EZZAHIR

Table des matières
1. Introduction ........................................................................................................................................... 3
2. Aperçu sur la théorie des langages........................................................................................................ 4
2.1 Alphabets - Mots - Langages ......................................................................................................... 4
2.1.1 Définitions.............................................................................................................................. 4
2.1.2 Opérations sur les langages ................................................................................................... 5
2.2 Langages réguliers ......................................................................................................................... 6
2.2.1 Langages réguliers ................................................................................................................. 7
2.2.2 Expressions rationnelles ........................................................................................................ 7
3. Automates finis...................................................................................................................................... 9
3.1.1 Comment fonctionne les AFD .............................................................................................. 10
3.1.2 Configurations et mouvement............................................................................................. 11
3.1.3 Langages reconnaissables.................................................................................................... 11
3.1.4 Automate non déterministe ................................................................................................ 12
3.1.5 Automates équivalents ........................................................................................................ 12
3.1.6 D'un AFN à l’AFD équivalent ................................................................................................ 13
4. Translation des expressions régulières en automates ........................................................................ 17
4.1 є –Fermeture ............................................................................................................................... 18
4.2 Élimination des є-transitions ....................................................................................................... 19
5. Implantation d’un analyseur lexical .................................................................................................... 21
6. Exercices .............................................................................................................................................. 21
1. Introduction

Dans un compilateur, l'analyseur lexical lit les caractères du programme source, les regroupe en
unités lexicales significatives appelées lexèmes, et produit en sortie des jetons (tokens) représentant
ces lexèmes (Figure 1).

Figure 1 Schéma d’un analyseur lexical

Un jeton se compose de deux éléments, un nom symbolique et une valeur d'attribut. Les noms
symboliques sont des symboles abstraits qui seront utilisés par la phase d’analyse suivante. Ces
symboles sont appelés terminaux, car ils apparaissent comme symboles terminaux de la grammaire
du langage de programmation. La valeur de l'attribut, s'il est présent, est un pointeur sur la table des
symboles qui contient les informations supplémentaires sur le jeton. Cette information
supplémentaire ne fait pas partie de la grammaire, mais elle facilite implémentation du compilateur.

Exemple 1 : Soit le programme suivant :

float match0(char *s) /* find a zero */

{
if (!strncmp(s, "0.0", 3))
return 0.;
}

L’analyseur lexical va retourner le flot de jetons suivant :

FLOAT ID(match0) LPAREN CHAR STAR ID(s) RPAREN
LBRACE IF LPAREN BANG ID(strncmp) LPAREN ID(s)
COMMA STRING(0.0) COMMA NUM(3) RPAREN RPAREN
RETURN REAL(0.0) SEMI RBRACE EOF

L'objectif principal de l'analyse lexicale est de faciliter la tâche pour l’analyseur syntaxique qui le
suit. En théorie, le travail qui se fait lors de l'analyse lexicale peut être fait partie intégrante de
l'analyse syntaxique, en effet, cela est souvent appliquer dans les systèmes simples. Cependant, il y
a des raisons pour garder les deux phases séparées :
 Efficacité : Un analyseur syntaxique séparé peut faire des parties simples du travail plus vite
que dans un l'analyseur général. En outre, la taille d'un système qui est divisé en deux peut
être inférieure à la taille d’un système combiné, et ceci par un facteur qui peut être non-
linéaire.
 Modularité : La description syntaxique du langage ne doit pas être encombrée avec de petits
détails lexicaux tels que des espaces blancs et des commentaires.
 Tradition : Les langages sont souvent conçus avec des phases lexicales et syntaxiques
 distinctes dans l'esprit, et les documents standards de ces langages séparent généralement les
éléments lexicaux des éléments syntaxiques.

Il n'est généralement pas très difficile d'écrire un analyseur lexical à la main. Vous pouvez lire
d'abord l’espace blanc initial et l’ignorer, puis vous testez, dans l'ordre, pour voir si le prochain
jeton est un mot-clé, un nombre, une variable ou autre chose. Cependant, ce n'est pas une très bonne
façon de traiter le problème. Vous pouvez lire la même partie de l'entrée à plusieurs reprises tout en
testant chaque jeton possible et, dans certains cas, il ne peut pas être clair où le jeton suivant se
termine. En outre, un analyseur lexical écrit à la main peut être complexe et difficile à maintenir.
Ainsi, les analyseurs lexicaux sont normalement construits par des générateurs lexicaux, qui
transforment les spécifications lisibles de jetons et d'espace blanc en programmes efficaces. Nous
allons voir la même stratégie générale dans le chapitre sur l'analyse syntaxique :

Des spécifications dans une notation lisible bien définis sont transformées en programmes efficaces.
Pour une analyse lexicale, les spécifications sont traditionnellement écrites en utilisant des
expressions régulières : Une notation algébrique pour décrire des ensembles de chaînes. Les
analyseurs lexicaux générés sont dans une classe de programmes très simples, appelés automates
finis.

Ce chapitre décrit les expressions régulières et les automates finis, leurs propriétés et comment les
expressions régulières peuvent être convertis en automates finis. Enfin, nous discutons quelques
aspects pratiques de générateurs lexicaux.

2. Aperçu sur la théorie des langages

Le français est un langage, Java également. Le but de la théorie des langages et de donner un
modèle de ce qu’est un langage. Pour ce faire on utilise l’outil de base des scientifiques : les
mathématiques. Cependant, le modèle en question est un modèle qualitatif et non quantitatif : son
principal intérêt (à nos yeux) est de contribuer à améliorer l’activité de programmation. Enfin, il
faut admettre aussitôt le caractère réducteur, donc incomplet, de toute modélisation.

Nous demandons au modèle une aide pour résoudre deux problèmes étroitement liés :

 être capable de décrire un langage ;

 fabriquer une machine capable de reconnaître les textes qui appartiennent à un langage
donné.

Ces deux problèmes, description et reconnaissance, recèlent une difficulté intrinsèque : il faut
donner une description finie d’un objet en général infini : il y a en effet une infinité de textes
français, une infinité de programmes Java.

2.1 Alphabets - Mots - Langages

2.1.1 Définitions

 Un vocabulaire Σ (appelé aussi alphabet, ou lexique) est un ensemble fini de symboles (ou
de caractères) non vide.
  Un mot (ou phrase) sur un vocabulaire Σ est une séquence finie d'éléments de Σ
Les caractères sont des lettres, l'ensemble des lettres constitue donc un alphabet.
Exemples.
Table 1. Exemple de vocabulaire et mots
Vocabulaire Σ Mot sur Σ
{a,b} abb
{un, le, beau, féroce, chat, …} Un beau chat
{if, else, (, ), {, }, … } if(…){…} else {…}
{0,1} 100001

 Mot vide : Il y a un mot particulier, la séquence vide. On l'appelle le mot vide et nous le
notons ℇ (epsilon).
 Longueur d'un mot : Étant donné un mot w, on note |w| sa longueur, c'est-à-dire le nombre
de symboles qui le composent. En particulier |ℇ| = 0, et |w|a = le nombre de symboles « a »
dans le mot w.
 On note Σ* l'ensemble de tous les mots sur l'alphabet et Σ+ l'ensemble de tous les mots sur
l'alphabet sans ℇ.
Exemple 2 :
 Pour l'alphabet {a,b,c}, on a {a,b,c}*={ ℇ , a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, . . .}
 Pour la partie X={aa, b} composée des deux mots aa et b sur l'alphabet {a,b}, on obtient
{aa,b}*={ ℇ , b, aa, bb, aab, baa, bbb, aaaa, aabb, baab, bbaa, bbbb, . . .}

 Un mot u est un facteur d’un mot w  Σ* s’il existe α, βΣ* tels que w = αuβ. Si de plus α = ℇ
(i.e. w = uβ), u est dit préfixe, ou facteur gauche, de w. Si β = ℇ (i.e. w = αu), u est dit suffixe, ou
facteur droit, de w.
Exemple 3 :
 Soit w = aabccaa. Alors bcc est un facteur de w; aabc est un préfixe de w; caa est un suffixe
de w; aa est à la fois préfixe et suffixe de w.
 Pour tout mot w, ℇ et w sont à la fois préfixe et suffixe de w.

 On appelle L un langage formel (ou plus couramment langage) sur l'alphabet Σ si L  Σ*. Ø est le
langage vide (Ø≠{ℇ}). Autrement dit, c’est un ensemble de mots sur Σ.
Exemple 4 :
 Les ensembles {00; 01; 110; 1010} et {w  {0;1}* t.q |w|1 =1} sont des langages sur
l’alphabet {0;1}. Le premier est fini, le second infini (il contient, par exemple, la suite
infinie de mots : 1; 01; 001; 0001; . . .)
 L’ensemble des écritures d’entiers en base 10 est un langage sur l’alphabet {0,1, …,9}.

2.1.2 Opérations sur les langages

Les opérations sur les langages sont les opérations usuelles sur les ensembles : union, intersection,
différence, complémentaire. À cela s’ajoute la concaténation des langages, définie par extension de la
concaténation des mots :
Définition (Concaténation) : La concaténation est une opération sur les mots, mais peut être étendue aux
langages (sous-ensembles du monoïde1). Ainsi, si L1, L2  Σ* alors leur concaténation L1 . L2 est l'ensemble
{v.w | (v, w)  L1.L2}, c'est-à-dire l'ensemble des mots qui sont la concaténation d'un mot de L1 et d'un mot
de L2. Notation simplifiée : L1L2 = {uv t.q. u  L1 et v  L2}.

L’itération de cette opération sur un langage L permet d’obtenir les puissances de L : L0, L1, L2, …
Formellement, on définit par récurrence :

L0 = {ℇ} et n  N; Ln+1 = LLn

Enfin, on appelle fermeture de Kleene (ou l’étoile) du langage L, le langage :

L∗ = L

Notons que quel que soit le langage L, sa fermeture de Kleene L contient ℇ (puisque {ℇ}= L0  L*. En
particulier : {ℇ}  Ø*.
Exemple : Soient L = {ab, ba} et L’= {aa, b} deux langages sur {a;b}. Alors : LL’ = {abaa, abb,
baaa, bab}, L0 = {ℇ}, L1 =LL0=L{ℇ}= L, L2=LL1 = LL = {abab, abba, baab, baba}, etc.

Lemme 1. Soient A, B, et C trois langages sur un alphabet Σ. Alors :

 (AB)C = A(BC).
 (A ∪ B)C = AC ∪ BC.
 (A ∩ B)C ⊂ AC ∩ BC et l’inclusion réciproque est fausse en général.
 A ⊆ B ⇒ A∗ ⊆ B∗
 (A∗ )∗ = A∗
 (A ∪ B)∗ = A∗ ⋃ B∗

Preuve : Exercice.
Le miroir d’un langage L, noté LR, est l’ensemble des miroirs des mots de L.
Autrement dit : LR = {wR t.q. w  L}.

2.2 Langages réguliers

Supposons que le langage est un ensemble de chaînes, une chaîne est une séquence finie de
symboles. Les symboles eux-mêmes sont pris à partir d'un alphabet fini. Le langage Java est
l'ensemble de toutes les chaînes qui constituent les programmes Java valides, le langage des
nombres premiers est l'ensemble de toutes les chaînes de chiffres décimaux qui représentent des
nombres premiers, et le langage de mots réservés de C est l'ensemble de toutes les chaînes
alphabétiques qui ne peuvent être utilisés comme identifiants dans le langage de programmation C.

Les deux premiers de ces langues sont des ensembles infinis, le dernier est un ensemble fini. Dans
tous ces cas, l'alphabet est le jeu de caractères ASCII. Quand nous parlons des langages de cette

1
: Un monoïde est une structure algébrique consistant en un ensemble muni d'une loi de composition interne
associative et d'un élément neutre
façon, nous n'allons pas attribuer une signification à des chaînes, nous allons juste tenter de classer
chaque chaîne est-t-elle dans le langage ou pas. Pour spécifier certaines de ces langages
(éventuellement infinis) avec des descriptions finies, nous allons introduire la notation des langages
réguliers et expressions régulières.

2.2.1 Langages réguliers

Soit (Σ*) l’ensemble des parties de Σ*, c’est-à-dire l’ensemble des langages d’alphabet Σ.
L’union, la concaténation des langages et la fermeture de Kleene sont des opérations d’arités
respectives 2, 2 et 1 sur (Σ*). La classe des langages réguliers est définie inductivement à partir
de ces opérations et des atomes Ø, {ℇ}, {a} t.q a  Σ. Plus précisément :

Définition (Langage rationnel). Soit Σ un alphabet. Les langages rationnels ou réguliers sur Σ
sont définis inductivement par :
(a) {ℇ} et Ø sont des langages rationnels
(b) {a} t.q a  Σ est un langage rationnel
(c) si L1 et L2 sont des langages rationnels, alors L1.L2, L ∪ L , et L1* sont également des
langages rationnels.

Bien entendu, dans cette définition inductive on n’a le droit qu’à un nombre fini d’applications de la
récurrence (c).

Tous les langages finis sont rationnels, puisqu’ils se déduisent des singletons par un nombre fini
d’applications des opérations d’union et de concaténation. Par définition, l’ensemble des langages
rationnels est clos2 pour les trois opérations rationnelles (on dit aussi qu’il est rationnellement clos).

La famille des langages rationnels correspond précisément au plus petit ensemble de langages qui (i)
contient tous les langages finis, (ii) est rationnellement clos.

Un langage rationnel peut se décomposer sous la forme d’une formule finie, correspondant aux
opérations (rationnelles) qui permettent de le construire. Prenons l’exemple du langage sur Σ={0, 1}
contenant tous les mots dans lesquels apparaît au moins une fois le facteur 111. Ce langage peut
s’écrire : ({0}∪{1})* {1}{1}{1}({0}∪{1})* , exprimant que les mots de ce langage sont construits en
prenant deux mots quelconques de Σ* et en insérant entre eux le mot 111 : on peut en déduire que
ce langage est bien rationnel. Les expressions rationnelles / régulières définissent un système de
formules qui simplifient et étendent ce type de notation des langages rationnels.

2.2.2 Expressions rationnelles

En utilisant des symboles, l'alternance, la concaténation, epsilon, et la fermeture de Kleene nous

pouvons spécifier le jeu de caractères ASCII correspondant aux jetons lexicaux d’un langage de

2
Un ensemble S est clos par rapport à une loi * si seulement si l’application de cette loi sur les éléments de S produit
des éléments dans S.
programmation. Considérons d'abord quelques exemples:
 (0 | 1)* 0 : nombres binaires qui sont des multiples de deux.
 b * (abb*) * (a |ℇ) : chaînes des a et des b sans chaînes de a consécutive.
 (a | b) * aa (a | b) * : chaînes des a et des b contenant des chaînes de a consécutive.

En écrivant des expressions régulières, nous allons parfois omettre le symbole de concaténation ou
l'epsilon, et nous supposerons que la fermeture Kleene "se lie plus serré" que la concaténation, et la
concaténation se lie plus serré que l'alternance, de sorte que :
 ab | c signifié (a · b) | c, et (a|) signifié (| a |ℇ).
 [abcd] signifié (a | b | c |d), [b-g] signifié [BCDEFG], [b-GM-QKR] signifie
[bcdefgMNOPQkr]
 M? signifie (M |?), et M + signifie (M · M*).

Ces extensions sont pratiques, mais n’étend pas la puissance descriptive des expressions régulières:
Tout ensemble de chaine qui peut être décrite avec ces abréviations pourrait aussi être décrit par
juste l'ensemble de base des opérateurs. Tous les opérateurs sont résumés comment suit :

a Un caractère ordinaire représente lui-même.

ℇ La chaîne vide.
Une autre façon d'écrire la chaîne vide.
M|N Alternance, le choix de M ou N.
M·N concaténation, un M suivi par un N.
MN Une autre façon d'écrire concaténation.
M* Répétition (zéro ou plusieurs fois).
M+ répétition, une ou plusieurs fois.
M? Facultatif, zéro ou une occurrence de M.
[a-zA-Z] Jeu de caractères d’alternance.
. Une période correspond à n'importe quel caractère sauf retour à la ligne.
"a + *." Offre, une chaîne entre guillemets signifie littéralement la même.

Exemple 5 : Des expressions régulières pour certains jetons.

if IF
[a-z][a-z0-9]* ID
[0-9]+ NUM
([0-9]+"."[0-9]*)|([0-9]*"."[0-9]+) REAL
("\\"[a-z]*"\n")|(" "|"\n"|"\t")+ no token, just white
space
. error

La cinquième ligne de cette description reconnaît des commentaires ou des espaces, mais
l’analyseur ne retourne pas de jeton (no token), c’à’d qu’ils sont ignorés et l’analyseur lexical
reprend. Les commentaires commencent par deux antislash «\\ », ne contiennent que des caractères
alphabétiques, et se terminent par une nouvelle ligne.
Enfin, une spécification lexicale doit être complète, toujours correspondant à une certaine chaîne
initiale de l’entrée, nous pouvons toujours atteindre cet objectif en appliquant une règle qui
correspond à tout caractère unique (et dans ce cas, imprimer un message d'erreur « caractère illégal»
et continue). Ces règles sont un peu ambiguës. Par exemple, IF8 sera analysé comme un identifiant
unique ou deux jetons IF et 8? La chaine IF 89 commence avec un identifiant ou un mot réservé?

En générale, il y a deux règles de désambiguïsation importantes utilisées par les générateurs

lexicaux (JFlex, JavaCC, SableCC, ..):

Plus long correspondance (Longest match) : La plus longue chaîne initiale de l'entrée qui peut
correspondre à une expression régulière est considérée comme le prochain jeton.

Règle de priorité : Pour une plus longue chaîne initiale particulière, la première expression
régulière qui peut correspondre détermine son type de jeton. Cela signifie que l'ordre d'écrire des
règles d'expressions régulières a une signification.

Donc, IF8 correspond à un identifiant par la règle de la plus longue correspondance, et correspond à
un mot réservé (IF) par les règles de priorité.

Les expressions régulières sont un outil puissant et pratique pour définir les unités lexicales, c’est-a-
dire les constituants élémentaires des programmes. Mais elles se prêtent beaucoup moins bien à la
spécification de constructions de niveau plus élevé, car elles surviennent rapidement d’une trop
grande complexité.

De plus, il y a des chaînes qu’on ne peut pas décrire par des expressions régulières. Par exemple, le
langage suivant (supposé infini) : {a, (a), ((a)), (((a))), ...} ne peut pas être défini par des
expressions régulières, car ces dernières ne permettent pas d’assurer qu’il y a dans une expression
de la forme autant de parenthèses ouvrantes que de parenthèses fermantes. On dit que les
expressions régulières ne savent pas compter.

Une solution pour ces problèmes qui peut être facilement mis en œuvre par un programme est le
formalisme des automates finis.

3. Automates finis

Nous avons vu que les expressions régulières permettent de générer ce qu’on a décidé d’appeler les
langages réguliers. Les automates que nous allons introduire ici sont des “machines” permettant de
reconnaitre exactement ces langages. En d’autres termes, l’ensemble des langages acceptés par
automate fini coïncide avec l’ensemble des langages réguliers.

Définition : un Automate fini (AF) A est la donnée < Σ, Q, Q0, QF,  > où :
 Σ est un alphabet appelé ici alphabet d’entrée
 Q est un ensemble fini dont les éléments sont appelés les états de A
  Q0  Q est un ensemble fini des états initiaux (marqué par flèche entrant
entrant)
 QF  Q est l’ensemble des états d’acceptation (ou états terminaux) ()
   Q x (Σ  ) x Q est l’ensemble des transitions de l’automate.

On représente souvent un automate par un graphe valué (au sens où chaque arc est étiqueté par une
valeur, ici une lettre de Σ ou ). Q:
Q représente l’ensemble des
es sommets du graphe, ((Σ  ) celui des
étiquettes et  l’ensemble des arcs.
Un état sera noté par: , une flèche par: , un état initial par:, et un état final par: .
Ainsi, une transition (qi, a, qj ) see représente par une flèche de qi à qj, munie d'une étiquette a :

Définition. Un automate fini déterministe (AFD)

(A est un automate :
 avec un unique état initial q0
 à partir de chaque état, il y a au plus une transition d’étiquette donnée.

3.1.1 Comment fonctionne les AFD

L’automate fini déterministe est
st un modèle de calcul rudimentaire qui peut être représenté par le
schéma de la
Figure 2.

Figure 2 Une machine de reconnaissance

 On commence
ommence par l'état initial q0 et le mécanisme de lecture de l’entrée
ntrée aux symboles le plus
à gauche de la chaîne d'entrée.
d' Par exemple:
xemple: Pour la chaîne d'entrée a0a1a2 ... an, les
symboles sont entrés de gauche à droite a0 (en 1er) et an (en dernier.)
 Lors de chaque mouvement, l’entrée avancee d'une position vers la dro droite et un symbole est
consommé.
 Lorsque "EOS" (fin de symboles) est atteint, la chaine est acceptée si l'automate est dans
l'un des états finaux.

Fonction de transition
Exemple : Soit l’automate A : < Σ={a,b},
Σ={a,b} Q={q0, q1} , q0, QF={ q0},  > où laa fonction de transistion
est
est donnée par la table de transition suivante :
On a (q0, a) = q1 q0, q1  Q, donc Si l’AF est en état q0, et le symbole d’entrée courant est un
« a », l’AF va à l’état q1.

L'automate A permet de reconnaître le langage définie sur {a, b} et qui consiste de mots contenant
un nombre paire de a. Par exemple, les mots aa, aba et aaaba seront reconnus par A tant dis que ab
et ababa seront rejetés.

3.1.2 Configurations et mouvement

Soit A = < Σ, Q, q0, QF,  > un AF, on appelle configuration la paire (q, w)  Q x Σ * où q représente l'état
courant de l'unité de contrôle et w est la partie du mot à reconnaître non encore lue. Le premier symbole
de w (le plus à gauche) est celui qui se trouve sous la tête de lecture. Si w = ℇ alors tout le mot à été lu.

 La configuration initiale est (q0, w) où w est le mot à reconnaître

 La configuration d'acceptation est (q, ℇ) avec q  QF
 Un mouvement est défini par la transition (q, xu) ⊢(q', u) si q'   (q, a).

Pour un x  Σ*, (xw, q) ⊢ (w, q') dénote n transitions successives et (xw, q) ⊢∗ (w, q') indique  n
≥ 0 tel que (xw, q) ⊢ (w, q') c'à'd qu'à partir du mot xw à l'état q on peut attendre le mot w à l'état
q' après n mouvements.

Exemple 6 : On s’intéresse ici à reconnaitre le mot ababc par l’automate présente par la figure
suivante :
- La configuration initiale est (q0 , ababc)
- La configuration d’acceptation est (q2, b)
- Premier mouvement (q0, ababc) |- (q1, babc)
- Le mot ababc est reconnu après 5 mouvements.

3.1.3 Langages reconnaissables

Définition (Etat accessible.) On dit qu’un état q' de Q est accessible à partir d’un état q si  w Σ*
 n ≥ 0 tel que (w, q) ⊢ (w, q').

Définition. (Ensemble clos.) On dit qu’un ensemble C d’états de Q est clos si les seuls états
accessibles à partir d’un état de C appartiennent à C.

Définition (Etat absorbant.) On dit qu’un état q de Q est absorbant si  a  Σ t.q (a, q) ⊢ (, q).

Exemple 7 : soit l’automate représenté par le graphe suivant :

Les états q0 et q2 sont absorbants, l’état q1 n’est pas accessible à partir de q2, et les ensembles {q1,
q2}, et {q2} sont des clos alors que et l’ensemble {q0, q1} n’est pas un clos.

Définitoion : Un langage reconnu par un automate A, noté L(A), est l'ensemble de tous les mots
acceptés par A. L(A) = {w  *: *(q0, w)  QF} et L~ (A) = {w  *: *(q0, w)  QF}.
Théorème de Kleene: Tout langage reconnu par un automate fini déterministe est régulier, et
réciproquement.

Autrement dit: Le langage accepté par tout automate fini déterministe est régulier. Tout langage
régulier est accepté par un automate fini déterministe.
Exemple de langages qui ne sont pas réguliers
L'ensemble des palindromes sur Σ={a,b}: L={a,b,aa,bb,aba,bab,aaa,bbb,aaaa,baab,abba, …}
L'ensemble des mots qui contiennent autant de a que de b: L={ℇ,ab,ba,aabb,abab,bbaa,abba,...}

3.1.4 Automate non déterministe

Un automate fini non-déterministe (AFN) est un automate tel que dans un état donné, il peut y
avoir plusieurs transitions avec le même symbole ou une transition avec le symbole vide ℇ. Le
fonctionnement d'un tel automate n'est donc pas totalement “ déterminé ”, car on ne sait pas quel
état l'automate va choisir.

Exemple 8 : l’automate suivant n’est pas déterministe car à partir de l’état 0 et de la

lecture du symbole ‘b’ l’automate peut rester dans l’état 0 que de passer à l’état 1.

Les automates non-déterministes permettent de modéliser facilement les cas complexes. Ils peuvent
être convertis en des automates finis déterministe. Ces derniers peuvent être exponentiellement plus
grands que les automates non déterministes dont ils sont issus.

Définition : Un automate fini Non Déterministe (AFN) est un quintuple (, Q, q0, QF, ) :
- un alphabet (fini) ;
- Q, un ensemble fini d'états ;
- q0 un état initial ;
- QF, un ensemble fini des états finaux (accepteurs).
-  : Q x  Σ  {}  Q, une fonction de transition;

Exemple 9 : Un automate qui reconnait les mots définis sur l’alphabet {a, b} qui finissent par
soit aa ou ab est reprsenté par l’operateur de transition est donné formellement par :

Exemple 10 : Considérons l'AFN avec -transitions suivant :

Cet automate accepte le mot a car on a le chemin

3.1.5 Automates équivalents

Définition. Deux automates sont équivalents s'ils reconnaissent le même langage.

Exemple : Les deux automates A et A’ suivants sont équivalents. Ils reconnaissent l'ensemble de
tous les mots qui terminent par bb.

A : Automate non-déterministe A’ : Automate déterministe

Dans un automate fini non-déterministe, 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 allant
d’un état initial à un état final.
La lecture d’un mot dans un automate non-déterministe n’est pas forcément unique. Ainsi, pour un
mot accepté par un automate, il peut exister d’autres chemins issus de q0 mais ne menant pas à un
état final.

Théorème. Si un langage est reconnu par un automate fini, alors il est également reconnu par un
automate fini déterministe.

Sketch de Preuve:
 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 par l’algorithme
de détermination.
 Il resterait à prouver formellement que le nouvel automate B accepte exactement les mots
acceptés par A

Un automate non-déterministe peut toujours être transformé en un automate déterministe équivalent

(qui reconnait le même langage)

3.1.6 D'un AFN à l’AFD équivalent

Soit A = (Σ, Q, q0, QF, ) un automate fini non-déterministe sans -transition, on construit
l’automate fini déterministe B = (Σ, Q’, q0’, QF’, ’) selon l’algorithme suivant (Q’ sera alors un
sous-ensemble de (Q)) :
 ’  ∅
 q0’  {q0}
 Q’  {q0’}
 pour tout état q’ de Q’ non encore considéré faire pour toute lettre s de Σ faire
o q"  { qi / il existe qj  q’ et qi  Q tels que (qi, a, qj)   }
o ’  ’ ∪ {(q’, a, q") t.q. « a » symbole de la ligne précédente}
o Q’  Q’ ∪ {q"}
 QF’  {q’ Q’ tels que Q’ ∩ QF ≠ ∅}
Exemple 11.

Vu de loin, l'algorithme peut faire un peu tordu mais en fait c'est simple. Nous allons déterminiser
cet automate :

Faire la table de transition de l'automate

La première des étapes est construire la table de transition de l'automate non-ddéterministe que nous
avons sous les yeux. Ce n’est pas long mais il faut faire
faire attention à bien la remplir. Plus l'automate
est important, plus nous avons tendance
ndance à zapper des transitions.
transitions

La table a en lignes chaque état de l'automate, et en colonne, les

les transitions. La table de transition
est le suivant :
_ a b
0 {1,2} -
1 - {1,2}
2 {2} -

Nous allons pouvoir faire celle de notre automate déterministe maintenant.

Déduire la table de transition de l'automate déterministe

Les états de l'automate déterminiséminisé ne seront plus de simples états mais des ensembles d'états ;
ceux-ci
ci sont détaillés lorsqu'ils sont visités depuis un état visité plus haut. Nous commençons par
détailler l'état (ou les états) initial, ici 0.
_ a b
0 {1,2} -

Il suffit de reprendre la ligne de notre table de tout à l'heure.

Nous remarquons qu'il y a un ensemble d'état ({1,2}, ici tout seul) qui n'est pas détaillé dans la
table. Nous s'en chargeons donc promptement : pour chaque état de l'ensemble à détailler, nous
allons faire l'ensemble
emble de tous les états où quels nous pouvons aller avec la transition.
_ a b
0 {1,2} -
{1,2} {2} {1,2}

Ici par exemple, nous détaillonsons {1,2} : pour la transition a, nous ajoutonsons au résultat les états
atteignables par a pour 1 (ici aucun) et pour 2 (ici {2}). Le résultat est donc {2}. Nous faisons pareil
pour b : depuis 1 on peut aller à 1 ou 2 (donc {1,2}), et depuis 2, on ne peut aller nulle part (la case
est vide), le résultat est donc {1,2}.

Nous construisons les lignes suivantes en fonction des nouveaux états découverts : ici le seul
nouveau est {2} (nous venons de définir l'autre, {1,2})
_ a b
0 {1,2} -
{1,2} {2} {1,2}
{2} {2} -

Nous remarquons qu'il n'y a pas de nouveaux états ou d'autres pas encore définis, donc nous avons
fini, nous avonss notre automate déterministe.
déterministe Nous pouvons le tracer assez facilement :

Deux remarques :

 la première est concernant l'ensemble vide {} qui concerne les cases vides de la table (par ex
on ne va nulle part de 0 par b, donc on peut faire une flèche b vers
rs un état {}). Mais ce n'est
pas forcément demandé.
 La seconde concernant les états finaux : c'est très simple, tous les ensembles d'états
contenant un état final ou plus sont maintenant des états finaux : ici on avait l'état 2 final,
donc les ensembles {2}
2} et {1,2} sont finaux.
Exemple 12. Soit l’automate (un peu plus massif)) définit par la table de transition suivante :

_ a b c
A {C,D} {A,B} {C}
B {A,C} {B} -
C {C,D} - -
D - {D} {A}

Nous allons construire la table de transition pour

p AFD. Commençons avec l'état initial A :

_ a b c

{A} {C,D} {A,B} {C}

Ici,
ci, tous les états obtenus sont indéfinis, donc tous nouveaux. Nous allons donc définir {D,C},
{A,B} et {C}.
 _ a b c
{A} {C,D} {A,B} {C}
{C,D} {C,D} {D} {A}
{A,B} {A,C,D} {A,B} {C}
{C} {C,D} - -

Nous allons augmenter la table par les deux

d nouveaux états : {D} et {A, C, D}
_ a b c
{A} {C,D} {A,B} {C}
{C,D} {C,D} {D} {A}
{A,B} {A,C,D} {A,B} {C}
{C} {C,D} - -
{D} - {D} {A}
{A,C,D} {C,D} {A,B,D} {A,C}
De même pour les nouveaux états {A,B,D} et {A,C}

_ a b c
{A} {C,D} {A,B} {C}
{C,D} {C,D} {D} {A}
{A,B} {A,C,D} {A,B} {C}
{C} {C,D} - -
{D} - {D} {A}
{A,C,D} {C,D} {A,B,D} {A,C}
{A,B,D} {A,C,D} {A,B,D} {A,C}
{A,C} {C,D} {A,B} {C}

C'est fini, nous avons notre table. Les

Les états finaux sont ceux contenant C (seul état final de
l'automate de départ). Le graphe se fait assez facilement en suivant la table :
4. Translation des expressions régulières en automates
Les automates non déterministes sont très utile, car il est facile de convertir un (statique, déclarative)
expression régulière en un (simulable, quasi-exécutable) AFN.
L'algorithme de conversion transforme chaque expression régulière en un AFN avec une queue
(arête de départ) et une tête (état de fin). Par exemple, le seul symbole expression
régulière « a » convertit à la AFN
L'expression régulière « ab » de la concaténation de deux expressions régulières « a » et « b », est
faite en combinant les deux AFN, en accrochant la tête de a la queue de b. La machine résultante
possède une queue marqué par a en tête dans laquelle coule l’arête de b.
En général, toute expression régulière R aura un certain AFN avec une
queue et la tête:

Nous pouvons définir la traduction des expressions régulières en AFNs par induction. Soit
l'expression est primitif (un seul symbole ou ℇ) Ou il est fabriqué à partir des expressions plus
petites. De même, l’AFN sera primitif ou fabriqués à partir de petits AFN.

La Figure 3 présente les règles pour traduire des expressions régulières en automates finis non-
déterministes.

a ℇ M*

M|N M.N

Figure 3 : Règles pour traduire des expressions régulières en automates

Nous allons illustrer la méthode de translation sur quelques-unes des expressions. La Figure 4
présente les automates permettant la reconnaissance des jetons de l’exemple 5 (jetons IF, ID, NUM,
et Error). Chaque expression est traduite en un AFN.

L’automate résultant après un certain regroupement des états de l’AFN équivalents est illustré à la
Figure 5. Nous pouvons maintenant chercher l’automate déterministe équivalent. Cependant, cet
automate possède des є –transitions, la chose que nous n’avons pas considérer dans notre méthode
de détérminisation de d’un AFN. Afin de détérminiser un AFN nous devons supprimer ces
transitions nulles. Pour ce faire, nous allons commencer tout d’abord par définir є –fermeture.
IF NUM

REAL ID

White Error
Space

Figure 4 : automates permettant la reconnaissance des jetons de l’exemple 5

Figure 5 : Quatre expressions régulières convertis en un AFN

4.1 є –Fermeture
Soit A = (Σ, Q, QF, q0, δ) un AFN avec des є –transitions, et soit S une partie quelconque de Q. Le
є-fermeture de S est l'ensemble є (s) défini comme suit :
 Chaque élément de S est un élément de є (S);
 Pour tout q  є (s), chaque élément de δ (q, є) est en є (S);
 Aucun autre élément de Q est dans є (S)

En termes simples, є (S) est l’ensemble de tous les états qui peuvent être atteints à partir des états S,
sans donner (consommer) aucune symbole d’entrée.

Exemple 13
Soit l’AFN suivant :
є (q0) = {q0, q1, q2}, є (q1) = {q1, q2}, є (q2) = {q2},
є ({q1, q2} = є (q1)  є (q2) = {q1, q2}  {q2} = {q1, q2}

4.2 Élimination des є-transitions

Dans un automate, si l’on se trouve dans un état q quelconque comportant des є -transitions, on se
trouve en réalité dans le même temps dans chaque état accessible q’ à partir de q en suivant les є-
transitions. En effet, soit le w le mot étiquetant le chemin de q0 (état initial) à q, alors w. є (= w) est
le chemin étiquetant le chemin de q0 à q’.
L’élimination des є-transitions est effectuée en quatre étapes :
1. Augmentation des transitions ;
2. Propagation des états finals ;
3. Suppression des є-transitions ;
4. Élimination des états inaccessibles.

On construit un nouvel automate où il existe une transition entre l’état qi et l’état qj étiqueté par x
s’il existe un état qk tel qu’il existe une suite d’є-transitions de qi à qk et qu’il existe une transition x
de qk à qj.

Exemple 14 : Soit l’automate AFN pour (a | bc*) :

 Si on augmente les transitions à partir de l’automate donné en exemple ci-dessus, on obtient

le nouvel automate suivant :

 Un état est final s’il existe une suite d’ є-transitions qui mène à un état final.
 On supprime les -transitions.

On supprime les états inaccessibles à partir de l’état initial.

On obtient comme résultat final l’automate défini à partir de l’expression régulière : a | bc*.

Si nous nous appliquons cette méthode sur l’automate de la Figure 5 (obtenu par regroupant des
automates calculer à partir des expressions régulières des jetons IF, ID, NUM, Error) nous allons
obtenir l’automate présenté dans la Figure 6.

Figure 6 : Un AFN converti à AFD

5. Implantation d’un analyseur lexical

A Faire !

6. Exercices

1. Démontrez, à l'aide de la définition inductive des langages réguliers, que les deux langages
suivants sont réguliers (l'alphabet considéré est Σ = {0, 1}):
1. L'ensemble des mots composés d'un nombre arbitraire de 1, suivis de 01, suivis d'un
nombre arbitraire de 0.
2. L'ensemble des nombres binaires impairs.
2.
3. Ecrire un programme java qui fait l'analyse lexical pour le code de l'exemple 1.