MP/MP*: Option Informatique
DS du mardi 7 décembre 2004
Automates finis pondérés



Problème 1

À partir du modèle classique de l'automate fini (déterministe ou non), de nombreuses variantes ont été étudiées: automate avec bande de sortie (sur laquelle on peut écrire un mot), automate boustrophédon (la tête de lecture peut revenir en arrière). Dans un automate pondéré, chaque transition est étiquetée par la lettre lue et par un poids; le poids d'un calcul est la somme des poids des transitions constituant ce calcul.

Nous nous intéressons dans le premier problème à un modèle particulier d'automate pondéré: les poids appartiennent au groupe (Z,+); un mot est reconnu s'il est l'étiquette d'un calcul de poids nul commençant dans l'état initial. Nous verrons que la famille des langages reconnus par ces automates possède certaines des propriétés des langages rationnels, mais pas toutes. Les idées ont été trouvées dans un chapitre du livre Jewels are Forever, recueil d'articles écrits en l'honneur d'Arto Salomaa pour son soixante-cinquième anniversaire.

Problème 2

Le deuxième problème demande la définition par induction structurelle puis la programmation en Caml de quelques fonctions définies sur la famille des langages rationnels sur un alphabet fixé.