Transductor de estados finitos

Esto contrasta con un autómata finito habitual, que tiene solamente una cinta.Podemos decir que el autómata reconoce una cadena si esta se encuentra en su cinta de entrada.En otras palabras, el autómata computa una función que convierte una cadena en un elemento del conjunto (0,1).Desde este punto de vista, el autómata genera un lenguaje formal, que no es más que un conjunto de cadenas.Los dos puntos de vista del autómata son equivalentes: la función que computa el autómata es la función indicadora del conjunto de cadenas reconocidas.Un transductor también puede no producir ninguna salida para una cadena de entrada, y en este caso se dice que el transductor rechaza la entrada.En general, un transductor establece una relación entre dos lenguajes formales.Los transductores de estados finitos se utilizan normalmente en análisis morfológico y en la investigación y aplicaciones de procesamiento del lenguaje natural.Formalmente un transductor de estados finitos T es una tupla (Q, Σ, Γ, I, F, δ) tal que: Se puede ver (Q, δ) como un grafo dirigido etiquetado, conocido como el grafo de transición de T: el conjunto de vértices es Q, yindica que hay una arista etiquetada que va del vértice q al vértice r. También se dice que a es la etiqueta de entrada y b la etiqueta de salida de esa arista.Se define la función de transición extendidacomo el conjunto más pequeño tal que: La relación de transición extendida es, esencialmente, cláusula transitiva reflexiva del grafo de transición que ha sido aumentada para tener en cuenta las etiquetas de las aristas.Esto significa que T transduce una cadenaLas siguientes operaciones definidas en autómatas finitos también se aplican a los transductores: No existe el concepto de intersección de transductores.Por el contrario, existe una operación de composición que es específica para los transductores, cuya construcción es parecida a la intersección de autómatas.