stringtranslate.com

Construcción de conjuntos de potencia

En la teoría de la computación y la teoría de autómatas , la construcción de conjuntos potencia o construcción de subconjuntos es un método estándar para convertir un autómata finito no determinista (AFN) en un autómata finito determinista (AFD) que reconoce el mismo lenguaje formal . Es importante en teoría porque establece que los AFN, a pesar de su flexibilidad adicional, son incapaces de reconocer cualquier lenguaje que no pueda ser reconocido por algún AFD. También es importante en la práctica para convertir AFN más fáciles de construir en AFD ejecutables de manera más eficiente. Sin embargo, si el AFN tiene n estados, el AFD resultante puede tener hasta 2 n estados, un número exponencialmente mayor, lo que a veces hace que la construcción sea poco práctica para AFN grandes.

La construcción, a veces llamada construcción de conjunto de potencias de Rabin-Scott (o construcción de subconjuntos) 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 dada, es necesario realizar un seguimiento de un único estado en cualquier momento: el estado al que llegará el autómata después de ver un prefijo de la entrada. En cambio, para simular un NFA, es necesario realizar un seguimiento de un conjunto de estados: todos los estados a los que podría llegar el autómata después de ver el mismo prefijo de la entrada, según 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]

Construcción

La construcción de conjuntos potencia se aplica más directamente a un 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 5-tupla ( 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 asigna 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 que corresponden 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 ) | qS } , el conjunto de todos los estados a los que se puede llegar mediante una transición x desde un estado en S . Un estado S del DFA es un estado de aceptación si y solo si al menos un miembro de S es un estado de aceptación del NFA. [2] [3]

En la versión más simple de la construcción del conjunto potencia, el conjunto de todos los estados del DFA es el conjunto potencia 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 solo los estados que son realmente alcanzables. [4]

NFA con movimientos ε

En el caso de un NFA con ε-movimientos (también llamado ε-NFA), la construcción debe modificarse para abordar estos problemas calculando el ε- cierre de estados: el conjunto de todos los estados alcanzables desde un estado dado utilizando solo ε-movimientos. Van Noord reconoce tres formas posibles de incorporar este cálculo de cierre en la construcción del conjunto potencia: [5]

  1. Calcular el ε-cierre del autómata completo como un paso de preprocesamiento, produciendo un NFA equivalente sin ε-movimientos, luego aplicar la construcción de conjuntos de potencias regular. Esta versión, también analizada por Hopcroft y Ullman, [6] es sencilla de implementar, pero poco práctica para autómatas con una gran cantidad de ε-movimientos, como los que surgen comúnmente en aplicaciones de procesamiento de lenguaje natural . [5]
  2. Durante el cálculo del conjunto de potencias, calcule el cierre ε de cada estado q que considera el algoritmo (y almacene en caché el resultado).
  3. Durante el cálculo del conjunto potencia, calcule el ε-cierre de cada subconjunto de estados Q' que considera el algoritmo y agregue sus elementos a Q' .

Múltiples estados iniciales

Si se definen NFA 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 los estados iniciales mediante ε-movimientos.

Ejemplo

El siguiente NFA tiene cuatro estados: el estado 1 es inicial y los estados 3 y 4 son de aceptación. Su alfabeto consta de 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 desde {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 alcanzables desde el estado inicial del DFA; los 11 conjuntos restantes en el conjunto de potencia del conjunto de estados NFA no son alcanzables.

Complejidad

NFA con 5 estados (izquierda) cuyo DFA (derecha) requiere 16 estados. [4]

Como los estados DFA consisten en conjuntos de estados 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 alcanzable desde el subconjunto inicial, de modo que el DFA convertido tiene exactamente 2 n estados, lo que da una complejidad temporal de peor caso de Θ( 2 n ) . [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 n -ésimo desde el último de los cuales es 1. Puede representarse mediante un NFA de ( n + 1) estados, 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 de conjuntos de potencias 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 de conjuntos de potencias 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 funciona más rápido de lo que su complejidad en el peor de los casos sugeriría. [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 de conjunto potencia como parte de su maquinaria. [11]

Referencias

  1. ^ Rabin, MO ; Scott, D. (1959). "Autómatas finitos y sus problemas de decisión". Revista IBM de Investigación y Desarrollo . 3 (2): 114–125. doi :10.1147/rd.32.0114. ISSN  0018-8646.
  2. ^ abc Sipser, Michael (1997). "Teorema 1.19". Introducción a la teoría de la computación . pp. 55–56. ISBN 0-534-94728-X.
  3. ^ Hopcroft, John E. ; Ullman, Jeffrey D. (1979). "La equivalencia de DFA y NFA". Introducción a la teoría de autómatas, lenguajes y computación . Reading Massachusetts: Addison-Wesley. págs. 22-23. ISBN 0-201-02988-X.
  4. ^ abc Schneider, Klaus (2004). Verificación de sistemas reactivos: métodos formales y algoritmos. Springer. pp. 210–212. ISBN 978-3-540-00296-3.
  5. ^ ab Van Noord, Gertjan (2000). "Tratamiento de movimientos épsilon en la construcción de subconjuntos". Computational Linguistics . 26 (1): 61–76. arXiv : cmp-lg/9804003 . doi :10.1162/089120100561638. S2CID  5622079.
  6. ^ Hopcroft y Ullman (1979), págs. 26-27.
  7. ^ Rothe, Jörg (2006). Teoría de la complejidad y criptología: una introducción a la criptocomplejidad. Textos de informática teórica. Springer. pp. 21-22. ISBN 9783540285205..
  8. ^ Lupanov, Oleg B. (1963). "Una comparación de dos tipos de fuentes finitas". Problemy Kibernetiki . 9 : 321–326.
  9. ^ Moore, Frank R. (1971). "Sobre los límites para el tamaño del conjunto de estados en las pruebas de equivalencia entre autómatas finitos deterministas, no deterministas y bidireccionales". IEEE Transactions on Computers . C-20 (10): 1211–1214. doi :10.1109/TC.1971.223108. S2CID  206618275..
  10. ^ Brzozowski, JA (1963). "Expresiones regulares canónicas y gráficos de estado mínimos para eventos definidos". Proc. Sympos. Math. Theory of Automata (Nueva York, 1962) . Polytechnic Press del Instituto Politécnico de Brooklyn, Brooklyn, NY, págs. 529–561. MR  0175719.
  11. ^ 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..

Lectura adicional