Transducteur fini

Un transducteur fini est défini par un 6-uple

${\displaystyle T=(\Sigma _{1},\Sigma _{2},Q,I,F,\delta )}$, où :

• ${\displaystyle \Sigma _{1}}$ est l'alphabet fini d'entrée ;

• ${\displaystyle \Sigma _{2}}$ est l'alphabet fini de sortie ;

• ${\displaystyle Q}$ est l'ensemble fini des états ;

• ${\displaystyle I\subseteq Q}$ est l'ensemble des états initiaux ;

• ${\displaystyle F\subseteq Q}$ est l'ensemble des états finaux ;

• ${\displaystyle \delta }$ est la table de transition : c'est un sous-ensemble de ${\displaystyle Q\times (\Sigma _{1}\cup \{\varepsilon \})\times (\Sigma _{2}\cup \{\varepsilon \})\times Q}$ où ${\displaystyle \varepsilon }$ est le mot vide.

La propriété ${\displaystyle (q,a,b,r)\in \delta }$ signifie qu'il existe une transition de l'état ${\displaystyle q}$ vers l'état ${\displaystyle r}$ par laquelle on lit le symbole ${\displaystyle a\in \Sigma _{1}\cup \{\varepsilon \}}$ sur le ruban d'entrée et on écrit le symbole ${\displaystyle b\in \Sigma _{2}\cup \{\varepsilon \}}$ sur le ruban de sortie. Ceci est fréquemment représenté par la notation

${\displaystyle q\,{\xrightarrow {a|b}}\,r}$

Le symbole ${\displaystyle a}$ est l'étiquette d'entrée, le symbole ${\displaystyle b}$ est l'étiquette de sortie de la transition[1].

Si ${\displaystyle |T(w)|\leq 1}$ pour tout ${\displaystyle w\in {\Sigma _{1}}^{*}}$, alors le transducteur T est dit fonctionnel.

La clôture transitive ${\displaystyle \delta ^{*}}$ de ${\displaystyle \delta }$ est la plus petite relation (pour l'inclusion des relations) vérifiant :

• ${\displaystyle \delta ^{*}\subseteq Q\times \Sigma _{1}^{*}\times \Sigma _{2}^{*}\times Q}$

• ${\displaystyle \delta \subseteq \delta ^{*}}$

• ${\displaystyle \forall q\in Q,(q,\varepsilon ,\varepsilon ,q)\in \delta ^{*}}$ (réflexivité)

• Si ${\displaystyle (q,x,y,r)\in \delta ^{*}}$ et ${\displaystyle (r,a,b,s)\in \delta }$, alors ${\displaystyle (q,xa,yb,s)\in \delta ^{*}}$ (transitivité)

En d'autres termes, ${\displaystyle (q,x,y,r)\in \delta ^{*}}$ signifie qu'il existe un chemin de l'état ${\displaystyle q}$ vers l'état ${\displaystyle r}$ dont l'étiquette d'entrée est le mot ${\displaystyle x\in \Sigma _{1}^{*}}$ et l'étiquette de sortie est le mot ${\displaystyle y\in \Sigma _{2}^{*}}$. Un chemin est réussi si ${\displaystyle q\in I}$ et ${\displaystyle r\in F}$.

Par analogie avec les automates finis qui reconnaissent un langage, un transducteur fini ${\displaystyle T}$ reconnaît une relation, notée ${\displaystyle [T]}$ du produit cartésien des deux monoïdes libres. On a ${\displaystyle (x,y)\in [T]}$ ou ${\displaystyle x[T]y}$ si et seulement s'il existe ${\displaystyle p\in I}$ et ${\displaystyle r\in F}$ tel que ${\displaystyle (p,x,y,r)\in \delta ^{*}}$. En d'autres termes, ${\displaystyle x}$ est en relation avec ${\displaystyle y}$ si et seulement s'il existe un chemin réussi qui lit ${\displaystyle x}$ et écrit ${\displaystyle y}$.

Dans une variante de la définition, au lieu de demander que les étiquettes des transitions soient des lettres ou le mot vide, on autorise comme étiquettes des mots sur l'alphabet d'entrée resp. l'alphabet de sortie.

Dans le cas où aucune des étiquettes du transducteur n'est le mot vide, on peut voir un transducteur comme un cas particulier des automates finis. Il vérifie alors les propriétés classiques des automates.

Il suffit en effet de considérer un automate dont l'alphabet est le produit cartésien des deux alphabets : ${\displaystyle \Sigma =\Sigma _{1}\times \Sigma _{2}}$.

Le fait de considérer un transducteur comme une relation rationnelle permet d'établir une propriété primordiale dans l'étude et l'utilisation de ceux-ci : la clôture par composition.

• Union : soient ${\displaystyle A}$ et ${\displaystyle B}$ deux transducteurs finis. On définit un transducteur fini, noté ${\displaystyle A\cup B}$ tel que ${\displaystyle [A\cup B]=[A]\cup [B]}$.

• Produit de concaténation : soient ${\displaystyle A}$ et ${\displaystyle B}$ deux transducteurs, alors il existe un transducteur noté ${\displaystyle A\cdot B}$ tel que ${\displaystyle u[A\cdot B]v}$ si et seulement s'il existe des décompositions ${\displaystyle u=xx'}$ et ${\displaystyle v=yy'}$ telles que ${\displaystyle x[A]y}$ et ${\displaystyle x'[B]y'}$. En d'autres termes, ${\displaystyle [A\cdot B]=\{(xx',yy')\mid (x,y)\in [A],(x',y')\in [B]\}}$.

• Étoile de Kleene : soit ${\displaystyle T}$, alors il existe un transducteur noté ${\displaystyle T^{*}}$ qui correspond à l'étoile pour l'opération de concaténation.

Attention, l'intersection de relations rationnelles n'est pas nécessairement rationnelle (l'intersection de deux relations ${\displaystyle R}$ et ${\displaystyle R'}$ est la relation ${\displaystyle R''}$ définie par ${\displaystyle R''=R\cap R'}$)

Considérons deux transducteurs finis ${\displaystyle T_{1}}$ et ${\displaystyle T_{2}}$ tels que l'alphabet de sortie de ${\displaystyle T_{1}}$ coïncide avec l'alphabet d'entrée de ${\displaystyle T_{2}}$.

Le composé ${\displaystyle T_{3}=T_{2}\circ T_{1}}$ est défini par la relation ${\displaystyle [T_{3}]}$ :

${\displaystyle x[T_{3}]y\Leftrightarrow \exists z}$ tel que ${\displaystyle x[T_{1}]z}$ et ${\displaystyle z[T_{2}]y}$.

Il est important de noter que la composition de deux transducteurs finis est encore un transducteur fini. Ainsi la composition permet d'élaborer facilement des transducteurs ayant une fonction complexe à partir de transducteurs simples.

• Projection gauche : la projection gauche d'une relation ${\displaystyle R}$ est l'ensemble ${\displaystyle K=\{x\mid \exists y:(x,y)\in R\}}$. Soit ${\displaystyle T}$ un transducteur fini. La projection gauche de la relation ${\displaystyle [T]}$ est un langage rationnel: il existe automate fini qui la reconnaît; il suffit en effet d’« oublier » les étiquettes de sortie sur les transitions de ${\displaystyle T}$.

• Projection droite : de même, la projection droite d'une relation rationnelle est un langage rationnel.