En la teoría de la computación y la teoría de autómatas , la construcción de conjuntos de poder o la construcción de subconjuntos es un método estándar para convertir un autómata finito no determinista (NFA) en un autómata finito determinista (DFA) que reconoce el mismo lenguaje formal . Es importante en teoría porque establece que los NFA, a pesar de su flexibilidad adicional, no pueden reconocer ningún idioma que no pueda ser reconocido por algunos DFA. También es importante en la práctica para convertir NFA más fáciles de construir en DFA ejecutables de manera más eficiente. Sin embargo, si el NFA tiene n estados, el DFA resultante puede tener hasta 2 n afirma, un número exponencialmente mayor, lo que a veces hace que la construcción no sea práctica para grandes NFA.
La construcción, a veces llamada construcción (o construcción de subconjunto) Rabin-Scott powerset para distinguirla de construcciones similares para otros tipos de autómatas, fue publicada por primera vez por Michael O. Rabin y Dana Scott en 1959. [1]
Intuición
Para simular el funcionamiento de un DFA en una cadena de entrada determinada, es necesario realizar un seguimiento de un solo estado en cualquier momento: el estado que alcanzará el autómata después de ver un prefijo de la entrada. Por el contrario, para simular un AFN, es necesario realizar un seguimiento de un conjunto de estados: todos los estados que el autómata podría alcanzar después de ver el mismo prefijo de la entrada, de acuerdo con las elecciones no deterministas realizadas por el autómata. Si, después de un cierto prefijo de la entrada, se puede alcanzar un conjunto S de estados, entonces después del siguiente símbolo de entrada x, el conjunto de estados alcanzables es una función determinista de S y x . Por lo tanto, los conjuntos de estados NFA alcanzables juegan el mismo papel en la simulación NFA que los estados DFA individuales juegan en la simulación DFA y, de hecho, los conjuntos de estados NFA que aparecen en esta simulación pueden ser reinterpretados como estados de un DFA. [2]
Construcción
La construcción del conjunto de potencias se aplica más directamente a un NFA que no permite transformaciones de estado sin consumir símbolos de entrada (también conocido como: "ε-move"). Tal autómata puede definirse como una tupla de 5 ( Q , Σ, T , q 0 , F ) , en la que Q es el conjunto de estados, Σ es el conjunto de símbolos de entrada, T es la función de transición (mapeo de un estado y un símbolo de entrada a un conjunto de estados), q 0 es el estado inicial y F es el conjunto de estados de aceptación. El DFA correspondiente tiene estados correspondientes a subconjuntos de Q . El estado inicial del DFA es { q 0 } , el conjunto (de un elemento) de estados iniciales. La función de transición del DFA mapea un estado S (que representa un subconjunto de Q ) y un símbolo de entrada x al conjunto T ( S , x ) = ∪ { T ( q , x ) | q ∈ S } , el conjunto de todos los estados que pueden ser alcanzados por un x -Transición de un estado en S . Un estado S de la DFA es un estado de aceptación si y solo si al menos un miembro de S es un estado de aceptación de la NFA. [2] [3]
En la versión más simple de la construcción de conjunto potencia, el conjunto de todos los estados de la DFA es la powerset de Q , el conjunto de todos los posibles subconjuntos de Q . Sin embargo, muchos estados del DFA resultante pueden ser inútiles, ya que pueden ser inalcanzables desde el estado inicial. Una versión alternativa de la construcción crea solo los estados que son realmente alcanzables. [4]
NFA con movimientos ε
Para un NFA con ε-movimientos (también llamado ε-NFA), la construcción debe modificarse para lidiar con ellos calculando el ε- cierre de estados: el conjunto de todos los estados alcanzables desde algún estado dado usando solo ε-movimientos. Van Noord reconoce tres posibles formas de incorporar este cálculo de cierre en la construcción del conjunto de potencias: [5]
- Calcule el cierre ε de todo el autómata como un paso de preprocesamiento, produciendo un NFA equivalente sin movimientos ε, luego aplique la construcción regular del conjunto de potencias. Esta versión, también discutida por Hopcroft y Ullman, [6] es fácil de implementar, pero impráctica para autómatas con un gran número de movimientos ε, como surgen comúnmente en aplicaciones de procesamiento de lenguaje natural . [5]
- Durante el cálculo de powerset, calcule el cierre ε de cada estado q que es considerado por el algoritmo (y cachear el resultado).
- Durante el cálculo de powerset, calcule el cierre ε de cada subconjunto de estados Q ' que es considerado por el algoritmo, y agrega sus elementos a Q' .
Varios estados iniciales
Si los NFA se definen para permitir múltiples estados iniciales, [7] el estado inicial del DFA correspondiente es el conjunto de todos los estados iniciales del NFA, o (si el NFA también tiene movimientos ε) el conjunto de todos los estados accesibles desde estados iniciales por ε-movimientos.
Ejemplo
La NFA a continuación tiene cuatro estados; el estado 1 es inicial y los estados 3 y 4 se aceptan. Su alfabeto consta de los dos símbolos 0 y 1, y tiene movimientos ε.
El estado inicial del DFA construido a partir de este NFA es el conjunto de todos los estados NFA que son alcanzables desde el estado 1 mediante ε-movimientos; es decir, es el conjunto {1,2,3}. Una transición de {1,2,3} mediante el símbolo de entrada 0 debe seguir la flecha del estado 1 al estado 2, o la flecha del estado 3 al estado 4. Además, ni el estado 2 ni el estado 4 tienen movimientos ε salientes. Por lo tanto, T ({1,2,3}, 0) = {2,4}, y por el mismo razonamiento, el DFA completo construido a partir del NFA es como se muestra a continuación.
Como se puede ver en este ejemplo, hay cinco estados accesibles desde el estado inicial del DFA; los 11 conjuntos restantes en el conjunto de potencia del conjunto de estados NFA no son accesibles.
Complejidad
Debido a que los estados de DFA constan de conjuntos de estados de NFA, un NFA de n- estados se puede convertir en un DFA con un máximo de 2 n estados. [2] Para cada n , existen NFA de n estados, de modo que cada subconjunto de estados es accesible desde el subconjunto inicial, de modo que el DFA convertido tiene exactamente 2 n estados, lo que da Θ ( 2 n ) una complejidad de tiempo en el peor de los casos . [8] [9] Un ejemplo simple que requiere casi tantos estados es el lenguaje de las cadenas sobre el alfabeto {0,1} en el que hay al menos n caracteres, el n º de la última de las cuales es 1. Se puede representar por un NFA de estado ( n + 1) , pero requiere 2 n estados DFA, uno para cada sufijo de n caracteres de la entrada; cf. imagen para n = 4 . [4]
Aplicaciones
El algoritmo de Brzozowski para la minimización de DFA utiliza la construcción del conjunto de potencia, dos veces. Convierte el DFA de entrada en un NFA para el lenguaje inverso, invirtiendo todas sus flechas e intercambiando los roles de los estados inicial y de aceptación, convierte el NFA nuevamente en un DFA utilizando la construcción del conjunto de potencias y luego repite su proceso. Su complejidad en el peor de los casos es exponencial, a diferencia de otros algoritmos conocidos de minimización de DFA, pero en muchos ejemplos funciona más rápido de lo que sugeriría su complejidad en el peor de los casos. [10]
La construcción de Safra , que convierte un autómata Büchi no determinista con n estados en un autómata Muller determinista o en un autómata Rabin determinista con 2 O ( n log n ) estados, utiliza la construcción powerset como parte de su maquinaria. [11]
Referencias
- ^ Rabin, MO ; Scott, D. (1959). "Autómatas finitos y sus problemas de decisión". Revista de investigación y desarrollo de IBM . 3 (2): 114-125. doi : 10.1147 / rd.32.0114 . ISSN 0018-8646 .
- ^ a b c Sipser, Michael (1997). "Teorema 1,19". Introducción a la Teoría de la Computación . págs. 55–56 . ISBN 0-534-94728-X.
- ^ Hopcroft, John E .; Ullman, Jeffrey D. (1979). "La equivalencia de DFA y NFA". Introducción a la teoría, los lenguajes y la computación de los autómatas . Lectura de Massachusetts: Addison-Wesley. págs. 22-23 . ISBN 0-201-02988-X.
- ^ a b c Schneider, Klaus (2004). Verificación de sistemas reactivos: métodos formales y algoritmos . Saltador. págs. 210–212. ISBN 978-3-540-00296-3.
- ^ a b Van Noord, Gertjan (2000). "Tratamiento de movimientos épsilon en la construcción de subconjuntos" . Lingüística computacional . 26 (1): 61–76. arXiv : cmp-lg / 9804003 . doi : 10.1162 / 089120100561638 . S2CID 5622079 .
- ^ Hopcroft y Ullman (1979) , págs. 26-27.
- ^ Rothe, Jörg (2006). Teoría de la complejidad y criptología: una introducción a la criptocomplejidad . Textos en Informática Teórica. Saltador. págs. 21-22. ISBN 9783540285205..
- ^ Lupanov, Oleg B. (1963). "Una comparación de dos tipos de fuentes finitas". Problemy Kibernetiki . 9 : 321–326.
- ^ Moore, Frank R. (1971). "Sobre los límites del tamaño del conjunto de estados en las pruebas de equivalencia entre autómatas deterministas, no deterministas y finitos bidireccionales". Transacciones IEEE en computadoras . C-20 (10): 1211–1214. doi : 10.1109 / TC.1971.223108 . S2CID 206618275 ..
- ^ Brzozowski, JA (1963). "Expresiones regulares canónicas y gráficos de estado mínimo para eventos definidos". Proc. Simpos. Matemáticas. Theory of Automata (Nueva York, 1962) . Prensa Politécnica del Instituto Politécnico. de Brooklyn, Brooklyn, NY págs. 529–561. Señor 0175719 .
- ^ Safra, S. (1988). "Sobre la complejidad de los ω-autómatas". Actas del 29º Simposio Anual sobre Fundamentos de la Ciencia de la Computación (FOCS '88) . Washington, DC, EE.UU .: IEEE Computer Society. págs. 319–327. doi : 10.1109 / SFCS.1988.21948 ..
Otras lecturas
- Anderson, James Andrew (2006). Teoría de los autómatas con aplicaciones modernas . Prensa de la Universidad de Cambridge. págs. 43–49. ISBN 978-0-521-84887-9.