[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):
ıllı Transductor de estados finitos : que es, definición y significado, descargar videos y fotos.
- Detalles
- Categoría: INTERNET
ıllı Transductor de estados finitos : que es, definición y significado, descargar videos y fotos.
Un transductor de estados finitos, o bien transductor finito, es un robot finito (o bien máquina de estados finitos) con 2 cintas, una de entrada y otra de salida. Esto contrasta con un robot finito frecuente, que tiene únicamente una cinta. Podemos decir que el autómatareconoce una cadena si esta se halla en su cinta de entrada. En otras palabras, el androide computa una función que transforma una cadena en un factor del conjunto (0,1). Por otro lado, podemos decir que un robot produce cadenas desde su cinta de salida. Desde este punto de vista, el androide produce un lenguaje formal, que no es más que un conjunto de cadenas. Los 2 puntos de vista del androide son equivalentes: la función que computa el robot es la función indicadora del conjunto de cadenas reconocidas. La clase de lenguajes generados por un androide finito se conoce con el nombre de lenguajes regulares Típicamente las 2 cintas de un transductor se ven como una cinta de entrada y otra de salida. Desde este punto de vista, un transductor diríase que transduce (traduce) el contenido de la cinta de entrada a la cinta de salida, a través de la aceptación de una cadena en la cinta de entrada, y la generación de otra cadena en la cinta de salida. Esta transducción se puede efectuar de forma no determinista y entonces se generará más de una salida por cada cadena de entrada. Un transductor asimismo puede no generar ninguna salida para una cadena de entrada, y en un caso así diríase que el transductor rechaza la entrada. Por norma general, un transductor establece una relación entre 2 lenguajes formales. La clase de relaciones computadas por un transductor de estados finitos se conoce como una clase de relaciones racionales. Los transductores de estados finitos se emplean por norma general 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, S, G, I, F, d) tal que: Se puede ver (Q, d) como un grafo dirigido etiquetado, conocido como el grafo de transición de T: el conjunto de vértices es Q, y (q,a,b,r)?dundefined señala que hay una arista etiquetada que va del vértice q al vértice r. Asimismo diríase que a es la etiqueta de entrada y b la etiqueta de salida de esa arista. Esta definición de traductor de estados finitos asimismo se conoce como traductor de letras (Roche and Schabes mil novecientos noventa y siete); hay otras definiciones posible, mas todas y cada una se pueden producir partiendo de esta. Se define la función de transición extendidad*undefined como el conjunto más pequeño tal que: La relación de transición extendida es, fundamentalmente, cláusula transitiva reflexiva del grafo de transición que ha sido aumentada para tomar en consideración las etiquetas de las aristas. Los elementos de d*undefined se conocen como caminos. Las etiquetas de la aristas de un camino se consiguen concadenando las etiquetas de las aristas de las transiciones que se han generado en orden. El comportamiento del transductor T es la relación racional definida como sigue: xyundefinedsi y solo si existe i?Iundefined y f?Fundefined tal que (i,x,y,f)?d*undefined. Esto quiere decir que T transduce una cadena x?S*undefined en una cadena y?G*undefined si hay un camino desde un estado inicial hasta un estado final con entrada x y salida y. Las siguientes operaciones definidas en androides finitos asimismo se aplican a los transductores: No existe el término de intersecció de transductores. Por contra, hay una operación de composición que es concreta para los transductores, cuya construcción es semejante a la intersección de androides. La composición se define como sigue: También se puede se puede projectar una cinta del transductor para conseguir un androide. Hay 2 funciones de projección: p1undefined conserva la cinta de entrada, y p2undefined conserva la de salida. La primera projección (p1undefined) se define como sigue: La segunda projección (p2undefined) se puede delimitar de forma similar.