Ver el código de «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 [[Robot|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 [[lenguaje regular|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 de lenguajes naturales|procesamiento del lenguaje natural]].


== Construcción formal ==

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
* <math>\delta \subseteq Q \times (\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\}) \times Q</math> (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 <math>(q,a,b,r)\in\delta</math> 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'' <math>\delta^*</math> como el conjunto más pequeño tal que:

* <math>\delta\subseteq\delta^*</math>;
* <math>(q,\epsilon,\epsilon,q)\in\delta^*</math> \forall <math>q\in Q</math>; y
* whenever <math>(q,x,y,r) \in \delta^*</math> and <math>(r,a,b,s) \in \delta</math> entonces <math>(q,xa,yb,s) \in \delta^*</math>.

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 <math>\delta^*</math> 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: <math>x[T]y</math> [[si y solo si]] existe <math>i \in I</math> y <math>f \in F</math> tal que <math>(i,x,y,f) \in \delta^*</math>. Esto significa que ''T'' transduce una cadena <math>x\in\Sigma^*</math> en una cadena <math>y\in\Gamma^*</math> si existe un camino desde un estado inicial hasta un estado final con entrada x y salida y.

== Operaciones en transductores de estados finitos ==

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

* [[Unión de conjuntos|Unión]]. Dados los transductores ''T'' y ''S'', existe un transductor <math>T\cup S</math> tal que <math>x[T\cup S]y</math> si y solo si <math>x[T]y</math> o <math>x[S]y</math>.

* [[Concatenación]]. Dados los transductores ''T'' y ''S'', existe un transductor <math>T\cdot S</math> tal que <math>wx[T\cdot S]yz</math> si y solo si <math>w[T]y</math> y <math>x[S]z</math>.

* [[Clausura de Kleene]]. 

No existe el concepto de [[intersección de conjuntos|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 <math>T \circ S</math> sobre Σ y Δ tal que <math>x[T\circ S]z</math> si y solo si existe una cadena <math>y\in\Gamma^*</math> tal que <math>x[T]y</math> y <math>y[S]z</math>.

También se puede se puede projectar una cinta del transductor para obtener un autómata. Hay dos funciones de projección: <math>\pi_1</math> conserva la cinta de entrada, y <math>\pi_2</math> conserva la de salida. La primera projección (<math>\pi_1</math>) se define como sigue:

* Dado un transductor ''T'', existe un autómata finito <math>\pi_1 T</math> tal que <math>\pi_1 T</math> acepta ''x'' si y solo si existe una cadena ''y'' de forma que <math>x[T]y</math>.

La segunda projección (<math>\pi_2</math>) se puede definir de forma parecida.

== Propiedades adicionales de los transductores de estados finitos ==

* 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 <math>L=(\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\})</math>, el traductor de estados finitos es isomórfico a un autómata finito indeterminista (AFI) sobre el alfabeto <math>L</math>, y puede convertirse en un autómata finito no determinista sobre el alfabeto <math>L=[(\Sigma\cup\{\epsilon\}) \times \Gamma] \cup [\Sigma \times (\Gamma\cup\{\epsilon\})]</math> ) y pueden ser minimizado de forma que tengan el mínimo número de estados.

== Tipos de transductores de estados finitos ==

Dentro de los transductores de estados finitos tenemos:

* [[Transductor secuencial]]
* [[Transductor subsecuencial]] 
* [[Transductor p-subsecuencial]] 
* [[Transductor p-subsecuencial adelantado]] 
* [[Transductor de estados finitos determinista p-subsecuencial]] 
* [[Transductor de estados finitos determinista p-subsecuencial adelantado]] 

== Véase también ==
* [[Máquina de Mealy]]

== Bibliografía ==

* {{cita libro |apellidos= Jurafsky|nombre= Daniel |coautores= James H. Martin|enlaceautor=Daniel Jurafsky|título= Speech and Language Processing |url= https://archive.org/details/speechlanguagepr00jura|editorial= [[Prentice Hall]] |año= 2000 |isbn = 0-13-095069-6|páginas=[https://archive.org/details/speechlanguagepr00jura/page/n206 71]-83}}
* {{cita libro |apellidos= Roche|nombre= Emmanuel |autor2= Yves Schabes|enlaceautor=Emmanuel Roche|título= Finite-state language processing |url= https://archive.org/details/finitestatelangu00roch|editorial= [[MIT Press]] |año= 1997 |isbn = 0-262-18182-7|páginas=[https://archive.org/details/finitestatelangu00roch/page/n15 1]-65}}
* {{cita libro |apellidos= Galvez|nombre= Carmen |autor2= Félix Moya-Anegon|enlaceautor=Carmen Galvez|título= An Evaluation of Conflation Accuracy Using Finite-State Transducers |editorial= [[Journal of Documentation]] |año= 2006 |id= ISSN 0022-0418 |páginas=vol. 62 (3), 328-349}}
* {{cita libro |apellidos= Galvez|nombre= Carmen |enlaceautor=Carmen Galvez|título= Approximate Personal Name-Matching Through Finite-State Graphs |editorial= [[Journal of The American Society for Information Science and Technology]] |año= 2007 |id= ISSN 1532-2882|páginas= vol.58 (13), 1960-1976}}
* {{cita libro |apellidos= Galvez|nombre= Carmen |enlaceautor=Carmen Galvez|título= Standardizing Formats of Corporate Source Data |editorial= [[Scientometrics]]  |año= 2007 |id= ISSN 0138-9130 |páginas= vol. 70 (1), 3-26}}

{{Control de autoridades}}
[[Categoría:Lenguajes formales]]
[[Categoría:Traducción automática]]