MP/MP*: Option Informatique
Devoir à rendre le 10 janvier 2008
Transducteurs et mots de Christoffel



La première partie présente la notion de transducteur: c'est un automate fini muni d'une deuxième bande, sur laquelle il peut, à chaque transition, écrire zéro, un ou plusieurs symboles. Il réalise ainsi une fonction qui, à un mot écrit sur la bande d'entrée, associe le mot écrit sur la bande de sortie.

La deuxième partie vous fait démontrer la formule de Pick; elle servira dans la suite, et peut, au besoin, être admise.

La troisième partie définit les mots (finis) de Christoffel et propose une étude de certaines de leurs propriétés.

Enfin, la quatrième partie réalise le lien entre les transducteurs et les mots de Christoffel.

Fichiers

En lisant ces deux articles, vous constaterez que le sujet proposé est bien loin d'épuiser la question!