Transducción secuencial
# Transducción secuencial

Una transducción $\eta :E\rightarrow \Gamma ^{*}$, donde:

* $\Sigma$ es un conjunto finito, denominado alfabeto de entrada
* $\Sigma ^{*}$ es el conjunto de todas las cadenas que se pueden construir mediante los símbolos de $\Sigma$
* $E$ es el subconjunto de $\Sigma ^{*}$
* $\Gamma ^{*}$ es el lenguaje de salida

es secuencial si:

$\eta (\varepsilon )=\mu _{0}$

$\eta (w\sigma )=\eta (w)\zeta (w,\sigma )\;\;\forall w,w\sigma \in \mathrm {Pr} (E),\;\sigma \in \Sigma$

donde:

* $\mu _{0}\in \Gamma ^{*}$ es la cadena de salida inicial (normalmente vacía)
* $\zeta (w,\sigma )\in \Gamma ^{*}$ es la cadena de salida que se concatena tras el resultado cuando después de la entrada $w$ se lee el símbolo $\sigma$
* $\mathrm {Pr} (E)=\{x:(\exists y\in \Sigma ^{*}:xy\in E)\}$ es el conjunto de todos los prefijos de las cadenas en $E$.

Cada vez que se lee un símbolo $\sigma$, la función $\zeta (w,\sigma )$ añade la cadena de salida a $\eta (w)$ para formar $\eta (w\sigma )$.

Las transducciones secuenciales tienen la propiedad de preservar los prefijos. Es decir, la transducción de un prefijo es siempre un prefijo de la transducción. Esto es: si existe $\eta (uv)$, entonces $\eta (u)\in \mathrm {Pr} (uv)$ .

Las transduccciones secuenciales se pueden realizar por transductores de estados finitos, también denominados transductores secuenciales.

