mates non déterministes et l' uni cité du
chemi n des automates déterministes. En
particulier, un résultat dû à Valentin M.
Antimi rov permet de co nstruire, à partir d' une expression rationnelle à n lettres,
un automate non nécessaireme nt déterministe à 11 + 1 états au pire qui le reconnaît. Un tel automate est appelé awomate
aux termes dérivés.
Parmi tous les auto mates qui reconnaissent le même langage, i I en ex iste
un unique, déterministe, à nombre d'états
minimal, appe lé ... automate minimal.
De plus , cet automate est ca lcul ab le
efficacement .
Les langages contenant un nombre fini
de mots sont rationnels puisque la somme
de tous les mots d'un tel langage consti -
tue une express ion rationnelle finie qui
le dénote . Le dictionnaire électronique
des formes fléchies du français , réa li sé
par les lin g ui stes de l' unive rsité de
Marne-la-Vallée, contient huit cent deux
mille neuf mots sur un alphabet de quatrevingt-dix lettres (minu scul es et maj uscules accentuées, chiffres et autres signes).
Sa représe ntati on par arbre lex icographique nécessite 2 203 26 1 nœuds, tandis que l' a ut o mate minim a l le
reconnaissant ne possède que 273 716
états. Les automates constituent donc
un exce llent moyen de compresser l' informat ion contenue dans un di ctionnai re, et donc d'accepter des mots validés
ou rejetés dans une version électronique
du jeu de Scrabble par exempl e.
Ain si, ces mac hines très simpl es permettent de décrire une vaste classe de langages. Et c'est ce qui est à la base de la
co mpl ex ité algorithmique : savoi r ce
que l' on peut décrire à partir de ressou rces limitées, ou réciproquement
tro uver la capac ité de ca lcul suffi sante
pour répondre à un problème donné. À
note r que si les automates fini s peuvent
être vus co mme des programmes qui
B
POUR L'INFORMATIQUE
R
s
~ 111J--- -
·
~ -f - - --· s
s
, __ __ , ,___ o _ ~ -•~--•
u
( }---- ·
p
D
c
X
s
~ 111J--- -
·
~ . . ..___ __ .
s
i-----------1 ':·
O
U
Une représentation par arbre lexicographique.
Une représentation équiva lente par automates.
prennent en entrée un mot et retournent
O ou I selon s' il est accepté ou rejeté, il
en ex iste une généra li sation (les transducteurs finis) qui transforme l'entrée en
une sorti e sur un autre alphabet , ce qui
a des appli cations en compilation , en
reconnaissance de la parole et en analyse
grammaticale.
J.-J. V.
Références
• Élémems de théorie des automates. Jacques Sakarovitch , Vuibert , 2003.
• Fondations mathématiques de la théorie des automates .
Jean-Éric Pin et O li vier Carton , disponible en li gne.
• Co111bi11atorics on Words, M. Lothaire, Cambridge Un iversi ty Press.
1997.
Hors-série n• 52. Mathématiques & informatique Tangente
chemi n des automates déterministes. En
particulier, un résultat dû à Valentin M.
Antimi rov permet de co nstruire, à partir d' une expression rationnelle à n lettres,
un automate non nécessaireme nt déterministe à 11 + 1 états au pire qui le reconnaît. Un tel automate est appelé awomate
aux termes dérivés.
Parmi tous les auto mates qui reconnaissent le même langage, i I en ex iste
un unique, déterministe, à nombre d'états
minimal, appe lé ... automate minimal.
De plus , cet automate est ca lcul ab le
efficacement .
Les langages contenant un nombre fini
de mots sont rationnels puisque la somme
de tous les mots d'un tel langage consti -
tue une express ion rationnelle finie qui
le dénote . Le dictionnaire électronique
des formes fléchies du français , réa li sé
par les lin g ui stes de l' unive rsité de
Marne-la-Vallée, contient huit cent deux
mille neuf mots sur un alphabet de quatrevingt-dix lettres (minu scul es et maj uscules accentuées, chiffres et autres signes).
Sa représe ntati on par arbre lex icographique nécessite 2 203 26 1 nœuds, tandis que l' a ut o mate minim a l le
reconnaissant ne possède que 273 716
états. Les automates constituent donc
un exce llent moyen de compresser l' informat ion contenue dans un di ctionnai re, et donc d'accepter des mots validés
ou rejetés dans une version électronique
du jeu de Scrabble par exempl e.
Ain si, ces mac hines très simpl es permettent de décrire une vaste classe de langages. Et c'est ce qui est à la base de la
co mpl ex ité algorithmique : savoi r ce
que l' on peut décrire à partir de ressou rces limitées, ou réciproquement
tro uver la capac ité de ca lcul suffi sante
pour répondre à un problème donné. À
note r que si les automates fini s peuvent
être vus co mme des programmes qui
B
POUR L'INFORMATIQUE
R
s
~ 111J--- -
·
~ -f - - --· s
s
, __ __ , ,___ o _ ~ -•~--•
u
( }---- ·
p
D
c
X
s
~ 111J--- -
·
~ . . ..___ __ .
s
i-----------1 ':·
O
U
Une représentation par arbre lexicographique.
Une représentation équiva lente par automates.
prennent en entrée un mot et retournent
O ou I selon s' il est accepté ou rejeté, il
en ex iste une généra li sation (les transducteurs finis) qui transforme l'entrée en
une sorti e sur un autre alphabet , ce qui
a des appli cations en compilation , en
reconnaissance de la parole et en analyse
grammaticale.
J.-J. V.
Références
• Élémems de théorie des automates. Jacques Sakarovitch , Vuibert , 2003.
• Fondations mathématiques de la théorie des automates .
Jean-Éric Pin et O li vier Carton , disponible en li gne.
• Co111bi11atorics on Words, M. Lothaire, Cambridge Un iversi ty Press.
1997.
Hors-série n• 52. Mathématiques & informatique Tangente