SAVOIRS
par Jill-Jênn Vie
langages rationnels
et automates finis
La théorie des langages formels est une modélisation du
langage naturel. Fondamentale pour décrire et analyser les
langages de programmation et la calculabilité, elle a de
nombreuses applications en linguistique
correction
orthographique, reconnaissance vocale, traduction.
P
anni les langages formels se trouve
la sous-cl asse re marqu abl e des
langages rationnels, indissociables
des automates fini s ou des machines
abstraites (à la base des fameuses machines
de Turing). Les automates trouvent euxmêmes des applications en info rmatique,
te lles que la modé li sation de processus,
l'analyse lex icale effectuée par les compi lateurs et la recherche de motifs (par
exemple la recherche d'occurrences d' un
mot dans un texte, ou de détection de
séquences de bases azotées dans I' ADN).
Des lettres, des mots ... un langage !
Un langage est défini comme un ensemble
de mots, eux- mêmes suites d 'éléments
d ' un alphabet , ensemble de lettres souvent supposé fini . L'ensemble des mots
fini s sur l'alphabet A est noté A*. Sur l'alphabet {a, b, n}, les ensembles
{baba, m:ibab, banann.} et {a,aa,aaa .. . }
sont des langages (le premier est fi ni ,
le seco nd es t infini ). De mê me, les
séque nces de bases azotées so nt des
mots sur l'a lphabet {A , T, C , G}.
Marcel-Paul Schützenberger
(1920-1996), fo ndateur
de la combinatoire des mols (1983).
On introduit ensuite la concaténation , opération (natu re lle) qui à deux mots
u = u 1 u 2 . •• u 111 et
v = v 1 v 2 ... v 11 assoc ie le mot
uv = u 1 u 1 . .. u,,,v 1 v 2 ••• v 11 obtenu en « ajoutant » o u « coll ant » v après u. La notati o n (a b )
3 = ababab est ut ili sée pour
simplifier les notati ons. Enfin , on note
Tangente Hors-série n°52. Mathématiques & informatique
par Jill-Jênn Vie
langages rationnels
et automates finis
La théorie des langages formels est une modélisation du
langage naturel. Fondamentale pour décrire et analyser les
langages de programmation et la calculabilité, elle a de
nombreuses applications en linguistique
correction
orthographique, reconnaissance vocale, traduction.
P
anni les langages formels se trouve
la sous-cl asse re marqu abl e des
langages rationnels, indissociables
des automates fini s ou des machines
abstraites (à la base des fameuses machines
de Turing). Les automates trouvent euxmêmes des applications en info rmatique,
te lles que la modé li sation de processus,
l'analyse lex icale effectuée par les compi lateurs et la recherche de motifs (par
exemple la recherche d'occurrences d' un
mot dans un texte, ou de détection de
séquences de bases azotées dans I' ADN).
Des lettres, des mots ... un langage !
Un langage est défini comme un ensemble
de mots, eux- mêmes suites d 'éléments
d ' un alphabet , ensemble de lettres souvent supposé fini . L'ensemble des mots
fini s sur l'alphabet A est noté A*. Sur l'alphabet {a, b, n}, les ensembles
{baba, m:ibab, banann.} et {a,aa,aaa .. . }
sont des langages (le premier est fi ni ,
le seco nd es t infini ). De mê me, les
séque nces de bases azotées so nt des
mots sur l'a lphabet {A , T, C , G}.
Marcel-Paul Schützenberger
(1920-1996), fo ndateur
de la combinatoire des mols (1983).
On introduit ensuite la concaténation , opération (natu re lle) qui à deux mots
u = u 1 u 2 . •• u 111 et
v = v 1 v 2 ... v 11 assoc ie le mot
uv = u 1 u 1 . .. u,,,v 1 v 2 ••• v 11 obtenu en « ajoutant » o u « coll ant » v après u. La notati o n (a b )
3 = ababab est ut ili sée pour
simplifier les notati ons. Enfin , on note
Tangente Hors-série n°52. Mathématiques & informatique