Hispanopedia Wiki
Articulo de referencia

minimización de DFA

Ejemplo de DFA. Si está en estado do {\displaystyle c} , exhibe el mismo comportamiento para cada cadena de entrada que en el estado d {\displaystyle d} o en el estado mi {\disp...

Hispanopedia WikiContenido en espanolLectura gratuita
Ejemplo de DFA. Si está en estadodo{\displaystyle c}, exhibe el mismo comportamiento para cada cadena de entrada que en el estadod{\displaystyle d}o en el estadomi{\displaystyle e}De manera similar, los estadosa{\displaystyle a}yb{\displaystyle b}son indistinguibles. El DFA no tiene estados inalcanzables.
Autómata finito determinista mínimo equivalente. Los estados indistinguibles se han fusionado en uno solo.

En la teoría de autómatas (una rama de la informática teórica ), la minimización de autómatas finitos deterministas (AFD) consiste en transformar un autómata finito determinista (AFD) dado en un AFD equivalente con un número mínimo de estados. En este contexto, dos AFD se consideran equivalentes si reconocen el mismo lenguaje regular . Existen varios algoritmos que realizan esta tarea y que se describen en los libros de texto estándar sobre teoría de autómatas. [ 1 ]

DFA mínimo

Para cada lenguaje regular, existe un autómata determinista mínimo que lo acepta, es decir, un autómata finito determinista (AFD) con un número mínimo de estados. Según el teorema de Myhill-Nerode , este AFD es único (excepto que los estados pueden tener nombres diferentes). [ 2 ] [ 3 ] El AFD mínimo garantiza un costo computacional mínimo para tareas como la coincidencia de patrones .

Existen tres clases de estados que pueden eliminarse o fusionarse del autómata finito determinista (AFD) original sin afectar el lenguaje que acepta.

  • Los estados inalcanzables son aquellos que no se pueden alcanzar desde el estado inicial del autómata finito determinista (AFD) para ninguna cadena de entrada. Estos estados se pueden eliminar.
  • Los estados muertos son aquellos desde los que no se puede alcanzar ningún estado final. Estos estados pueden eliminarse a menos que se requiera que el autómata esté completo .
  • Los estados indistinguibles son aquellos que no se pueden diferenciar entre sí para ninguna cadena de entrada. Estos estados se pueden fusionar.

La minimización de DFA generalmente se realiza en tres pasos:

  1. eliminar estados muertos e inaccesibles (esto acelerará el siguiente paso),
  2. fusionar estados no distinguibles,
  3. Opcionalmente, se puede recrear un único estado muerto (estado "sumidero") si se requiere que el autómata finito determinista resultante esté completo.

Estados inalcanzables

El estadopag{\displaystyle p}de un autómata finito deterministaMETRO=(Q,Σ,δ,q0,F){\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}es inalcanzable si no hay cadenaw{\displaystyle w}enΣ∗{\displaystyle \Sigma ^{*}}existe para el cualpag=δ∗(q0,w){\displaystyle p=\delta ^{*}(q_{0},w)}. En esta definición,Q{\displaystyle Q}es el conjunto de estados,Σ{\displaystyle \Sigma }es el conjunto de símbolos de entrada,δ{\displaystyle \delta }es la función de transición (mapear un estado y un símbolo de entrada a un conjunto de estados),δ∗{\displaystyle \delta ^{*}}es su extensión a cadenas (también conocida como función de transición extendida),q0{\displaystyle q_{0}}es el estado inicial, yF{\displaystyle F}es el conjunto de estados de aceptación (también conocidos como estados finales). Los estados alcanzables se pueden obtener con el siguiente algoritmo:

let reachable_states := { q0 } let new_states := { q0 }hacer { temp := el conjunto vacío para cada q en new_states hacer para cada c en Σ hacer temp := temp ∪ { δ ( q , c )} new_states := temp \ reachable_states reachable_states := reachable_states ∪ new_states } mientras ( new_states ≠ el conjunto vacío )estados_inalcanzables := Q \ estados_alcanzables

Suponiendo una implementación eficiente de los conjuntos de estados (por ejemplo new_states) y operaciones sobre ellos (como agregar un estado o verificar si está presente), este algoritmo puede implementarse con una complejidad temporalO(norte+metro){\displaystyle O(n+m)}, dóndenorte{\displaystyle n}es el número de estados ymetro{\displaystyle m}es el número de transiciones del autómata de entrada.

Los estados inalcanzables pueden eliminarse del autómata finito determinista (AFD) sin afectar al lenguaje que acepta.

Estados no distinguibles

Los siguientes algoritmos presentan diversos enfoques para fusionar estados indistinguibles.

El algoritmo de Hopcroft

Un algoritmo para fusionar los estados indistinguibles de un autómata finito determinista (AFD), propuesto por Hopcroft (1971) , se basa en el refinamiento de particiones , dividiendo los estados del AFD en grupos según su comportamiento. Estos grupos representan clases de equivalencia de la congruencia de Nerode , donde dos estados son equivalentes si presentan el mismo comportamiento para cada secuencia de entrada. Es decir, para cada par de estados p₁ y p₂ pertenecientes al mismo bloque de la partición P , y para cada palabra de entrada w , las transiciones determinadas por w siempre deben llevar los estados p₁ y p₂ a estados que ambos aceptan o a estados que ambos rechazan. No debería ser posible que w lleve p₁ a un estado de aceptación y p₂ a un estado de rechazo , ni viceversa.

El siguiente pseudocódigo describe la forma del algoritmo según lo dado por Xu. [ 4 ] También se han presentado formas alternativas. [ 5 ] [ 6 ]

P := { F , Q \ F } W := { F , Q \ F }mientras ( W no esté vacío ) haga elija y elimine un conjunto A de W para cada c en Σ haga X el conjunto de estados para los cuales una transición en c conduce a un estado en A para cada conjunto Y en P para el cual X ∩ Y no está vacío y Y \ X no está vacío haga reemplace Y en P por los dos conjuntos X ∩ Y e Y \ X si Y está en W reemplace Y en W por los mismos dos conjuntos sino si | X ∩ Y | < = | Y \ X | agregue X ∩ Y a W sino agregue Y \ X a W

El algoritmo comienza con una partición demasiado gruesa: cada par de estados que son equivalentes según la congruencia de Nerode pertenecen al mismo conjunto en la partición, pero los pares que no son equivalentes también podrían pertenecer al mismo conjunto. Refina gradualmente la partición en un mayor número de conjuntos más pequeños, dividiendo en cada paso los conjuntos de estados en pares de subconjuntos que son necesariamente no equivalentes. La partición inicial es una separación de los estados en dos subconjuntos de estados que claramente no tienen el mismo comportamiento entre sí: los estados de aceptación y los estados de rechazo. Luego, el algoritmo elige repetidamente un conjunto A de la partición actual y un símbolo de entrada c , y divide cada uno de los conjuntos de la partición en dos subconjuntos (posiblemente vacíos): el subconjunto de estados que conducen a A con el símbolo de entrada c , y el subconjunto de estados que no conducen a A. Dado que ya se sabe que A tiene un comportamiento diferente al de los otros conjuntos de la partición, los subconjuntos que conducen a A también tienen un comportamiento diferente al de los subconjuntos que no conducen a A. Cuando ya no se encuentran más divisiones de este tipo, el algoritmo finaliza.

Lema . Dado un carácter fijo c y una clase de equivalencia Y que se divide en clases de equivalencia B y C , solo se necesita una de B o C para refinar toda la partición. [ 7 ]

Ejemplo: Supongamos que tenemos una clase de equivalencia Y que se divide en las clases de equivalencia B y C. Supongamos también que tenemos las clases D , E y F ; D y E tienen estados con transiciones a B en el carácter c , mientras que F tiene transiciones a C en el carácter c . Según el lema, podemos elegir B ​​o C como discriminador, digamos B. Entonces, los estados de D y E se dividen por sus transiciones a B. Pero F , que no apunta a B , simplemente no se divide durante la iteración actual del algoritmo; se refinará mediante otros discriminadores.

Observación . Es necesario tener todos los elementos B o C para dividir correctamente las clases de referencia como D , E y F ; los subconjuntos no servirán.

El propósito de la ifinstrucción más externa ( if Y is in W) es completar W , el conjunto de distinguidores. Vemos en la instrucción anterior del algoritmo que Y acaba de ser dividido. Si Y está en W , se ha vuelto obsoleto como medio para dividir clases en iteraciones futuras. Por lo tanto, Y debe ser reemplazado por ambas divisiones debido a la Observación anterior. Sin embargo, si Y no está en W , solo una de las dos divisiones, no ambas, necesita ser agregada a W debido al Lema anterior. Elegir la división más pequeña de las dos garantiza que la nueva adición a W no sea más de la mitad del tamaño de Y ; este es el núcleo del algoritmo de Hopcroft: cómo obtiene su velocidad, como se explica en el siguiente párrafo.

El tiempo de ejecución en el peor de los casos de este algoritmo es O ( ns log n ) , donde n es el número de estados y s es el tamaño del alfabeto. Este límite se deriva del hecho de que, para cada una de las ns transiciones del autómata, los conjuntos extraídos de Q que contienen el estado objetivo de la transición tienen tamaños que disminuyen entre sí por un factor de dos o más, por lo que cada transición participa en O (log n ) de los pasos de división en el algoritmo. La estructura de datos de refinamiento de partición permite que cada paso de división se realice en un tiempo proporcional al número de transiciones que participan en él. [ 8 ] Este sigue siendo el algoritmo más eficiente conocido para resolver el problema, y ​​para ciertas distribuciones de entradas su complejidad en el caso promedio es incluso mejor, O ( n log log n ) . [ 6 ]

Una vez que se ha utilizado el algoritmo de Hopcroft para agrupar los estados del autómata finito determinista (AFD) de entrada en clases de equivalencia, se puede construir el AFD mínimo formando un estado para cada clase de equivalencia. Si S es un conjunto de estados en P , s es un estado en S y c es un carácter de entrada, entonces la transición en el AFD mínimo desde el estado para S , con la entrada c , va al conjunto que contiene el estado al que iría el autómata de entrada desde el estado s con la entrada c . El estado inicial del AFD mínimo es el que contiene el estado inicial del AFD de entrada, y los estados de aceptación del AFD mínimo son aquellos cuyos miembros son estados de aceptación del AFD de entrada.

El algoritmo de Moore

El algoritmo de Moore para la minimización de DFA se debe a Edward F. Moore ( 1956 ) . Al igual que el algoritmo de Hopcroft, mantiene una partición que inicialmente separa los estados de aceptación de los de rechazo, y refina repetidamente la partición hasta que no se pueden realizar más refinamientos. En cada paso, reemplaza la partición actual con el refinamiento común más grueso de s + 1 particiones, una de las cuales es la actual y el resto son las preimágenes de la partición actual bajo las funciones de transición para cada uno de los símbolos de entrada. El algoritmo termina cuando este reemplazo no cambia la partición actual. Su complejidad temporal en el peor de los casos es O ( n 2 s ) : cada paso del algoritmo puede realizarse en tiempo O ( ns ) utilizando una variante de ordenación por radix para reordenar los estados de manera que los estados en el mismo conjunto de la nueva partición sean consecutivos en el orden, y hay como máximo n pasos ya que cada uno, excepto el último, aumenta el número de conjuntos en la partición. Las instancias del problema de minimización del DFA que causan el comportamiento en el peor de los casos son las mismas que para el algoritmo de Hopcroft. El número de pasos que realiza el algoritmo puede ser mucho menor que n , por lo que en promedio (para s constante ) su rendimiento es O ( n log n ) o incluso O ( n log log n ) dependiendo de la distribución aleatoria de autómatas elegida para modelar el comportamiento en el caso promedio del algoritmo. [ 6 ] [ 9 ] 

El algoritmo de Brzozowski

Invertir las transiciones de un autómata finito no determinista (AFN)METRO{\displaystyle M}y el intercambio de estados inicial y final [ nota 1 ] produce un autómata finito no determinista (AFND)METROR{\displaystyle M^{R}}para la inversión del lenguaje original. Convertir este NFA a un DFA utilizando la construcción estándar del conjunto potencia (manteniendo solo los estados alcanzables del DFA convertido) conduce a un DFAMETRODR{\displaystyle M_{D}^{R}}para el mismo lenguaje invertido. Como observó Brzozowski (1963) , al repetir esta inversión y determinización una segunda vez, manteniendo nuevamente solo los estados alcanzables, se obtiene el autómata finito determinista mínimo para el lenguaje original.

La idea subyacente al algoritmo es la siguiente: al determinizar el autómata inverso, se fusionan estados que no se distinguen en el autómata original, pero que pueden generar varios estados de aceptación. En tal caso, al invertir el autómata por segunda vez, estos estados de aceptación se convierten en iniciales, por lo que el autómata deja de ser determinista al tener múltiples estados iniciales. Por ello, es necesario determinizarlo de nuevo, obteniendo así el autómata finito determinista mínimo.

Prueba de corrección

Después de que determinemosMETROR{\displaystyle M^{R}}para obtenerMETRODR{\displaystyle M_{D}^{R}}, revertimos estoMETRODR{\displaystyle M_{D}^{R}}para obtener(METRODR)R=METRO′{\displaystyle (M_{D}^{R})^{R}=M'}. AhoraMETRO′{\displaystyle M'}reconoce el mismo idioma queMETRO{\displaystyle M}, pero hay una diferencia importante: no hay dos estados enMETRO′{\displaystyle M'}de la cual podemos aceptar la misma palabra. Esto se deduce deMETRODR{\displaystyle M_{D}^{R}}siendo determinista, es decir, no hay dos estados enMETRODR{\displaystyle M_{D}^{R}}que podemos alcanzar desde el estado inicial a través de la misma palabra. La determinización deMETRO′{\displaystyle M'}luego crea estados de potencia (conjuntos de estados deMETRO′{\displaystyle M'}), donde cada dos estados de potenciaR,S{\displaystyle {\mathcal {R}},{\mathcal {S}}}difieren – naturalmente – en al menos un estadoq{\displaystyle q}deMETRO′{\displaystyle M'}. Asumirq∈R{\displaystyle q\in {\mathcal {R}}}yq∉S{\displaystyle q\not \in {\mathcal {S}}}; entoncesq{\displaystyle q}aporta al menos una palabra [ nota 2 ] al idioma deR{\displaystyle {\mathcal {R}}}, [ nota 3 ] que no podría estar presente enS{\displaystyle {\mathcal {S}}}, ya que esta palabra es única deq{\displaystyle q}(ningún otro estado lo acepta). Vemos que esto se cumple para cada par de estados de poder, y por lo tanto cada estado de poder es distinguible de cualquier otro estado de poder. Por consiguiente, después de la determinización deMETRO′{\displaystyle M'}Tenemos un DFA sin estados indistinguibles o inalcanzables; por lo tanto, el DFA mínimoMETRO¯{\displaystyle {\overline {M}}}para el originalMETRO{\displaystyle M}.

Complejidad

La complejidad en el peor de los casos del algoritmo de Brzozowski es exponencial con respecto al número de estados del autómata de entrada. Esto se cumple independientemente de si la entrada es un autómata finito no determinista (AFND) o un autómata finito determinista (AFD). En el caso de un AFD, la explosión exponencial puede ocurrir durante la determinización de la inversión del autómata de entrada; [ nota 4 ] en el caso de un AFND, también puede ocurrir durante la determinización inicial del autómata de entrada. [ nota 5 ] Sin embargo, el algoritmo suele tener un rendimiento mejor del que sugeriría este peor caso. [ 6 ]

minimización de NFA

Si bien los procedimientos anteriores funcionan para los autómatas finitos deterministas (AFD), el método de partición no funciona para los autómatas finitos no deterministas (AFN). [ 10 ] Si bien una búsqueda exhaustiva puede minimizar un AFN, no existe un algoritmo de tiempo polinomial para minimizar AFN generales a menos que P = PSPACE , una conjetura sin resolver en la teoría de la complejidad computacional que se considera ampliamente falsa. Sin embargo, existen métodos de minimización de AFN que pueden ser más eficientes que la búsqueda por fuerza bruta. [ 11 ]

Para un lenguaje dado, pueden existir varios autómatas finitos no deterministas (AFND) con estados mínimos estructuralmente diferentes (es decir, no isomorfos ). Estos pueden tener estrictamente menos estados que el único autómata finito determinista (AFD) mínimo (ejemplo aquí ).

Véase también

Notas

  1. ↑ Hopcroft, Motwani y Ullman (2001) , Sección 4.4.3, "Minimización de DFA".
  2. ↑ Hopcroft y Ullman (1979) , Sección 3.4, Teorema 3.10, pág. 67
  3. ↑ Hopcroft, Motwani y Ullman (2001) , Sección 4.4.3, "Minimización de DFA", pág. 159 y pág. 164 (observación después del Teorema 4.26)
  4. ↑ Xu, Yingjie (2009). "Descripción de un algoritmo n log n para minimizar estados en un autómata finito determinista" (PDF) . pág.  5. S2CID 14461400 . 
  5. ↑ Knuutila (2001)
  6. ^ Berstel y cols . (2010) .
  7. ↑ Basado en el Corolario 10 de Knuutila (2001)
  8. ↑ Hopcroft (1971) ; Aho, Hopcroft y Ullman (1974)
  9. ↑ David (2012) .
  10. ↑ Hopcroft, Motwani y Ullman (2001) , Sección 4.4, Figura titulada "Minimizando los estados de un NFA", pág. 163.
  11. ↑ Kameda y Weiner (1970) .
  1. ↑ En caso de que haya varios estados finales en M , debemos permitir múltiples estados iniciales en la inversión de M ; o agregar un estado extra con transiciones ε a todos los estados iniciales y hacer que solo este nuevo estado sea inicial.
  2. ↑ Recordemos que no hay estados muertos en M '; por lo tanto, se acepta al menos una palabra de cada estado.
  3. ↑ El idioma de un estado es el conjunto de palabras aceptadas de ese estado.
  4. ↑ Por ejemplo, el lenguaje de cadenas binarias cuyo n- ésimo símbolo es un uno requiere solo n + 1 estados, pero su inversión requiere 2 n estados. Leiss (1981) proporciona un autómata finito determinista (AFD) ternario de n estados cuya inversión requiere 2 n estados, el máximo posible. Para ver ejemplos adicionales y la observación de la conexión entre estos ejemplos y el análisis del peor caso del algoritmo de Brzozowski, consulte Câmpeanu et al. (2001) .
  5. ↑ La explosión exponencial ocurrirá como máximo una vez, no en ambas determinaciones. Es decir, el algoritmo es, en el peor de los casos, exponencial, no doblemente exponencial.

Referencias

  • Aho, Alfred V.; Hopcroft , John E .; Ullman, Jeffrey D. ( 1974), "4.13 Particionamiento", El diseño y análisis de algoritmos informáticos , Addison-Wesley, págs. 157–162 .
  • Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle (2010), "Minimización de autómatas", Autómatas: de las matemáticas a las aplicaciones , Sociedad Matemática Europea , arXiv : 1010.5318 , Bibcode : 2010arXiv1010.5318B
  • Brzozowski, JA (1963), "Expresiones regulares canónicas y grafos de estados mínimos para eventos definidos", Actas del Simposio sobre Teoría Matemática de Autómatas (Nueva York, 1962) , Polytechnic Press del Instituto Politécnico de Brooklyn, Brooklyn, NY, págs. 529–561 , MR 0175719  .
  • Câmpeanu, Cezar; Culik, Karel II; Salomaa, Kai; Yu, Sheng (2001), "Complejidad de estados de operaciones básicas en lenguajes finitos", Implementación de autómatas , Lecture Notes in Computer Science, vol.  2214, Springer-Verlag, pp. 60–70 , doi : 10.1007/3-540-45526-4_6 , ISBN  978-3-540-42812-1.
  • David, Julien (2012), "Complejidad promedio de los algoritmos de Moore y Hopcroft", Theoretical Computer Science , 417 : 50–65 , doi : 10.1016/j.tcs.2011.10.011.
  • Hopcroft, John (1971), "Un algoritmo n log n para minimizar estados en un autómata finito", Teoría de máquinas y computación (Actas del Simposio Internacional, Technion, Haifa, 1971) , Nueva York: Academic Press, págs. 189–196 , MR 0403320  Véase también la versión preliminar, Informe Técnico STAN-CS-71-190 , Universidad de Stanford, Departamento de Ciencias de la Computación, enero de 1971.
  • Hopcroft, John E.; Ullman, Jeffrey D. (1979), Introducción a la teoría de autómatas, lenguajes y computación , Reading/MA: Addison-Wesley, ISBN 978-0-201-02988-8
  • Hopcroft, John E .; Motwani, Rajeev ; Ullman, Jeffrey D. (2001), Introducción a la teoría de autómatas, lenguajes y computación (2.ª  ed.), Addison-Wesley.
  • Kameda, Tsunehiko; Weiner, Peter (1970), "Sobre la minimización del estado de autómatas finitos no deterministas", IEEE Transactions on Computers , 100 (7): 617– 627, doi : 10.1109/TC.1970.222994 , S2CID 31188224 .
  • Knuutila, Timo (2001), "Re-describing an algorithm by Hopcroft", Theoretical Computer Science , 250 ( 1–2 ): 333–363 , doi : 10.1016/S0304-3975(99)00150-4 , MR 1795249 .
  • Leiss, Ernst (1981), "Representación sucinta de lenguajes regulares mediante autómatas booleanos", Theoretical Computer Science , 13 (3): 323–330 , doi : 10.1016/S0304-3975(81)80005-9 , MR 0603263 .
  • Leiss, Ernst (1985), "Representación sucinta de lenguajes regulares mediante autómatas booleanos II", Theoretical Computer Science , 38 : 133–136 , doi : 10.1016/0304-3975(85)90215-4
  • Moore, Edward F. (1956), "Experimentos mentales sobre máquinas secuenciales", Estudios de autómatas , Anales de estudios matemáticos, n.º 34, Princeton, NJ: Princeton University Press, págs. 129–153 , MR 0078059  .
  • Sakarovitch, Jacques (2009), Elementos de la teoría de autómatas , Traducido del francés por Reuben Thomas, Cambridge University Press , ISBN 978-0-521-84425-3, Zbl 1188.68177 
  • Minimización de DFA utilizando el teorema de Myhill-Nerode