Transducción secuencial

Plantilla:Enmarañado Una transducción $\eta :E\to {\mathrm{\Gamma }}^{*}$, donde:

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

es secuencial si:

$\eta (\epsilon )={\mu }_0$

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

donde:

• ${\mu }_0\in {\mathrm{\Gamma }}^{*}$ es la cadena de salida inicial (normalmente vacía)
• $\zeta (w,\sigma )\in {\mathrm{\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{P}\mathrm{r}(E)=\{x:(\mathrm{\exists }y\in {\mathrm{\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{P}\mathrm{r}(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.