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

Véase también

• Transductor de estados finitos.
• Transductor subsecuencial.
• Transductor p-subsecuencial.
• Transductor p-subsecuencial adelantado.
• Transductor de estados finitos determinista p-subsecuencial.
• Transductor de estados finitos determinista p-subsecuencial adelantado.

Enlaces externos

• Wikimedia Commons alberga una categoría multimedia sobre Transductores.

• Datos: Q6151638