computer science - magister - ¿Qué es un transductor de estado finito?

master of science magister

Question

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

He leído el artículo de Wikipedia y no entiendo nada.

Answer 1

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 convierte 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 en la segunda.

Referencia: Transductores de estado finito.

Answer 2

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

La FST completa está representada por un conjunto de estados y enlaces entre ellos. Un enlace se "activa" cuando su condición de entrada es correcta y luego da a la cinta ajustada el siguiente estado.

Por ejemplo, digamos que un FST comienza con la cinta abc en el estado 1. Un enlace al estado 2 coincide con a y lo cambia a b . Esto se activaría, configuraría la cinta de salida a solo b , y pasaría el bc restante al estado 2. Como puede ver, cada estado solo se activa si existe un enlace cuya condición de entrada era 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, lea y consulte los diagramas de este artículo ( enlace roto original ).

Answer 3

Un transductor de estado finito (FST) es un autómata de estado finito (FSA, FA) que produce salida y lectura de entrada, lo que significa que es útil para el análisis (mientras que una FSA "simple" solo se puede usar para reconocer, es decir, la comparación 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 la salida de acuerdo con su tabla de transición.

Los FST son útiles en la PNL y el reconocimiento de voz porque tienen buenas propiedades algebraicas, sobre todo porque se pueden combinar libremente (forman un álgebra) bajo la composición, lo que implementa la composición relacional en las relaciones regulares (piense en esto como una composición de función no determinista) mientras quedando muy compacto. Los FST pueden analizar los lenguajes 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, decir "caminó", en "caminar + PASADO". También tuve un FST para el verbo "ser", que convertiría "es" en "be + PRESENT + 3rd" (tercera persona), y de manera similar para otros verbos irregulares. Todas las FST se combinaron en una sola utilizando un compilador de FST, que produjo una única FST que era mucho más pequeña que la suma de sus partes y corría muy rápido. Los FST pueden construirse mediante una variedad de herramientas que aceptan una sintaxis de expresión regular extendida.