¿Qué es un transductor de estado finito?

Question

¿Puede alguien decirme qué es un transductor de estado finito?

He leído the Wikipedia article y no entiendo nada.

Answer 1

Un transductor de estado finito (FST) es un autómata de estado finito (FSA, FA) que produce salida y lectura, lo que significa que es útil para analizar (mientras que un FSA "simple" solo puede utilizarse para reconocer , es decir, coincidencia de patrones).

Un FST consiste en un número finito de estados que están vinculados por transiciones etiquetadas con un par de entrada/salida. El FST comienza en un estado de inicio designado y salta a diferentes estados dependiendo de la entrada, mientras produce salida de acuerdo con su tabla de transición.

FST son útiles en NLP y reconocimiento de voz porque tienen buenas propiedades algebraicas, más notablemente que se pueden combinar libremente (forma un álgebra) en composición, que implementa la composición relacional en relaciones regulares (piense en esto como no determinista composición de la función) mientras se mantiene muy compacto. Los FST pueden hacer el análisis sintáctico de los idiomas regulares en cadenas en tiempo lineal.

Como ejemplo, una vez implementé el análisis morfológico como un grupo de FST. Mi FST principal para verbos convertiría un verbo regular, di "caminó", en "caminar + PASADO". También tuve un FST para el verbo "to be", que se convertiría "is" en "be + PRESENT + 3rd" (tercera persona), y de manera similar para otros verbos irregulares. Todos los FST se combinaron en uno solo con un compilador FST, que produjo un solo FST que era mucho más pequeño que la suma de sus partes y funcionaba muy rápido. Los FST se pueden construir mediante una variedad de herramientas que aceptan una sintaxis de expresión regular extendida.

Answer 2

Un transductor de estado finito es esencialmente un autómata de estado finito que funciona en dos (o más) cintas. La forma más común de pensar en los transductores es como una especie de "máquina de traducción". Leen de una de las cintas y escriben en la otra. Esto, por ejemplo, es un transductor que se traduce a s en b s:

a:b en el arco significa que en esta transición el transductor lee a de la primera cinta y escribe b sobre la segunda.

Referencia: Finite State Transducers

Answer 3

En términos tan simples como sea posible, entiendo que una FST es esencialmente una "cosa" que se mueve de un estado a otro basado en una cinta de entrada y escribe en una salida diferente cinta. Una cinta es esencialmente un conjunto de entradas como caracteres en una cadena.

Todo el FST está representado por un conjunto de estados y enlaces entre ellos. Un enlace se "activa" cuando su condición de entrada es correcta y luego da el próximo estado de la cinta ajustada.

Por ejemplo digamos que una FST se inicia con la cinta abc en el estado 1. Un enlace a estado 2 partidos a y cambios que a b. Esto se activaría, establezca la cinta de salida a solo b, y pase el bc restante al estado 2. Como puede ver, cada estado solo se activa si hay un enlace a él cuya condición de entrada es correcta, pasa la entrada restante a el siguiente estado, y escribe en una cinta de salida separada. Cada FST se ejecuta en la cinta una vez y se envía a otra cinta una vez.

Para obtener una comprensión más clara de ellos read and take a look at the diagrams in this article.