Construccion De Expresiones Regulares De Automatas Finitos Incluyendo Ciclos Multinodos
Páginas: 4 (888 palabras)
Publicado: 28 de octubre de 2012
CONSTRUCCION DE EXPRESIONES REGULARES DE AUTOMATAS FINITOS INCLUYENDO CICLOS MULTINODOS
Los autómatas han tenido muchas áreas de aplicación en la ciencia tales como análisis aritmético oreconocimientos de patrones solo por mencionar algunas de sus aplicaciones. La investigación en el campo de la teoría de autómatas continuamente nos provee el teorema de equivalencia entre los autómatasfinitos y expresiones regulares, pero también nos muestra el problema en las reglas de construcción cuando se utilizan ciclos multinodos. Por ello se propone una aproximación para la construcción deexpresiones regulares a partir de autómatas finitos cuando se incluyan multinodos.
EQUIVALENCIA ENTRE EXPRESIONES REGULARES Y AFDs
Teorema 1: dado un autómata finito determinístico M sobre elalfabeto ∑, existe una expresión regular e, tal que L(M)=L(e), y viceversa.
Para mostrar las condiciones suficientes, eliminamos los nodos y aristas, hasta dejar solo el estado de aceptación y deinicio como se muestra en la parte izquierda de la Fig.1.
Ahora para las condiciones necesarias de este teorema se transforma la formula en la Fig1 para reconstruirlo en la Fig2, en donde se estableceel estado de inicio como 1 y el estado de acaptacion como n, la etiqueta de la arista (1,n) será una expresión regular e. Entonces si añadimos más nodos y aristas continuamente, hasta que la etiquetaen cada arista es un carácter en ∑, tal que el resultado final es un autómata correspondiente a la expresión regular e.
Aparentemente hay un solo nodo en el ciclo en las reglas de construcción enla Fig1. De ahí que ciclos de multiples nodos pudieran ser transformados en un ciclo de un nodo especial usando estas reglas. Pero ciertamente esto es un error como se ve en el siguiente ejemplo.Nodos 2 y 3 construyen un loop, sin embargo no puede ser construido directamente con las reglas en Fig1.
Es aquí donde aparece un método llamado fusión de nodos, en el cual un autómata que incluya...
Los autómatas han tenido muchas áreas de aplicación en la ciencia tales como análisis aritmético oreconocimientos de patrones solo por mencionar algunas de sus aplicaciones. La investigación en el campo de la teoría de autómatas continuamente nos provee el teorema de equivalencia entre los autómatasfinitos y expresiones regulares, pero también nos muestra el problema en las reglas de construcción cuando se utilizan ciclos multinodos. Por ello se propone una aproximación para la construcción deexpresiones regulares a partir de autómatas finitos cuando se incluyan multinodos.
EQUIVALENCIA ENTRE EXPRESIONES REGULARES Y AFDs
Teorema 1: dado un autómata finito determinístico M sobre elalfabeto ∑, existe una expresión regular e, tal que L(M)=L(e), y viceversa.
Para mostrar las condiciones suficientes, eliminamos los nodos y aristas, hasta dejar solo el estado de aceptación y deinicio como se muestra en la parte izquierda de la Fig.1.
Ahora para las condiciones necesarias de este teorema se transforma la formula en la Fig1 para reconstruirlo en la Fig2, en donde se estableceel estado de inicio como 1 y el estado de acaptacion como n, la etiqueta de la arista (1,n) será una expresión regular e. Entonces si añadimos más nodos y aristas continuamente, hasta que la etiquetaen cada arista es un carácter en ∑, tal que el resultado final es un autómata correspondiente a la expresión regular e.
Aparentemente hay un solo nodo en el ciclo en las reglas de construcción enla Fig1. De ahí que ciclos de multiples nodos pudieran ser transformados en un ciclo de un nodo especial usando estas reglas. Pero ciertamente esto es un error como se ve en el siguiente ejemplo.Nodos 2 y 3 construyen un loop, sin embargo no puede ser construido directamente con las reglas en Fig1.
Es aquí donde aparece un método llamado fusión de nodos, en el cual un autómata que incluya...
Leer documento completo
Regístrate para leer el documento completo.