Transductor de estados finitos

Máquina de estados finitos con dos cintas (entrada, salida)

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 se asigna entre dos conjuntos de símbolos. ^[1] Un FST es más general que un FSA. Un FSA define un lenguaje formal al definir un conjunto de cadenas aceptadas, mientras que un FST define una relación entre conjuntos de cadenas.

Una FST leerá un conjunto de cadenas en la cinta de entrada y generará un conjunto de relaciones en la cinta de salida. Una FST puede considerarse como un traductor o un relacionador entre cadenas en un conjunto.

En el análisis morfológico , un ejemplo sería ingresar una cadena de letras en la FST, que luego generaría una cadena de morfemas .

Descripción general

Se puede decir que un autómata reconoce una cadena si vemos 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 ver su cinta como una cinta de salida. En esta visión, el autómata genera un lenguaje formal , que es un conjunto de cadenas. Las dos visiones 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 consideran típicamente como una cinta de entrada y una cinta de salida. Desde este punto de vista, 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 su cinta de entrada y generar otra cadena en su cinta de salida. Puede hacerlo de manera no determinista y puede producir más de una salida para cada cadena de entrada. Un transductor también puede no producir 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 se pueden implementar 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 un Γ*, 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 incluyen Ronald Kaplan , Lauri Karttunen , Martin Kay y Kimmo Koskenniemi . ^{[2] [ Se necesita una fuente no primaria ]} Una forma común de utilizar transductores es en una denominada "cascada", donde los transductores para varias operaciones se combinan en un único transductor mediante la aplicación repetida del operador de composición (definido a continuación).

Construcción formal

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 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. ${\displaystyle (q,a,b,r)\in \delta }$

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

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

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

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

El comportamiento del transductor T es la relación racional [ T ] definida de la siguiente manera: si y solo si existe y tal que . Es decir, T transduce una cadena en una cadena 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 . ${\displaystyle x[T]y}$ ${\displaystyle i\in I}$ ${\displaystyle f\in F}$ ${\displaystyle (i,x,y,f)\in \delta ^{*}}$ ${\displaystyle x\in \Sigma ^{*}}$ ${\displaystyle y\in \Gamma ^{*}}$

Autómatas ponderados

Los transductores de estados finitos pueden ser ponderados, donde cada transición se etiqueta con un peso además de las etiquetas de entrada y salida. Un transductor de estados finitos ponderado (WFST) sobre un conjunto K de pesos se puede definir de manera similar a uno no ponderado como una tupla de 8 T = ( Q , Σ, Γ, I , F , E , λ , ρ ) , donde:

• Q , Σ, Γ, I , F se definen como arriba;
• ${\displaystyle E\subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q\times K}$(donde ε es la cadena vacía ) es el conjunto finito de transiciones;
• ${\displaystyle \lambda :I\rightarrow K}$asigna estados iniciales a pesos;
• ${\displaystyle \rho :F\rightarrow K}$asigna estados finales a pesos.

Para que ciertas operaciones en WFST estén bien definidas, es conveniente exigir que el conjunto de pesos forme un semianillo . ^[3] Dos semianillos típicos utilizados en la práctica son el semianillo logarítmico y el semianillo tropical : los autómatas no deterministas pueden considerarse como si tuvieran pesos en el semianillo booleano . ^[4]

FST estocástico

Las FST estocásticas (también conocidas como FST probabilísticas o FST estadísticas) son presumiblemente una forma de FST ponderada. ^{[ cita requerida ]}

Operaciones en transductores de estados finitos

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

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

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

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

Esta definición utiliza la misma notación que se utiliza 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 , cuando existen algunas y tales que y ${\displaystyle (x,z)\in T\circ S}$ ${\displaystyle (x,y)\in S}$ ${\displaystyle (y,z)\in T.}$

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

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

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

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

Propiedades adicionales de los transductores de estados finitos

• Es decidible si la relación [ T ] de un transductor T está vacía.
• Es decidible si existe una cadena y tal que x [ T ] y para una cadena dada x .
• No se puede decidir si dos transductores son equivalentes. ^[12] Sin embargo, la equivalencia es decidible en el caso especial donde la relación [ T ] de un transductor T es una función (parcial).
• Si se define el alfabeto de etiquetas , los transductores de estados finitos son isomorfos a NDFA sobre el alfabeto y, por lo tanto, pueden determinarse (convertirse en autómatas finitos deterministas sobre el alfabeto ) y, posteriormente, minimizarse para que tengan el número mínimo de estados. ^{[ cita requerida ]} ${\displaystyle L=(\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})}$ ${\displaystyle L}$ ${\displaystyle L=[(\Sigma \cup \{\epsilon \})\times \Gamma ]\cup [\Sigma \times (\Gamma \cup \{\epsilon \})]}$

Aplicaciones

Las FST se utilizan en la fase de análisis léxico de los compiladores para asociar el valor semántico con los tokens descubiertos. ^[13]

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 los transductores de estados finitos, siempre que la aplicación no sea recursiva, es decir, no se permite que la regla reescriba la misma subcadena dos veces. ^[14]

Las FST ponderadas encontraron aplicaciones en el procesamiento del lenguaje natural , incluida la traducción automática , y en el aprendizaje automático . ^{[15] [16]} Una implementación para el etiquetado de partes del discurso se puede encontrar como un componente de la biblioteca OpenGrm ^[17] .

Véase también

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

Notas

1. Jurafsky, Daniel (2009). Procesamiento del habla y del lenguaje . Pearson. ISBN 9789332518414.
2. Koskenniemi 1983
3. Berstel, Jean; Reutenauer, Christophe (2011). Series racionales no conmutativas con aplicaciones . Enciclopedia de matemáticas y sus aplicaciones. Vol. 137. Cambridge: Cambridge University Press . pág. 16. ISBN. 978-0-521-19022-0.Zbl 1250.68007  .
4. Lotario, M. (2005). Combinatoria aplicada a las palabras. Enciclopedia de Matemáticas y sus aplicaciones. vol. 105. Una obra colectiva de Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert , Sophie Schbath , Michael Waterman, Philippe Jacquet, Wojciech Szpankowski , Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche y Valérie Berthé . Cambridge: Prensa de la Universidad de Cambridge . pag. 211.ISBN​ 0-521-84802-4.Zbl 1133.68067  .
5. Boigelot, Bernard; Legay, Axel; Wolper, Pierre (2003). "Iteración de transductores en el gran formato". Verificación asistida por ordenador . Apuntes de clase sobre informática. Vol. 2725. Springer Berlin Heidelberg. págs. 223–235. doi :10.1007/978-3-540-45069-6_24. eISSN  1611-3349. ISBN 978-3-540-40524-5. ISSN  0302-9743.
6. Mohri 2004, págs. 3-5
7. "Determinación de transductores".
8. Mohri 2004, págs. 5-6
9. Allauzen y Mohri 2003
10. Mohri 2004, págs. 7-9
11. Mohri 2004, págs. 9-11
12. Griffiths 1968
13. Charles N. Fischer; Ron K. Cytron; Richard J. LeBlanc, Jr. (2010). "Escaneo: teoría y práctica". Elaboración de un compilador . Addison-Wesley. ISBN 978-0-13-606705-4.
14. "Modelos regulares de sistemas de reglas fonológicas" (PDF) . Archivado desde el original (PDF) el 11 de octubre de 2010 . Consultado el 25 de agosto de 2012 .
15. Kevin Knight; Jonathan May (2009). "Aplicaciones de los autómatas ponderados en el procesamiento del lenguaje natural". En Manfred Droste; Werner Kuich; Heiko Vogler (eds.). Manual de autómatas ponderados . Springer Science & Business Media. ISBN 978-3-642-01492-5.
16. "Aprendizaje con transductores ponderados" (PDF) . Consultado el 29 de abril de 2017 .
17. OpenGrm

Referencias

• Allauzen, Cyril; Mohri, Mehryar (2003). "Algoritmos eficientes para probar la propiedad de gemelos" (PDF) . Revista de autómatas, lenguajes y combinatoria . 8 (2): 117–144.
• Koskenniemi, Kimmo (1983), Morfología de dos niveles: un modelo computacional general de reconocimiento y producción de formas de palabras (PDF) , Departamento de Lingüística General, Universidad de Helsinki , archivado desde el original (PDF) el 2018-12-21 , consultado el 2010-01-10
• Mohri, Mehryar (2004). "Algoritmos de transductores de estados finitos ponderados. Una descripción general" (PDF) . Lenguajes formales y aplicaciones . Estudios en difusividad y computación blanda. Vol. 148. págs. 551–564. doi :10.1007/978-3-540-39886-8_29. ISBN 978-3-642-53554-3.
• Griffiths, TV (1968). "La insolubilidad del problema de equivalencia para máquinas generalizadas no deterministas libres de Λ". Revista de la ACM . 15 (3). ACM: 409–413. doi :10.1145/321466.321473.

Enlaces externos

• OpenFst, una biblioteca de código abierto para operaciones FST.
• Morfología de estados finitos: el libro archivado el 25 de marzo de 2022 en Wayback Machine XFST/LEXC, una descripción de la implementación de Xerox de transductores de estados finitos destinados a aplicaciones lingüísticas.
• Implementación y extensión de código abierto de Xerox fst en Helsinki
• FOMA, una implementación de código abierto de la mayoría de las capacidades de la implementación Xerox XFST/LEXC.
• Herramientas de transductores de estados finitos de Stuttgart, otro conjunto de herramientas FST de código abierto
• Java FST Framework, un marco Java FST de código abierto capaz de manejar el formato de texto OpenFst.
• Vcsn Archivado el 23 de junio de 2020 en Wayback Machine , una plataforma de código abierto (C++ e IPython) para autómatas ponderados y expresiones racionales.

Lectura adicional

• 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