apprentissage de langages formels. Ce sous-domaine de l’apprentissage automatique,
qui a une quarantaine d’années, est appel´e inférence grammaticale [dlH03].
Sa motivation premi`ere ´etait de modéliser l’apprentissage de la langue par l’enfant
[Cho56]. Mais, par la suite, de multiples autres domaines ont bénéficié de
ses avanc´ees, allant de la génétique [BJVU98] `a la reconnaissance de la parole
[GSVG94], en passant par le traitement de documents structurés [Fer01]
ou la compression de textes [NMW97].
Un langage est un ensemble, fini ou non, de mots formés sur un alphabet
donn´e [Aut87]. Un mot est simplement une concaténation de symboles de l’alphabet.
Un langage peut ˆetre représenté par une grammaire formelle, c’est-`a-dire
un ensemble de règles formées sur l’alphabet du langage (les lettres) et sur un alphabet
compl´ementaire distinct (appel´e alphabet des non-terminaux ). Ces réglés
permettent de ré écrire un ensemble de symboles des alphabets par un autre ensemble.
Le langage engendré par une grammaire est l’ensemble des mots que
l’on peut obtenir en utilisant les r`egles de la grammaire `a partir d’un symbole
non-terminal particulier, appel´e axiome de la grammaire.
