Transducteur fini

En informatique théorique, en linguistique, et en particulier en théorie des automates, un transducteur fini (appelé aussi transducteur à états finis par une traduction littérale de l'anglais finite state transducer) est un automate fini avec sorties. C'est une extension des automates finis. Ils opèrent en effet sur les mots sur un alphabet d'entrée et, au lieu de simplement accepter ou refuser le mot, ils le transforment, de manière parfois non déterministe, en un ou plusieurs mots sur un alphabet de sortie. Ceci permet des transformations de langages, et aussi des utilisations variées telles que notamment l'analyse syntaxique des langages de programmation, et l'analyse morphologique ou l'analyse phonologique en linguistique. Une des propriétés remarquables des transducteurs finis est qu'ils transforment les langages rationnels en langages rationnels, et les langages algébriques en langages algébriques. Un transducteur fini est une machine mathématique qui transforme des mots. Une telle machine est conçue sur le modèle des automates finis, avec, pour chaque transition, une étiquette additionnelle sous forme d'un mot. Chaque transition est donc dotée de deux étiquettes. Ceci est fréquemment représenté par l'écriture Le symbole est l' étiquette d'entrée, le symbole est l' étiquette de sortie de la transition. De manière imagée, on dit que le transducteur « lit » le symbole et « écrit » le symbole en passant de l'état à l'état . En itérant cette action un transducteur lit un mot de gauche à droite sur son ruban d'entrée et écrit un mot sur son ruban de sortie. La finitude du transducteur signifie la finitude du nombre d'états. Mais comme souvent en informatique théorique, les machines sont — en principe — non déterministes, c'est-à-dire qu'il existe plusieurs exécutions où un même mot est lu, mais les états pris par la machine et les mots écrits peuvent différer dans les différentes exécutions. Les transducteurs finis ont de nombreuses propriétés théoriques, et des applications pratiques nombreuses, par exemple en compilation, en reconnaissance de la parole et en linguistique.