En la teoría de la computación y la teoría de autómatas , la construcción de conjuntos de potencias o 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 las NFA, a pesar de su flexibilidad adicional, no pueden reconocer ningún lenguaje que no pueda ser reconocido por algunas 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 la NFA tiene n estados, la DFA resultante puede tener hasta 2 n estados, un número exponencialmente mayor, lo que a veces hace que la construcción no sea práctica para NFA grandes.
La construcción, a veces llamada construcción de conjunto de potencias Rabin-Scott (o construcción de subconjunto) 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]
Para simular el funcionamiento de un DFA en una cadena de entrada determinada, es necesario realizar un seguimiento de un único 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 una NFA, 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 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 desempeñan el mismo papel en la simulación NFA que los estados DFA individuales en la simulación DFA y, de hecho, los conjuntos de estados NFA que aparecen en esta simulación pueden reinterpretarse como estados de un DFA. [2]
La construcción del conjunto de poderes se aplica más directamente a una NFA que no permite transformaciones de estado sin consumir símbolos de entrada (también conocido como "ε-movimientos"). Un autómata de este tipo 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 (que mapea 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 asigna 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 alcanzarse mediante una transición x desde un estado en S . Un estado S de la DFA es un estado aceptador si y sólo si al menos un miembro de S es un estado aceptador de la NFA. [2] [3]
En la versión más simple de la construcción del conjunto de poderes, el conjunto de todos los estados del DFA es el conjunto de poderes de Q , el conjunto de todos los subconjuntos posibles 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 sólo los estados a los que realmente se puede llegar. [4]
Para un NFA con ε-movimientos (también llamado ε-NFA), la construcción debe modificarse para abordarlos calculando el ε- cierre de estados: el conjunto de todos los estados alcanzables desde un estado determinado usando solo ε-movimientos. Van Noord reconoce tres formas posibles de incorporar este cálculo de cierre en la construcción del conjunto de poderes: [5]
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 alcanzables desde estados iniciales por ε-movimientos.
La NFA a continuación tiene cuatro estados; El estado 1 es inicial y los estados 3 y 4 son de aceptación. 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 del NFA a los que se puede llegar 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 AFD completo construido a partir del AFN es como se muestra a continuación.
Como se puede ver en este ejemplo, hay cinco estados a los que se puede llegar desde el estado inicial del DFA; los 11 conjuntos restantes en el conjunto de poderes del conjunto de estados de la NFA no son accesibles.
Debido a que los estados de DFA constan de conjuntos de estados de NFA, un NFA de n estados puede convertirse en un DFA con como máximo 2 n estados. [2] Para cada n , existen NFA de n estados tales 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 ) complejidad temporal en el peor de los casos . [8] [9] Un ejemplo simple que requiere casi esta cantidad de estados es el lenguaje de cadenas sobre el alfabeto {0,1} en el que hay al menos n caracteres, el enésimo desde el último de los cuales es 1. Se puede representar por un NFA de estado ( n + 1) , pero requiere 2 n estados de DFA, uno para cada sufijo de n caracteres de la entrada; cf. imagen para n =4 . [4]
El algoritmo de Brzozowski para la minimización de DFA utiliza la construcción del conjunto de poderes 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 usando la construcción powerset y luego repite su proceso. Su complejidad en el peor de los casos es exponencial, a diferencia de otros algoritmos de minimización de DFA conocidos, pero en muchos ejemplos se ejecuta más rápidamente 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]
