transductor de estado finito

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] Una FST es más general que una FSA. Una FSA define un lenguaje formal definiendo un conjunto de cadenas aceptadas, mientras que una FST define una relación entre conjuntos de cadenas.

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

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

Descripción general

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 ver su cinta como una cinta de salida. Desde este punto de vista, 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 clase de lenguajes regulares .

Las dos cintas de un transductor normalmente se consideran 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, aceptando una cadena en su cinta de entrada y generando otra cadena en su cinta de salida. Puede hacerlo de forma 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 determinada, en cuyo caso se dice que rechaza la entrada. En general, un transductor calcula una relación entre dos lenguajes formales.

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

Los transductores de estado finito se utilizan a menudo para análisis fonológicos y morfológicos en investigaciones y aplicaciones de procesamiento del lenguaje natural . Entre los pioneros en este campo se encuentran Ronald Kaplan , Lauri Karttunen , Martin Kay y Kimmo Koskenniemi . ^{[2] [ se necesita fuente no primaria ]} Una forma común de usar transductores es en la llamada "cascada", donde los transductores para varias operaciones se combinan en un solo 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 tupla de 6 ( 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 gráfico dirigido etiquetado , conocido como gráfico 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 yb la etiqueta de salida de ese borde. ${\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 esta.

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 aumentado para tener en cuenta las etiquetas de los bordes. Los elementos de se conocen como caminos . Las etiquetas de borde de una ruta se obtienen concatenando en orden las etiquetas de borde de sus transiciones constituyentes. ${\displaystyle \delta ^{*}}$

El comportamiento del transductor T es la relación racional [ T ] definida de la siguiente manera: si y sólo si existe y tal que . Esto quiere decir que 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 estado finito se pueden ponderar, donde cada transición está etiquetada con un peso además de las etiquetas de entrada y salida. Un transductor de estado finito 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 anteriormente;
• ${\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 sobre WFST estén bien definidas, es conveniente requerir que el conjunto de pesos forme un semianillo . ^[3] Dos semirings típicos utilizados en la práctica son el semiring logarítmico y el semiring tropical : se puede considerar que los autómatas no deterministas tienen pesos en el semiring 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 necesaria ]}

Operaciones con transductores de estado finito.

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 tal que si y sólo 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 sólo si existe 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 kleene . Dado un transductor T , podría existir un transductor con las siguientes propiedades: ^[5] ${\displaystyle T^{*}}$

y no se mantiene a menos que así lo exija ( 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 solo 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 utilizada 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 existe alguna y tal 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. Hay dos funciones de proyección: conserva la cinta de entrada y conserva 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 que no haya dos transiciones que salgan de cualquier estado que compartan la misma etiqueta de entrada. La construcción del conjunto de potencia se puede extender a transductores, o incluso a transductores ponderados, pero a veces no logra detenerse; de hecho, algunos transductores no deterministas no admiten transductores deterministas equivalentes. ^[7] Se han propuesto caracterizaciones de transductores determinables ^[8] junto con algoritmos eficientes para probarlos: ^[9] se basan en el semianillo utilizado en el caso ponderado, así como en una propiedad general de la estructura del transductor (la propiedad de los gemelos ).
• Empuje de peso para el caso ponderado. ^[10]
• Minimización para el caso ponderado. ^[11]
• Eliminación de transiciones épsilon .

Propiedades adicionales de los transductores de estado finito.

• 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 .
• Es indecidible si dos transductores son equivalentes. ^[12] Sin embargo, la equivalencia es decidible en el caso especial en el que la relación [ T ] de un transductor T es una función (parcial).
• Si uno define el alfabeto de etiquetas , los transductores de estados finitos son isomorfos al NDFA sobre el alfabeto y, por lo tanto, pueden ser determinizados (convertidos en autómatas finitos deterministas sobre el alfabeto ) y posteriormente minimizados para que tengan el número mínimo de estados. ^{[ cita necesaria ]} ${\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

Los FST se utilizan en la fase de análisis léxico de los compiladores para asociar 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 estado finito, siempre que la aplicación sea no recursiva, es decir, no se permite reescribir la regla. la misma subcadena dos veces. ^[14]

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

Ver también

• maquina harinosa
• maquina moore
• Diccionario morfológico
• foma (software)
• transductor de arbol
• Transductor relacional

Notas

1. Jurafsky, Daniel (2009). Procesamiento del habla y el 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: Prensa de la Universidad de Cambridge . pag. 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). "Transductores iterativos a gran escala". Verificación asistida por computadora . Apuntes de conferencias sobre informática. vol. 2725. Springer Berlín 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. "Determinizació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 Caballero; Jonathan mayo (2009). "Aplicaciones de autómatas ponderados en el procesamiento del lenguaje natural". En Manfred Droste; Werner Kuich; Heiko Vogler (eds.). Manual de autómatas ponderados . Medios de ciencia y negocios de Springer. ISBN 978-3-642-01492-5.
16. "Aprendizaje con transductores ponderados" (PDF) . Consultado el 29 de abril de 2017 .
17. OpenGrm

Referencias

• Allauzen, Cirilo; Mohri, Mehryar (2003). "Algoritmos eficientes para probar la propiedad de los 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 21 de diciembre de 2018 , recuperado el 10 de enero de 2010
• Mohri, Mehryar (2004). "Algoritmos de transductores de estados finitos ponderados. Descripción general" (PDF) . Lenguajes formales y aplicaciones . Estudios en Borrosidad y Soft Computing. vol. 148, págs. 551–564. doi :10.1007/978-3-540-39886-8_29. ISBN 978-3-642-53554-3.
• Griffiths, televisión (1968). "La insolubilidad del problema de equivalencia para máquinas generalizadas no deterministas libres de Λ". 15 (3). ACC: 409–413. {{cite journal}}: Citar diario requiere |journal=( ayuda )

enlaces externos

• OpenFst, una biblioteca de código abierto para operaciones FST.
• Morfología de estados finitos: 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.
• La implementación de código abierto de Helsinki y la extensión de 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 Java FST Framework 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.

Otras lecturas

• Jurafsky, Daniel ; James H. Martín (2000). Procesamiento del habla y el 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 de Estudios del Lenguaje y la Información. ISBN 1-57586-434-7.
• Roark, Brian; Richard Sproat (2007). Enfoques computacionales de morfología y sintaxis . Prensa de la Universidad de Oxford. ISBN 978-0-19-927478-9.
• Berstel, Jean (1979). Transducciones y lenguajes libres de contexto . Teubner Verlag.. Versión PDF gratuita