Automates

3

0

4

Fig. 1.5 – Un automate non déterministe pour

les mots contenant la chaˆıne 010

Deux automates sont dits équivalents s’ils recon-

naissent le même langage. On démontre que tout

automate non déterministe est équivalent à un au-

tomate déterministe, comme illustré sur la figure

1.6.

Toutefois, déterminiser un automate peut

avoir un coût prohibitif puisqu’on connaˆıt des

exemples d’automates non déterministes à n

états dont le plus petit équivalent déterministe

possède 2n états. Fort heureusement, cette situa-

tion extrême se rencontre rarement en pratique.

a, b

1

b

1

a

a

b

a

2

2

3

a, b

b

a

b

3

a

4

Fig. 1.6 – Un automate non déterministe et un

automate déterministe équivalent

6 Automate minimal

Si on dispose d’un automate déterministe re-

connaissant un langage L, on peut éliminer tous

les états inaccessibles à partir de l’état initial et

tous ceux à partir desquels on ne peut pas at-

teindre un état final. On obtient ainsi la version

émondée de l’automate, qui est équivalente à l’au-

tomate de départ.

On peut ensuite minimiser l’automate. Cette

opération consiste à identifier deux états p et

q lorsque ce sont exactement les mêmes mots

qui permettent d’aller de p à un état final et

de q a un état final. L’automate obtenu apres

cette opération, appelé automate minimal de L,

est encore équivalent à l’automate de départ.

On démontre que parmi tous les automates

déterministes reconnaissant L, l’automate mini-

mal est celui qui possède le plus petit nombre

d’états.

7 Expressions rationnelles

Si on connaˆıt un automate déterministe recon-

naissant un langage L, on peut facilement tester

si un mot appartient ou non à L. En revanche,

il n’est pas toujours facile de décrire les mots

de L. Les expressions rationnelles, appelées aussi

expression régulière, permettent de résoudre ce

problème.

(bab + ca)∗(b + ε)

L’expression (a + b)∗a+

∗c

est un exemple d’expression rationnelle sur l’al-

phabet {a, b, c}. Comme on le voit, c’est une forme

d’expression algébrique utilisant les lettres de l’al-

phabet, le mot vide, un opérateur +, un opérateur

produit et une sorte d’exposant, noté ∗.

`

´

Le symbole + désigne le ou logique. Autre-

ment dit, L + L′ représente l’union des deux lan-

gages L et L′, formée des mots qui sont dans L

i

i

i

i

i

i

4

“Automates” — 2006/4/16 — 11:20 — page 4 — #4

i

i

ou dans L′. Le produit de L et L′, noté LL′, est

formé des mots qui sont produits d’un mot de L

et d’un mot de L′.

L + L′ = {u ∈ A∗ | u ∈ L ou u ∈ L′}

LL′ = {uu′ | u ∈ L et u′ ∈ L′}.

Pour L = ab + abc et L′ = ab + cab, on trouve L +

L′ = ab+abc+cab et LL′ = abab+abcab+abccab.

Comme pour les mots, on peut définir les puis-

sances d’un langage en posant L0 = {ε}, L1 = L,

L2 = LL, etc.

L’étoile d’un langage L, notée L∗, est l’union

de toutes les puissances de L :

L∗ =

n

L

.

n>0

X

De façon équivalente, L∗ est formé de tous les

mots qui peuvent s’écrire comme produit d’un

nombre arbitraire de mots de L.

les

Les langages rationnels sont

langages

décrits par des expressions rationnelles. Si A =

{a, b}, les langages suivants sont rationnels : l’al-

phabet A, qui peut s’écrire a + b,

l’ensemble

A∗ = (a + b)∗ formé de tous les mots sur l’al-

phabet A, le langage A∗aA∗ des mots contenant

la lettre a, le langage (A2)∗A des mots de lon-

gueur impaire, le langage (ab)∗ formé des mots

ε, ab, abab, ababab, . . ..

Les expressions rationnelles sont d’un usage

courant en informatique. Ainsi, les éditeurs vi et

emacs d’Unix utilisent des expressions rationnelles

pour la recherche d’expressions. Une syntaxe voi-

sine est utilisée par les analyseurs lexicaux (lex)

ou les langages de script, tels que Perl ou PHP.

8 Le théorème de Kleene

Le théorème de Kleene, clef de voûte de la

théorie des automates, affirme qu’un langage est

rationnel si et seulement s’il est reconnaissable.

De plus, la démonstration de ce théorème four-

nit un algorithme pour passer d’un automate à

une expression rationnelle et vice-versa. Le lecteur

pourra par exemple vérifier que le langage accepté

par l’automate de la figure 1.1 est le langage ra-

tionnel (aa∗ba)∗aa∗(b + ε).

Le théorème de Kleene a plusieurs consé-

quences importantes, notamment le fait que l’in-

tersection de deux langages

rationnels et la

différence de deux langages rationnels sont encore

des langages rationnels.

Pour illustrer la portée de ce dernier résultat,

cherchons une expression rationnelle représentant

le langage L des mots ne contenant pas la chaˆıne

010. Pour l’obtenir, on part de l’automate de la

figure 1.5, qui reconnaˆıt le langage des mots qui

contiennent la chaˆıne 010. La figure 1.7 donne un

automate déterministe équivalent.

Automates finis

0, 1

1

3

0

4

1

1

0

0

2

1

Fig. 1.7 – Déterminisation de l’automate

En échangeant les états finaux et non finaux, puis

en supprimant l’état 4 devenu inutile, on obtient

un automate déterministe qui reconnaˆıt L (cf. fi-

gure 1.8).

1

1

0

0

2

1

3

1

Fig. 1.8 – Un automate pour L

Il reste alors à convertir cet automate en expres-

sion rationnelle pour résoudre notre problème.

Plusieurs réponses sont possibles, par exemple

(1 + 00∗11)∗(ε + 00∗ + 00∗1).

9 Automates séquentiels

Les automates séquentiels sont des automates

déterministes qui produisent un mot de sortie. Ils

permettent de réaliser plusieurs transformations

familières telles que l’addition des entiers, la mul-

tiplication par une constante, divers codages et

décodages, le « couper-coller » dans un texte, etc.

Dans un automate séquentiel, l’état initial et

les états finaux sont étiquetés par des mots et les

transitions sont étiquetées par des couples formés

d’une lettre et d’un mot séparés par une barre ver-

ticale. La lettre figurant à gauche de la barre est

lue en entrée, et le mot figurant à droite de la barre

est alors produit en sortie (voir figure 1.9). Le mot

de sortie associé à un mot d’entrée s’obtient en li-

sant l’entrée depuis l’état initial et en produisant

les sorties spécifiées par les transitions, y compris

celles données au début par l’état initial et à la

fin par l’état final. Si on ne parvient pas dans un

état final, aucune sortie n’est produite.

1|1

0

1

0|ε

0|0

2

0|01

1|ε

00

3

1|011

Fig. 1.9 – Un automate séquentiel

i

i

i

i

i

i

“Automates” — 2006/4/16 — 11:20 — page 5 — #5

Automates séquentiels

5

i

i

Considérons l’automate séquentiel de la figure 1.9

et prenons 1001101 comme mot d’entrée. En par-

tant de l’état initial 1, et en lisant le mot de gauche

à droite, on parcourt le chemin :

0

−→ 1

1|1

−→ 1

0|ε

−→ 2

0|0

−→ 2

1|ε

−→ 3

1|011

−→ 1

0|ε

−→ 2

1|ε

−→ 3

00

−→

3

La sortie est obtenue comme produit des mots de

sortie 0, 1, ε, 0, ε, 011, ε, ε, 00, soit 01001100.

Comme pour les automates déterministes, on

peut minimiser un automate séquentiel, bien que

l’algorithme soit plus délicat à mettre en place.

Une fonction est dite séquentielle si elle peut être

réalisée par un automate séquentiel. Un résultat

essentiel assure que la composition de deux fonc-

tions séquentielles est séquentielle.

Un automate séquentiel est dit lettre à lettre

si les mots de sortie de chaque transition sont des

lettres. Un automate de Mealy est un automate

lettre à lettre dont l’état initial et les états fi-

naux sont étiquetés par le mot vide, ce qui signifie

en pratique que l’on peut ignorer ces étiquettes.

Un automate de Moore est une variante d’au-

tomate séquentiel dans laquelle les sorties sont

liées aux états traversés et non aux transitions.

On peut démontrer que tout automate de Moore

peut être simulé par un automate de Mealy et

réciproquement.

La figure 1.10 représente un automate

séquentiel lettre à lettre qui permet de réaliser la

multiplication par 3 des entiers représentés sous

forme binaire inversée. Comme son nom l’indique,

la représentation binaire inversée est obtenue en

lisant de droite à gauche la représentation binaire

usuelle. Dans le jargon des informaticiens, c’est

la représentation binaire dans laquelle le bit de

droite a le plus fort poids.

0|0

0

ε

1|1

0|1

1|0

0|0

1

1

1|1

2

01

Fig. 1.10 – Un automate séquentiel lettre à lettre

pour la multiplication par 3

Par exemple, le mot 1011 est la représentation bi-

naire inversée du nombre 20 +22 +23 = 1+4+8 =

13. Or 13 × 3 = 39 et 39 = 20 + 21 + 22 + 25 dont la

représentation binaire inversée est 111001, ce qui

est bien la sortie obtenue en lisant 1011 en entrée

dans l’automate séquentiel de la figure 1.10.

L’addition des entiers est aussi une opération

séquentielle. Pour la réaliser, on écrit les en-

tiers n et m en binaire inversé et on rajoute

éventuellement des zéros pour que les deux

représentations aient la même longueur. Par

exemple, si n = 22 et m = 13, on prend pour n la

représentation 01101 (car 2 + 4 + 16 = 22) et pour

m la représentation 10110 (car 1 + 4 + 8 = 13). On

considère le couple (01101, 10110) comme un mot

0 ) , ( 0

sur l’alphabet

obtenu en su-

perposant les deux représentations et en lisant

˘

les colonnes : ( 0

1 ) ( 0

1 ) ( 1

0 ). L’automate qui

réalise l’addition est représenté sur la figure 1.11.

Il a pour alphabet de sortie {0, 1}. Les états 0 et 1

correspondent respectivement a l’absence et a la

présence d’une retenue.

1 ) , ( 1

1 )

( 0

0 ) , ( 1

1 ) ( 1

0 ) ( 1

¯

( 0

0 ) |0

( 0

1 ) |1

( 1

0 ) |1

ε

ε

0

( 1

1 ) |0

( 0

0 ) |1

1

1

( 0

1 ) |0

( 1

0 ) |0

( 1

1 ) |1

Fig. 1.11 – Un automate séquentiel lettre à lettre

pour l’addition

Sur notre exemple, on trouve en sortie 110001, qui

code bien 35 = 1 + 2 + 32.

Un automate de Mealy suffit pour réaliser la

division d’un polynôme à coefficients dans Z/2Z

par le polynôme X 2 + X + 1. Pour cela, on asso-

cie à chaque mot a0a1 · · · an sur l’alphabet {0, 1}

le polynôme a0X n + a1X n−1 + a2X n−2 + . . . +

an−1X + an à coefficients dans Z/2Z.

0|0

1|0

0

1

0|0

1|0

1|1

X

0|1

0|1

X + 1

1|1

Fig. 1.12 – Division d’un polynôme à coefficients

dans Z/2Z par X 2 + X + 1

Le quotient de la division est donné par le mot

de sortie et le reste par l’état d’arrivée. Ainsi le

mot d’entrée 10001 donne en sortie le mot 00110

et arrive dans l’état X + 1, ce qui correspond à la

formule X 4 +1 = (X 2 +X +1)(X 2 +X)+(X +1).

Les exemples qui précèdent sont génériques.

Les automates séquentiels permettent de réaliser

la multiplication et la division entière par une

constante. Si on travaille sur des polynômes

à coefficients dans un corps fini,

la

multiplication ou la division par un polynôme

l’addition,

i

i

i

i

i

i

6

“Automates” — 2006/4/16 — 11:20 — page 6 — #6

i

i

Automates finis

constant peuvent être réalisées par des automates

séquentiels.

En revanche, ni

la multiplication, ni la di-

vision de deux entiers ne sont des opérations

séquentielles. De fait, la conception d’un circuit

électronique réalisant la multiplication de deux

entiers est beaucoup plus difficile que celle d’un

additionneur.

Voici un dernier exemple, de nature assez

différente des précédents. Un filtre à rebonds lit

une suite de bits commençant et finissant par 0 et

change chaque 0 en 1 s’il est encadré par des 1, et

chaque 1 en 0 s’il est encadré par des 0, les autres

bits étant inchangés. Ainsi, si le mot d’entrée est

01011010, la sortie sera 00111100. La figure 1.13

représente un automate séquentiel qui réalise un

filtre à rebonds.

0|0

0

0|0

1

ε

1|ε

0

4

0|ε

0|00

0|0

1|1

2

1|11

3

1|1

Fig. 1.13 – Un filtre à rebonds

Ce type de filtre est utilisé en traitement d’images.

Chaque ligne de l’image est constituée d’une suite

de bits. Les éventuelles imperfections de l’image,

dues a une mauvaise qualité du film ou a un défaut

de transmission peuvent être éventuellement cor-

rigées de cette façon.

10 Utilisation pratique des automates

Les automates interviennent souvent dans la

modélisation de problèmes concrets. C’est d’ail-

leurs un bon réflexe, face a un probleme discret

(i.e. ne faisant pas intervenir de nombres réels),

de commencer par regarder si une approche par

automate n’est pas envisageable. Le modèle s’ap-

plique même a certains problemes continus. Il est

vrai que les chaˆınes de Markov utilisées en proba-

bilité sont de proches parents des automates.

Nous présentons ci-dessous quelques applica-

tions pratiques des automates. Toutefois, nous ne

dirons que quelques mots de l’une des applica-

tions les plus importantes, la spécification et la

vérification de systèmes (électroniques ou infor-

matiques), car elle est traitée en détail au chapitre

£Automates et vérification£.

10.1 Analyse lexicale

Les automates finis sont utilisés en com-

pilation (voir chapitre £Compilateurs£) pour

constituer des analyseurs lexicaux, qui permettent

notamment de repérer les mots-clés d’un lan-

gage de programmation. L’automate de la fi-

gure 1.14, dans lequel les états finaux sont en

noir, reconnaˆıt un ensemble de mots-clés du

langage Java : do, double, final, finally,

this, throw, throws.

l

l

e

l

y

f

d

t

o

i

u

n

h

i

b

a

s

r

o

Fig. 1.14 – Mots-clés en Java

w

s

10.2 Modélisation de systèmes finis

On peut (au moins théoriquement !) utiliser

des automates pour modéliser des situations dans

lesquelles il n’y a qu’un nombre fini de confi-

gurations possibles. Par exemple, la figure 1.15

représente un modele tres rudimentaire de monte-

charge. Les états symbolisent les étages. Le monte-

charge est muni de deux boutons, D et M qui per-

mettent de descendre ou monter d’un seul étage à

la fois. Le bouton D est inactif au rez-de-chaussée,

de même que M au deuxième étage.

D

0

M

D

1

M

D

2

M

Fig. 1.15 – Un modèle de monte-charge

L’exemple qui suit repose sur une devinette

classique. Un passeur doit faire passer d’une rive

a l’autre un loup, une chevre et une salade. Tou-

tefois, son bateau ne peut transporter qu’un seul

passager en dehors de lui-même. Bien entendu, il

ne peut laisser le loup et la chèvre seuls sans sur-

veillance, sinon le loup mangera la chèvre. Même

chose pour le couple chevre-salade, car la chevre

rêve de manger la salade. Pouvez-vous aider le

passeur ?

On peut modéliser ce problème par l’automate

de la figure 1.16.

i

i

i

i

i

i

“Automates” — 2006/4/16 — 11:20 — page 7 — #7

Utilisation pratique des automates

7

i

i

∅

C

CP

P

L

C

S

CLP

C

L

CP S

C

S

CL

P S

LS

C

L

LP S

S

P

Fig. 1.16 – Le loup, la chèvre et la salade

Chaque état représente les protagonistes sur la

rive opposée. Ainsi l’état CP signifie et que la

chèvre et le passeur sont sur la rive opposée (et

que le loup et la salade n’ont pas encore traversé).

Comme le précise l’énoncé, certains états sont in-

terdits. L’état initial est ∅ et l’état final et CLP S.

Les actions possibles (qui constituent donc l’al-

phabet de l’automate) sont les suivantes :

(1) traverser seul (P)

(2) traverser avec le loup (L)

(3) traverser avec la chèvre (C)

(4) traverser avec la salade (S)

On obtient ainsi l’automate de la figure 1.16 qui

donne immédiatement les deux solutions les plus

courtes : CP LCSP C et CP SCLP C.

10.3 Modélisation de systèmes infinis

Les automates permettent aussi de modéliser

certains systèmes de taille non bornée, ou même

infinie. Ces techniques sont particulièrement uti-

lisées pour résoudre les problèmes d’analyse et

de vérification de protocoles (nécessité de satis-

faire certaines contraintes logiques, comme l’ab-

sence de blocage, ou l’exclusion mutuelle). Le

plus souvent, on utilise des automates travaillant

sur des mots infinis (voir chapitre £Automates

et vérification£), mais l’exemple ci-dessous utilise

uniquement des automates traditionnels.

Considérons un réseau de processus alignés

qui communiquent avec chacun de leurs voisins,

conformément à la figure 1.17.

1

2

3

4

5

6

. . .

Fig. 1.17 – Un réseau de processus

la configuration du système par un mot sur l’al-

phabet {T, N }, dont la i-ème lettre vaut T ou N

selon que le processeur i possède on non le témoin.

S’il y a k processeurs, la configuration initiale est

donc représentée par le mot du langage T N k−1.

On représente ensuite la transmission du

témoin par l’automate séquentiel de la figure 1.18.

On peut donc considérer cette opération comme

une fonction séquentielle τ : {T, N }∗ → {T, N }∗.

N |N

N |N

T |N

N |T

Fig. 1.18 – La transmission du témoin

La configuration du systeme apres n transmis-

sions de témoin s’obtient en itérant n fois la fonc-

tion τ à partir de la configuration initiale.

car

Cet exemple semblera peut-être élémentaire

au lecteur,

fonction

l’itération de

séquentielle se calcule ici sans difficulté. Mais

c’est loin d’être toujours le cas ! Considérons par

exemple l’automate séquentiel de la figure 1.19.

la

0|0

1|1

2

ε

1|1

0|ε

1

ε

1|0

3

01

0|0

0|1

4

1|0

1

1|1

Fig. 1.19 – Un automate séquentiel

0|0

5

ε

Si on utilise la représentation binaire inversée des

entiers, cet automate calcule une fonction f bien

connue des programmeurs, définie par :

f (n) =

si n est pair

n/2

3n + 1 sinon

(

Une conjecture célébre affirme que, partant d’un

entier quelconque n, on arrive toujours à 1 en

itérant f . Par exemple, en partant de n = 31, on

trouve la suite 31, 94, 47, 142, 71, etc., qui abou-

tit a 1 apres 106 itérations. La conjecture a été

vérifiée pour n 6 5,764 · 1017, mais n’est toujours

pas résolue à ce jour. Elle montre en tout cas que

l’étude de l’itération des fonctions séquentielles

présente des difficultés insoupçonnées.

Ces processus réalisent un calcul en se passant un

témoin, qui est initialement détenu par le proces-

sus 1. À chaque étape du calcul, un processeur

peut passer le témoin à son voisin de droite. Com-

ment formaliser ce système ? On peut représenter

10.4 Industries de la langue

Les automates sont très utilisés dans ce qu’on

appelle les industries de la langue :

informa-

tique linguistique, traitement des langues na-

turelles, correction orthographique automatique,

i

i

i

i

i

i

8

“Automates” — 2006/4/16 — 11:20 — page 8 — #8

i

i

Automates finis

génération automatique de texte, réalisation de

dictionnaires électroniques, etc.

L’automate non déterministe de la figure 1.20,

dû au linguiste Maurice Gross, indique l’ordre de

succession des particules préverbales en français

(sans tenir compte des élisions). Par exemple les

phrases je ne le lui ai pas donné ou il n’y en a ja-

mais ! sont correctes, mais la phrase il se le lui

est fait volé ne l’est pas... Afin d’alléger la fi-

gure 1.20, seules certaines particules préverbales

sont représentées. Pour les obtenir toutes, il suffit

d’opérer les substitutions suivantes :

je → je, tu, nous, vous, on, ce

me → me, te, nous, vous, ε

il → il, ils, elle, elles

le → le, la, les, ε

lui → lui, leur, ε

y → y, ε

ne → ne, ε

se → se, ε

en → en, ε

je

il

ne

le

lui

y

ne

me

le

en

ne

se

Fig. 1.20 – Suites de particules préverbales

Les automates sont également utilisés dans

la réalisation de dictionnaires électroniques. La

représentation la plus na¨ıve d’un dictionnaire

consiste à conserver la liste de tous les mots du

dictionnaire. Une structure d’arbre permet d’obte-

nir une représentation plus concise. Ainsi, l’arbre

de la figure 1.21 représente l’ensemble des mots

{bal, bals, ban, bans, do, don, dons, doux, pal,

pals, pan, pans}. Mais l’utilisation d’un automate

(voir figure 1.22) donne une représentation beau-

coup plus compacte.

Le gain en place peut être très important.

Pour un dictionnaire de Scrabble anglais,

la

représentation par arbre nécessite 117 150 nœuds

et 780 kilo-octets de mémoire. La représentation

par automate nécessite seulement 19 853 états et

175 kilo-octets de mémoire, soit un gain de près

de 80%.

Pour le Dictionnaire électronique des formes

fléchies du français (DELAF) réalisé par les lin-

guistes de l’université de Marne-la-Vallée, qui

contient 802009 entrées

sur un alphabet de

90 lettres (minuscules et majuscules accentuées,

chiffres, et autres signes), la représentation par

arbre nécessite 2203261 nœuds, alors que l’auto-

mate minimal ne possède que 273716 états.

De plus, on dispose d’algorithmes très efficaces

pour les opérations de recherche et de mise à jour

pour ces dictionnaires électroniques. Si on dispose

d’un dictionnaire sous forme d’automate, on peut

ensuite facilement réaliser un programme informa-

tique champion du monde de Scrabble...

B

D

P

A

O

A

L

N

N

U

L

N

S

S

S

X

S

S

Fig. 1.21 – Représentation par arbre

B

P

D

A

O

L

N

N

U

S

X

Fig. 1.22 – Représentation par automate

10.5 Recherche d’information

Tout ce qui concerne l’analyse de textes et

l’extraction d’information fait grand usage des

automates. Les automates interviennent souvent

dans la conception d’algorithmes de recherche

d’information. Nous nous contenterons ici de

décrire le principe de la recherche dans un texte,

dans lequel les automates interviennent de façon

naturelle.

Supposons que l’on cherche à déterminer si la

chaˆıne ada apparaˆıt dans le texte abracadabra.

Cela revient à tester si le mot abracadabra ap-

partient au langage A∗adaA∗. Comme ce langage

est rationnel, il suffit de trouver son automate mi-

nimal, puis de vérifier que le texte est bien accepté

par cet automate.

Plus généralement, rechercher un mot u dans

un texte conduit à calculer l’automate minimal

du langage A∗uA∗. Si n est la longueur du mot

i

i

i

i

i

i

“Automates” — 2006/4/16 — 11:20 — page 9 — #9

Extensions de la notion d’automate

9

i

i

u,

il est facile de construire un automate non

déterministe à n + 1 états pour ce langage (voir la

figure 1.5, pour u = 010). Et, chose remarquable,

l’automate minimal de ce langage possède lui aussi

n+1 états. La figure 1.7 illustre cette construction

pour la chaˆıne 010.

10.6 Autres applications

Citons également la manipulation d’images

parmi les applications récentes. La compression,

et les transformations usuelles telles que rota-

tions, translations, homothéties peuvent en effet

être réalisées par des automates séquentiels appro-

priés. N’oublions pas la théorie de la commande

et du contrôle, où certains algorithmes récemment

développés sont entièrement basés sur les auto-

mates. En théorie des jeux, dont les applications

sont assez diverses, certaines st...