Transductor de estado finito

Un transductor de estados finitos ( FST ) es una máquina de estados finitos con dos cintas de memoria , siguiendo la terminología de las máquinas de Turing : una cinta de entrada y una cinta de salida. Esto contrasta con un autómata de estados finitos ordinario , que tiene una sola cinta. Un FST es un tipo de autómata de estados finitos (FSA) que establece una correspondencia entre dos conjuntos de símbolos. ^{[ 1 ]} Un FST es más general que un FSA. Un FSA define un lenguaje formal mediante la definición de un conjunto de cadenas aceptadas, mientras que un FST define una relación entre conjuntos de cadenas.

Un FST lee un conjunto de cadenas en la cinta de entrada y genera un conjunto de relaciones en la cinta de salida. Un FST puede considerarse como un traductor o un generador de relaciones entre las cadenas de un conjunto.

En el análisis morfológico , un ejemplo sería introducir una cadena de letras en el FST, y este generaría como salida una cadena de morfemas .

Se puede decir que un autómata reconoce una cadena si consideramos el contenido de su cinta como entrada. En otras palabras, el autómata calcula una función que asigna cadenas al conjunto {0,1}. Alternativamente, podemos decir que un autómata genera cadenas, lo que significa considerar su cinta como una cinta de salida. Desde esta perspectiva, el autómata genera un lenguaje formal , que es un conjunto de cadenas. Ambas perspectivas de los autómatas son equivalentes: la función que calcula el autómata es precisamente la función indicadora del conjunto de cadenas que genera. La clase de lenguajes generados por autómatas finitos se conoce como la clase de lenguajes regulares .

Las dos cintas de un transductor se suelen considerar como una cinta de entrada y una cinta de salida. Desde esta perspectiva, se dice que un transductor transduce (es decir, traduce) el contenido de su cinta de entrada a su cinta de salida, al aceptar una cadena en la cinta de entrada y generar otra en la cinta de salida. Puede hacerlo de forma no determinista y producir más de una salida para cada cadena de entrada. Un transductor también puede no producir ninguna salida para una cadena de entrada dada, en cuyo caso se dice que rechaza la entrada. En general, un transductor calcula una relación entre dos lenguajes formales.

Cada transductor de estados finitos de cadena a cadena relaciona el alfabeto de entrada Σ con el alfabeto de salida Γ. Las relaciones R en Σ*×Γ* que pueden implementarse como transductores de estados finitos se denominan relaciones racionales . Las relaciones racionales que son funciones parciales , es decir, que relacionan cada cadena de entrada de Σ* con como máximo una Γ*, se denominan funciones racionales .

Los transductores de estados finitos se utilizan a menudo para el análisis fonológico y morfológico en la investigación y las aplicaciones del procesamiento del lenguaje natural . Entre los pioneros en este campo se encuentran Ronald Kaplan , Lauri Karttunen , Martin Kay y Kimmo Koskenniemi . ^{[ 2 ]} Una forma común de utilizar transductores es en una denominada "cascada", donde los transductores para diversas operaciones se combinan en un único transductor mediante la aplicación repetida del operador de composición (definido más adelante).

Formalmente, un transductor finito T es una 6-tupla ( Q , Σ, Γ, I , F , δ ) tal que:

• Q es un conjunto finito , el conjunto de estados ;
• Σ es un conjunto finito, llamado alfabeto de entrada ;
• Γ es un conjunto finito, llamado 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
• ${\displaystyle \delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q}$(donde ε es la cadena vacía ) es la relación de transición .

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

NOTA: Esta definición de transductor finito también se denomina transductor de letras (Roche y Schabes 1997); son posibles definiciones alternativas, pero todas pueden convertirse en transductores siguiendo esta definición.

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

• ${\displaystyle \delta \subseteq \delta ^{*}}$;
• ${\displaystyle (q,\epsilon ,\epsilon ,q)\in \delta ^{*}}$a pesar de${\displaystyle q\in Q}$; y
• cuando sea${\displaystyle (q,x,y,r)\in \delta ^{*}}$y${\displaystyle (r,a,b,s)\in \delta }$entonces${\displaystyle (q,xa,yb,s)\in \delta ^{*}}$.

La relación de transición extendida es esencialmente el cierre transitivo reflexivo del grafo de transición que se ha aumentado para tener en cuenta las etiquetas de los bordes. Los elementos de${\displaystyle \delta ^{*}}$se conocen como caminos . Las etiquetas de los bordes de un camino se obtienen concatenando las etiquetas de los bordes de sus transiciones constituyentes en orden.

El comportamiento del transductor T es la relación racional [ T ] definida de la siguiente manera:${\displaystyle x[T]y}$si y solo si existe${\displaystyle i\in I}$y${\displaystyle f\in F}$de tal manera que${\displaystyle (i,x,y,f)\in \delta ^{*}}$Esto quiere decir que T transduce una cadena${\displaystyle x\in \Sigma ^{*}}$en una cuerda${\displaystyle y\in \Gamma ^{*}}$Si existe un camino desde un estado inicial a un estado final cuya etiqueta de entrada es x y cuya etiqueta de salida es y .

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

• Unión . Dados los transductores T y S , existe un transductor${\displaystyle T\cup S}$de tal manera que${\displaystyle x[T\cup S]y}$si y solo si${\displaystyle x[T]y}$o${\displaystyle x[S]y}$.
• Concatenación . Dados los transductores T y S , existe un transductor${\displaystyle T\cdot S}$de tal manera que${\displaystyle x[T\cdot S]y}$si y solo si existen${\ Displaystyle x_ {1}, x_ {2}, y_ {1}, y_ {2}}$con${\displaystyle x=x_{1}x_{2},y=y_{1}y_{2},x_{1}[T]y_{1}}$y${\displaystyle x_{2}[S]y_{2}.}$
• Cierre de Kleene . Dado un transductor T , podría existir un transductor${\displaystyle T^{*}}$con las siguientes propiedades: ^{[ 6 ]}

y${\displaystyle x[T^{*}]y}$no se sostiene a menos que lo exija ( k1 ) o ( k2 ).

• Composición . Dado un transductor T sobre los alfabetos Σ y Γ y un transductor S sobre los alfabetos Γ y Δ, existe un transductor${\displaystyle T\circ S}$en Σ y Δ de tal manera que${\displaystyle x[T\circ S]z}$si y solo si existe una cadena${\displaystyle y\in \Gamma ^{*}}$de tal manera que${\displaystyle x[T]y}$y${\displaystyle y[S]z}$Esta operación se extiende al caso ponderado. ^{[ 7 ]}

Esta definición utiliza la misma notación que se usa en matemáticas para la composición de relaciones . Sin embargo, la lectura convencional para la composición de relaciones es al revés: dadas dos relaciones T y S ,${\displaystyle (x,z)\in T\circ S}$cuando existe algún y tal que${\displaystyle (x,y)\in S}$y${\displaystyle (y,z)\in T.}$

• Proyección a un autómata. Existen dos funciones de proyección:${\displaystyle \pi _{1}}$conserva la cinta de entrada y${\displaystyle \pi _{2}}$conserva la cinta de salida. La primera proyección,${\displaystyle \pi _{1}}$se define de la siguiente manera:

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

:La segunda proyección,${\displaystyle \pi _{2}}$se define de manera similar.

• Determinización . Dado un transductor T , queremos construir un transductor equivalente que tenga un estado inicial único y tal que no haya dos transiciones que salgan de cualquier estado compartan la misma etiqueta de entrada. La construcción del conjunto potencia puede extenderse a transductores, o incluso a transductores ponderados, pero a veces no se detiene; de ​​hecho, algunos transductores no deterministas no admiten transductores deterministas equivalentes. ^{[ 8 ]} Se han propuesto caracterizaciones de transductores determinizables ^{[ 9 ]} junto con algoritmos eficientes para probarlos: ^{[ 10 ]} se basan en el semianillo utilizado en el caso ponderado así como en una propiedad general sobre la estructura del transductor (la propiedad de gemelos ).
• Empuje de peso para el caso ponderado. ^{[ 11 ]}
• Minimización para el caso ponderado. ^{[ 12 ]}
• Eliminación de transiciones épsilon .

• 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 dada .
• Es indecidible si dos transductores son equivalentes. ^{[ 13 ]} Sin embargo, la equivalencia es decidible en el caso especial en que la relación [ T ] de un transductor T es una función (parcial).

Los FST se utilizan en la fase de análisis léxico de los compiladores para asociar un valor semántico con los tokens descubiertos. ^{[ 14 ]}

Las reglas de reescritura sensibles al contexto de la forma a → b / c _ d , utilizadas en lingüística para modelar reglas fonológicas y cambios de sonido , son computacionalmente equivalentes a transductores de estados finitos, siempre que su aplicación no sea recursiva, es decir, que la regla no pueda reescribir la misma subcadena dos veces. ^{[ 15 ]}

Los FST ponderados encontraron aplicaciones en el procesamiento del lenguaje natural , ^{[ 16 ]} incluyendo traducción automática , ^{[ 17 ]} reconocimiento de voz , ^{[ 18 ] [ 19 ]} síntesis de voz , ^{[ 20 ]} y reconocimiento óptico de caracteres . ^{[ 21 ]} También en compresión de imágenes , ^{[ 22 ]} y aprendizaje automático en general. ^{[ 23 ]} Una implementación para el etiquetado de partes de la oración se puede encontrar como un componente de la biblioteca OpenGrm .

• Máquina harinosa
• Máquina de Moore
• Diccionario morfológico
• Foma (software)
• transductor de árbol
• Transductor relacional

• Jurafsky, Daniel ; James H. Martin (2000). Procesamiento del habla y del lenguaje . Prentice Hall. págs. 71-83 . ISBN  0-13-095069-6.
• Kornai, András (1999). Modelos de lenguaje de estados finitos extendidos . Prensa de la Universidad de Cambridge. ISBN 0-521-63198-X.
• Roche, Emmanuel; Yves Schábes (1997). Procesamiento del lenguaje de estados finitos . Prensa del MIT. págs. 1 –65. ISBN  0-262-18182-7.
• Beesley, Kenneth R.; Lauri Karttunen (2003). Morfología de estados finitos . Centro para el Estudio del Lenguaje y la Información. ISBN 1-57586-434-7.
• Roark, Brian; Richard Sproat (2007). Enfoques computacionales de la morfología y la sintaxis . Oxford University Press. ISBN 978-0-19-927478-9.
• Berstel, Jean (1979). Transducciones y lenguajes libres de contexto . Teubner Verlag.Versión PDF gratuita

• OpenFst , una biblioteca de código abierto para operaciones FST.
• La implementación de código abierto de Helsinki y la extensión del Xerox fst
• FOMA , una implementación de código abierto de la mayoría de las capacidades de la implementación Xerox XFST/LEXC.
• Stuttgart Finite State Transducer Tools , otro conjunto de herramientas FST de código abierto.
• Java FST Framework , un framework Java FST de código abierto capaz de manejar el formato de texto OpenFst.