Lextools, FSM et les transducteurs

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.

Décrire un transducteur avec lextools et FSM

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).

Premier exemple en Lextools

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:

102

Deuxième exemple en Lextools

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:

103

Exemple de transducteur en FSM

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:

104

Opérations sur les transducteurs

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.

Exemple complet

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



Francois Barthelemy 2012-01-13