Transductor de estados finitos

Un transductor de estados finitos, o transductor finito, es un autómata finito (o máquina de estados finitos) con dos cintas, una de entrada y otra de salida.

Esto contrasta con un autómata finito habitual, que tiene solamente una cinta. Podemos decir que el autómata reconoce una cadena si esta se encuentra en su cinta de entrada. En otras palabras, el autómata computa una función que convierte una cadena en un elemento del conjunto (0,1). Por otra parte, podemos decir que un autómata genera cadenas a partir de su cinta de salida. Desde este punto de vista, el autómata genera un lenguaje formal, que no es más que un conjunto de cadenas. Los dos puntos de vista del autómata son equivalentes: la función que computa el autómata es la función indicadora del conjunto de cadenas reconocidas. La clase de lenguajes generados por un autómata finito se conoce con el nombre de lenguajes regulares

Típicamente las dos cintas de un transductor se ven como una cinta de entrada y otra de salida. Desde este punto de vista, un transductor se dice que transduce (traduce) el contenido de la cinta de entrada a la cinta de salida, mediante la aceptación de una cadena en la cinta de entrada, y la generación de otra cadena en la cinta de salida. Esta transducción se puede realizar de forma no determinista y entonces se producirá más de una salida por cada cadena de entrada. Un transductor también puede no producir ninguna salida para una cadena de entrada, y en este caso se dice que el transductor rechaza la entrada. En general, un transductor establece una relación entre dos lenguajes formales. La clase de relaciones computadas por un transductor de estados finitos se conoce como una clase de relaciones racionales.

Los transductores de estados finitos se utilizan normalmente en análisis morfológico y en la investigación y aplicaciones de procesamiento del lenguaje natural.

Construcción formal[editar]

Formalmente un transductor de estados finitos T es una tupla (Q, Σ, Γ, I, F, δ) tal que:

Q es un conjunto finito, el conjunto de estados;
Σ es un conjunto finito, llamado el alfabeto de entrada;
Γ es un conjunto finito, llamado el alfabeto de salida;
I es un subconjunto de Q, el conjunto de estados iniciales;
F es un subconjunto de Q, el conjunto de estados finales; y
$\delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q$ (donde ε es la cadena vacía) es la función de transición.

Se puede ver (Q, δ) como un grafo dirigido etiquetado, conocido como el grafo de transición de T: el conjunto de vértices es Q, y $(q,a,b,r)\in \delta$ indica que hay una arista etiquetada que va del vértice q al vértice r. También se dice que a es la etiqueta de entrada y b la etiqueta de salida de esa arista.

Esta definición de traductor de estados finitos también se conoce como traductor de letras (Roche and Schabes 1997); hay otras definiciones posible, pero todas se pueden generar partiendo de esta.

Se define la función de transición extendida $\delta ^{*}$ como el conjunto más pequeño tal que:

$\delta \subseteq \delta ^{*}$ ;
$(q,\epsilon ,\epsilon ,q)\in \delta ^{*}$ \forall $q\in Q$ ; y
whenever $(q,x,y,r)\in \delta ^{*}$ and $(r,a,b,s)\in \delta$ entonces $(q,xa,yb,s)\in \delta ^{*}$ .

La relación de transición extendida es, esencialmente, cláusula transitiva reflexiva del grafo de transición que ha sido aumentada para tener en cuenta las etiquetas de las aristas. Los elementos de $\delta ^{*}$ se conocen como caminos. Las etiquetas de la aristas de un camino se obtienen concatenando las etiquetas de las aristas de las transiciones que se han generado en orden.

El comportamiento del transductor T es la relación racional [T] definida como sigue: $x[T]y$ si y solo si existe $i\in I$ y $f\in F$ tal que $(i,x,y,f)\in \delta ^{*}$ . Esto significa que T transduce una cadena $x\in \Sigma ^{*}$ en una cadena $y\in \Gamma ^{*}$ si existe un camino desde un estado inicial hasta un estado final con entrada x y salida y.

Operaciones en transductores de estados finitos[editar]

Las siguientes operaciones definidas en autómatas finitos también se aplican a los transductores:

Unión. Dados los transductores T y S, existe un transductor $T\cup S$ tal que $x[T\cup S]y$ si y solo si $x[T]y$ o $x[S]y$ .

Concatenación. Dados los transductores T y S, existe un transductor $T\cdot S$ tal que $wx[T\cdot S]yz$ si y solo si $w[T]y$ y $x[S]z$ .

Clausura de Kleene.

No existe el concepto de intersección de transductores. Por el contrario, existe una operación de composición que es específica para los transductores, cuya construcción es parecida a la intersección de autómatas. La composición se define como sigue:

Dado un transductor T sobre los alfabetos Σ i Γ y un transductor S sobre los alfabetos Γ i Δ, existe un transductor $T\circ S$ sobre Σ y Δ tal que $x[T\circ S]z$ si y solo si existe una cadena $y\in \Gamma ^{*}$ tal que $x[T]y$ y $y[S]z$ .

También se puede se puede projectar una cinta del transductor para obtener un autómata. Hay dos funciones de projección: $\pi _{1}$ conserva la cinta de entrada, y $\pi _{2}$ conserva la de salida. La primera projección ( $\pi _{1}$ ) se define como sigue:

Dado un transductor T, existe un autómata finito $\pi _{1}T$ tal que $\pi _{1}T$ acepta x si y solo si existe una cadena y de forma que $x[T]y$ .

La segunda projección ( $\pi _{2}$ ) se puede definir de forma parecida.

Propiedades adicionales de los transductores de estados finitos[editar]

Es decidible si la relación [T] de un transductor T es vacía.

Es decidible si existe una cadena y tal que x[T]y para una cadena x.

No es decidible si dos transductors son equivalents.

Si se define un alfabeto de etiquetes $L=(\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})$ , el traductor de estados finitos es isomórfico a un autómata finito indeterminista (AFI) sobre el alfabeto $L$ , y puede convertirse en un autómata finito no determinista sobre el alfabeto $L=[(\Sigma \cup \{\epsilon \})\times \Gamma ]\cup [\Sigma \times (\Gamma \cup \{\epsilon \})]$ ) y pueden ser minimizado de forma que tengan el mínimo número de estados.