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 tienes 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 és 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 utilitan normalmente en análisis morfológico y en la investigación y aplicaciones de procesamiento del lenguaje natural.


Contenido

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
  • \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 ésta.

Se define la función de transición extendida δ * 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 δ * 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

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.

No existe el concepto de intersecció 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: π1 conserva la cinta de entrada, y π2 conserva la de salida. La primera projección (π1) se define como sigue:

  • Dado un transductor T, existe un autómata finito π1T tal que π1T acepta x si y solo si existe una cadena y de forma que x[T]y.

La segunda projección (π2) 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 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.

Tipos de transductores de estados finitos

Dentro de los transductores de estados finitos tenemos:

Véase también

Bibliografía

  • Jurafsky, Daniel; James H. Martin (2000). Speech and Language Processing. Prentice Hall. pp. 71-83. ISBN 0-13-095069-6. 
  • Roche, Emmanuel; Yves Schabes (1997). Finite-state language processing. MIT Press. pp. 1-65. ISBN 0-262-18182-7. 
  • Galvez, Carmen; Félix Moya-Anegon (2006). An Evaluation of Conflation Accuracy Using Finite-State Transducers. Journal of Documentation. pp. vol. 62 (3), 328-349. ISSN 0022-0418. 
  • Galvez, Carmen (2007). Approximate Personal Name-Matching Through Finite-State Graphs. Journal of The American Society for Information Science and Technology. pp. vol.58 (13), 1960-1976. ISSN 1532-2882. 
  • Galvez, Carmen (2007). Standardizing Formats of Corporate Source Data. Scientometrics. pp. vol. 70 (1), 3-26. ISSN 0138-9130. 

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Transductor de estados finitos determinista p-subsecuencial adelantado — Los transductores de estados finitos son Autómatas de estados finitos deterministas con transiciones sobre parejas de símbolos. Un transductor de estados finitos determinista p subsecuencial adelantado (TpSSDA o EDpSST de sus siglas en inglés… …   Wikipedia Español

  • Transductor de estados finitos determinista p-subsecuencial — Un transductor de estados finitos determinista p subsecuencial es un Autómata de estados finitos deterministas con transiciones sobre parejas de símbolos. Éstos transductores no tienen estados de aceptación explicitamente definidos. Cada uno de… …   Wikipedia Español

  • Transductor p-subsecuencial — Un transductor p subsecuencial es un transductor subsecuencial que produce un número p de cadenas de salida adicional.[1] Se puede decir que es un transductor secuencial ampliado para permitir un número finito p de cadenas de salida en los… …   Wikipedia Español

  • Transductor subsecuencial — Un transductor subsecuencial o transductor 1 subsecuencial es aquel donde los símbolos de salida se generan sólo cuando se han visto suficientes símbolos en la entrada para garantizar una salida correcta. Se puede decir que es un transductor… …   Wikipedia Español

  • Transductor p-subsecuencial adelantado — Un Transductor p subsecuencial adelatado es un transductor p subsecuencial con la salida asignada a los arcos de forma que se produzca tan pronto como sea posible. Una transducción que asigna a cada cadena de caracteres en un conjunto de cadenas… …   Wikipedia Español

  • Transducción secuencial — Este artículo o sección tiene un estilo difícil de entender para los lectores interesados en el tema. Si puedes, por favor edítalo y contribuye a hacerlo más accesible para el público general, sin eliminar los detalles técnicos que interesan a… …   Wikipedia Español

  • Autómata finito — Un autómata finito (AF) o máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir una salida. Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de… …   Wikipedia Español

  • LRLM — La estrategia LRLM (left to right, longest match, o de izquierda a derecha, concordancia más larga) es una estrategia voraz para la segmentación (y subsecuente análisis) de una cadena de entrada. Esta estrategia analiza la cadena de entrada de… …   Wikipedia Español

  • General Architecture for Text Engineering — GATE ventana principal de GATE Developer v5 Desarrollador GATE research team …   Wikipedia Español

  • Electricidad — Este artículo o sección puede ser demasiado extenso(a). Algunos navegadores pueden tener dificultades al mostrar este artículo. Por favor, considera separar cada sección por artículos independientes, y luego resumir las secciones presentes en… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.