Exercice 4

1. Ecrivez un transducteur qui calcule le double d'un nombre (qui peut avoir plusieurs chiffres) à condition qu'il n'y ait pas de retenue (c'est-à-dire que tous les chiffres sont plus petits que 5).
2. On va essayer d'écrire maintenant une cascade de transducteurs qui calcule le double d'un nombre y compris lorsqu'il y a des retenues. Pour cela, on va commencer par faire un calcul trop général qui considère qu'à chaque chiffre on peut avoir une retenue ou pas. Par exemple, le double de 4 peut être 8 (pas de retenue) ou 9 (il y a une retenue). Ecrivez ce calcul trop général sous forme d'un transducteur qui transcrit un nombre à plusieurs chiffre en plusieurs nombres dont l'un est le double. Il faut aussi penser qu'une retenue sur le chiffre le plus à gauche ajoute un chiffre de plus au nombre.
3. On va à présent calculer les retenues sous forme d'une suite de 0 ou 1 à ajouter aux chiffres. Par exemple, pour 536, on va calculer la chaîne 101 (retenue pour le premier et le troisième chiffre, pas de retenue pour le second. Ecrivez ce calcul sous forme d'un transducteur.
4. Il s'agit maintenant de décaler les retenues qui doivent s'appliquer un cran à gauche par rapport à l'endroit où elles ont été calculées. Par exemple, sur 536, la retenue du nombre des centaines doit s'ajouter au nombre des milliers. Celle des unités doit s'ajouter au nombre des dizaines. Pour faire ce décalage, il faut et il suffit d'ajouter un 0 à droite de la chaîne obtenue à la question précédente. Faites cet ajout au moyen d'un transducteur qui transcrit chaque chiffre en lui-même concaténé au transducteur qui transcrit epsilon (noté "" en OpenGRM) en 0.
5. spécifiez un transducteur qui transcrit un 0 en n'importe quel chiffre pair et 1 en n'importe quel chiffre impair, pour un nombre de longueur quelconque. Par exemple 110 sera transcrit dans le langage (1|3|5|7|9)(1|3|5|7|9)(0|2|4|6|8).
6. calculez la composition des trois derniers transducteurs.
7. Pour calculer le double d'un nombre, on va calculer séparément son image par le transducteur de la question 2 et son image par le transducteur de la question 6. Puis on fera l'intersection des deux images et on espère obtenir exactement un nombre, le bon résultat.

Par exemple, l'image de 536 par le premier transducteur est le langage 1?(0|1)(6|7)(2|3). Par le second transducteur, c'est (1|3|5|7|9)(0|2|4|6|8)(1|3|5|7|9)(0|2|4|6|8). L'intersection des deux, c'est 1072.

Question subsidiaire: créez une fonction OpenGRM pour réaliser les différentes opérations de calcul du double.