F. Barthélemy
Ce document complète le TP Utilisation d'une boîte à outil d'automates pour ce qui est de la description de transducteurs finis. Si vous n'êtes pas bien famillier avec l'utilisation de Lextools et FSM pour la description d'automates finis, allez étudier ce TP avant d'aborder celui-ci.
Les transducteurs en lextools sont décrits au moyen d'expressions régulières comprenant l'opérateur de produit cartésien noté : (deux-points).
Voyons l'exemple de transducteur fini donné dans le polycopié de cours, qui consiste à traduire un, deux et trois en anglais.
Pour décrire ce transducteur en lextools, il faut d'abord un fichier de symboles que l'on appellera ici alpha.sym.
lettre a b c d e f g h i j k l m n o p lettre q r s t u v w x y z
Voici l'expression régulière lextools que l'on nommera trans1.lex:
(un:one) (deux:two) (trois:three)
Pour compiler cette expression puis générer l'image du graphe:
lexmakelab alpha lexcomplex -l alpha.lab -S alpha.scl trans1.lex > trans1.fsm fsmdraw -p -i alpha.lab -o alpha.lab trans1.fsm | dot -Tgif > trans1.gif
A noter que pour fsmdraw il faut donner le fichier des symboles en entrée (option -i) et le fichier des symboles en sortie (option -o). Ici, c'est le même fichier de symboles qui est utilisé pour l'entrée en français et la sortie en anglais.
Cela produit l'image:
Le premier exemple utilisait le prduit cartésien pour traduire une chaîne en une autre chaîne. Cet opérateur permet de mettre en correspondance deux langages réguliers.
Fichier trans2.lex:
((a|b|c):(x*))+((d*e):(y(z+)))
Exemples de chaînes et de traductions (paires de la relation régulière):
| abaddde |  |
xyzzzz |
| cbe | |
xxxxxxxxyz |
| cdde | |
yzz |
Compilation:
lexcomplex -l alpha.lab -S alpha.scl trans2.lex > trans2.fsm fsmdraw -p -i alpha.lab -o alpha.lab trans2.fsm | dot -Tgif > trans2.gif
Cela produit l'image:
Il est possible de définir directement un transducteur en FSM au moyen d'un fichier texte avec le codage suivant:
Le transducteur du premier exemple Lextools donné ci-dessus peut s'écrire comme suit.
Fichier trans3.txt:
0 1 d t 0 2 t t 0 3 u o 1 4 e w 2 5 r h 3 6 n n 4 7 u o 5 8 o r 6 9 <epsilon> e 7 9 x <epsilon> 8 10 i e 9 10 9 s e
La compilation et la génération de l'image s'obtiennent par:
fsmcompile -t -i alpha.lab -o alpha.lab trans3.txt > trans3.fsm fsmdraw -p -i alpha.lab -o alpha.lab trans3.fsm | dot -Tgif > trans3.gif
Cela produit l'image:
Pour obtenir les couples d'une relation régulière (à la condition qu'elle soit finie), on utilise la commande lexfsmstrings.
> lexfsmstrings -l alpha.lab trans1.fsm deux two trois three un one
La composition de transducteurs s'obtient par la commande fsmcompose. La sélection d'un langage et un transducteur s'obtient également par la même commande, avec comme premier argument un automate et comme second argument un transducteur. La projection avec fsmproject et une option -1 ou -2 pour spécifier si l'on projette sur l'entrée ou la sortie.
Le but de cet exemple est de décrire la conversion des nombres écrits avec des chiffres en une écriture en toutes lettres, en se limitant aux nombres à deux chiffres.
Voyons d'abord une expression au moyen d'expressions régulières, puis sa traduction en Lextools/FSM.
zero := (0:zero)
zero_muet := (0:'epsilon')
un := (1:un)
deux_six := (2:deux)|(3:trois)|(4:quatre)|(5:cinq)|(6:six)
sept_neuf := (7:sept)|(8:huit)|(9:neuf)
deux_neuf := <deux_six> | <sept_neuf>
dix := (1:dix)
dizaines_norm := (2:vingt)|(3:trente)|(4:quarante)|(5:cinquante)|
(6:soixante)
dizaines_7_9 := (7:soixante)|(9:quatre-vingt)
dizaines_8 := (8:quatre-vingt)
tiret := ('epsilon':'-')
et := ('epsilon':' 'et' ')
nombres_en_1 := (11:onze)|(12:douze)|(13:treize)|(14:quatorze)|(15:quinze)
|(16:seize)|<dix><tiret><zero_muet>|<dix><tiret><sept_neuf>
nombres_norm := <dizaine_norm>(<zero_muet>|<et><un>|<tiret><deux_neuf>)
nombres_en_7_9 := <dizaines_7_9><tiret><nombres_en_1>
nombres_en_8 := <dizaines_8>((0:s)|<tiret><un>|<tiret><deux_neuf>)
nombres = <zero> | <un> | <deux_neuf> | <nombres_en_1> | <nombres_norm>
| <nombres_en_7_9> | <nombres_en_8>
En Lextools, il n'est pas très facile d'utiliser une expression définie
précédemment dans une expression régulière, comme c'est le cas de
nombres_en_1 par exemple. Pour rester simple, on divisera une telle
expression en plus petits morceaux traité séparéments.
Voyons les fichiers sources Lextools et commandes FSM utilisées pour compiler cette description.
Fichier de symboles alpha2.sym:
lettre a b c d e f g h i j k l m n o p lettre q r s t u v w x y z chiffre 0 1 2 3 4 5 6 7 8 9 separateur esp tiret
Fichier zero.lex:
(0:zero)
Fichier zero_muet.lex:
(0:[<epsilon>])
Fichier un.lex:
(1:un)
Fichier deux_six:
(2:deux)|(3:trois)|(4:quatre)|(5:cinq)|(6:six)
Fichier sept_neuf:
(7:sept)|(8:huit)|(9:neuf)
Pour définir l'expression deux_neuf qui utilise deux expressions déjà définies, on utilise non pas Lextools mais FSM, après avoir compilé les deux expressions en question.
Compilation des expressions déjà définies:
lexmakelab alpha2 lexcomplex -l alpha2.lab -S alpha2.scl zero.lex > zero.fsm lexcomplex -l alpha2.lab -S alpha2.scl zero_muet.lex > zero_muet.fsm lexcomplex -l alpha2.lab -S alpha2.scl un.lex > un.fsm lexcomplex -l alpha2.lab -S alpha2.scl deux_six.lex > deux_six.fsm lexcomplex -l alpha2.lab -S alpha2.scl sept_neuf.lex > sept_neuf.fsm
Fichier deux_neuf.fsm:
fsmunion deux_six.fsm sept_neuf.fsm > deux_neuf.fsm
Nous allons présenter la suite des nombreuses définitions à donner au moyen d'un tableau.
| nom du fichier | type | description |
| dix.lex | Lextools |
(1:dix) |
| dizaines_norm.lex | Lextools |
(2:vingt)|(3:trente)|(4:quarante)|(5:cinquante)|(6:soixante) |
| dizaines_7_9.lex | Lextools |
(7:soixante)|(9:quatre[tiret]vingt) |
| dizaines_8.lex | Lextools |
(8:quatre[tiret]vingt) |
| tiret.lex | Lextools |
([<epsilon>]:[tiret]) |
| et.lex | Lextools |
([<epsilon>]:[esp]et[esp]) |
| nombres_en_1_spec.lex | Lextools |
(11:onze)|(12:douze)|(13:treize)|(14:quatorze)|(15:quinze)|(16:seize) |
| nombres_en_1_0.fsm | FSM |
fsmconcat dix.fsm tiret.fsm zero_muet.fsm > nombres_en_1_0.fsm |
| nombres_en_1_norm.fsm | FSM |
fsmconcat dix.fsm tiret.fsm sept_neuf.fsm > nombres_en_1_norm.fsm |
| nombres_en_1.fsm | FSM |
fsmunion nombres_en_1_0.fsm nombres_en_1_spec.fsm nombres_en_1_norm.fsm > nombres_en_1.fsm
|
| et_un.fsm | FSM | fsmconcat et.fsm un.fsm > et_un.fsm |
| tiret_2_9.fsm | FSM |
fsmconcat tiret.fsm deux_neuf.fsm > tiret_2_9.fsm |
| fin_norm.fsm | FSM |
fsmunion zero_muet.fsm et_un.fsm tiret_2_9.fsm > fin_norm.fsm |
| nombres_norm.fsm | FSM |
fsmconcat dizaines_norm.fsm fin_norm.fsm > nombres_norm.fsm |
| nombres_en_7_9.fsm | FSM |
fsmconcat dizaines_7_9.fsm tiret.fsm nombres_en_1.fsm > nombres_en_7_9.fsm
|
| zero_s.lex | Lextools |
(0:s) |
| fin_en_8.fsm | FSM |
fsmunion zero_s.fsm et_un.fsm tiret_2_9.fsm > fin_en_8.fsm |
| nombres_en_8.fsm | FSM |
fsmconcat dizaines_8.fsm fin_en_8.fsm > nombres_en_8.fsm |
| nombres_0_9.fsm | FSM |
fsmunion zero.fsm un.fsm deux_neuf.fsm > nombres_0_9.fsm |
| nombres_10_69.fsm | FSM |
fsmunion nombres_en_1.fsm nombres_norm.fsm > nombres_10_69.fsm
|
| nombres_70_99 | FSM |
fsmunion nombres_en_7_9.fsm nombres_en_8.fsm > nombres_70_99.fsm |
| nombres_0_99 | FSM |
fsmunion nombres_0_9.fsm nombres_10_69.fsm nombres_70_99.fsm > nombres_0_99.fsm
|
Pour compiler ces fichiers, voici la suite de commande à opérer (après avoir créé tous les fichiers .lex).
lexmakelab alpha2 lexcomplex -l alpha2.lab -S alpha2.scl zero.lex > zero.fsm lexcomplex -l alpha2.lab -S alpha2.scl zero_muet.lex > zero_muet.fsm lexcomplex -l alpha2.lab -S alpha2.scl un.lex > un.fsm lexcomplex -l alpha2.lab -S alpha2.scl deux_six.lex > deux_six.fsm lexcomplex -l alpha2.lab -S alpha2.scl sept_neuf.lex > sept_neuf.fsm lexcomplex -l alpha2.lab -S alpha2.scl dix.lex > dix.fsm lexcomplex -l alpha2.lab -S alpha2.scl dizaines_norm.lex > dizaines_norm.fsm lexcomplex -l alpha2.lab -S alpha2.scl dizaines_7_9.lex > dizaines_7_9.fsm lexcomplex -l alpha2.lab -S alpha2.scl dizaines_8.lex > dizaines_8.fsm lexcomplex -l alpha2.lab -S alpha2.scl tiret.lex > tiret.fsm lexcomplex -l alpha2.lab -S alpha2.scl et.lex > et.fsm lexcomplex -l alpha2.lab -S alpha2.scl nombres_en_1_spec.lex > nombres_en_1_spec.fsm lexcomplex -l alpha2.lab -S alpha2.scl zero_s.lex > zero_s.fsm fsmunion deux_six.fsm sept_neuf.fsm > deux_neuf.fsm fsmconcat dix.fsm tiret.fsm zero_muet.fsm > nombres_en_1_0.fsm fsmconcat dix.fsm tiret.fsm sept_neuf.fsm > nombres_en_1_norm.fsm fsmunion nombres_en_1_0.fsm nombres_en_1_spec.fsm nombres_en_1_norm.fsm > nombres_en_1.fsm fsmconcat et.fsm un.fsm > et_un.fsm fsmconcat tiret.fsm deux_neuf.fsm > tiret_2_9.fsm fsmunion zero_muet.fsm et_un.fsm tiret_2_9.fsm > fin_norm.fsm fsmconcat dizaines_norm.fsm fin_norm.fsm > nombres_norm.fsm fsmconcat dizaines_7_9.fsm tiret.fsm nombres_en_1.fsm > nombres_en_7_9.fsm fsmunion zero_s.fsm et_un.fsm tiret_2_9.fsm > fin_en_8.fsm fsmconcat dizaines_8.fsm fin_en_8.fsm > nombres_en_8.fsm fsmunion zero.fsm un.fsm deux_neuf.fsm > nombres_0_9.fsm fsmunion nombres_en_1.fsm nombres_norm.fsm > nombres_10_69.fsm fsmunion nombres_en_7_9.fsm nombres_en_8.fsm > nombres_70_99.fsm fsmunion nombres_0_9.fsm nombres_10_69.fsm nombres_70_99.fsm > nombres_0_99.fsm
La première chose que nous pouvons faire consiste à vérifier que le transducteur contient bien une traduction pour les 100 premiers nombres écrits en chiffres. Pour cela, nous le projetons sur son entrée, puis nous affichons toutes les chaînes du langage résultant de cette projection.
fsmproject -1 nombres_0_99.fsm | lexfsmstrings -l alpha2.lab
Cette première vérification montre un bug dans notre description.
On peut ensuite faire la même opération sur la sortie.
fsmproject -2 nombres_0_99.fsm | lexfsmstrings -l alpha2.lab
Ici, on voit un autre bug de la description.
Si l'on veut traduire un nombre donné, par exemple 56, il faut créer un fichier cinquante_six.lex contenant la chaîne 56. On compile ce fichier. Puis on calcule la sélection de 56 et du transducteur. Enfin, on projette le résultat sur la sortie. Et on affiche le résultat. Soit écrit en Lextools/FSM:
lexcomplex -l alpha2.lab -S alpha2.scl cinquante_six.lex > cinquante_six.fsm fsmcompose cinquante_six.fsm nombres_0_99.fsm | fsmproject -2 > trad_56.fsm lexfsmstrings -l alpha2.lab trad_56.fsm
On voit là qu'il n'y a pas de bug sur cet exemple.
Un peu plus compliqué, cherchons les traductions de tous les nombres ne
comportant que des 5 et des 3. Pour cela, on décrit en Lextools les chaînes ne
comportant que des 5 et des 3: (5|3)*. On met cette expression dans un
fichier chaines_5_3.lex et on suit la même démarche que pour 56.
lexcomplex -l alpha2.lab -S alpha2.scl chaines_5_3.lex > chaines_5_3.fsm fsmcompose chaines_5_3.fsm nombres_0_99.fsm | fsmproject -2 > trad_c53.fsm lexfsmstrings -l alpha2.lab trad_c53.fsm