¿Cómo construyes la unión de dos DFA?

¿Alguien tiene una descripción directa del algoritmo para construir la unión de dos DFA dados? Por ejemplo, digamos que tenemos más de dos de DFA {0,1} donde¿Cómo construyes la unión de dos DFA?

{w|w has an odd number of characters} 
    w has states A and B 

delta | 0 | 1 
---------------- 
    A | B | B 
---------------- 
    B | A | A 


{x|x has an even number of 1s} 
    x has states a and b 

delta | 0 | 1 
---------------- 
    a | a | b 
---------------- 
    b | b | a

tengo una tabla de transición resultante muestra la unión como:

delta | 0 | 1 
---------------- 
    Aa | Ba | Bb 
---------------- 
    Ab | Bb | Ba 
---------------- 
    Ba | Aa | Ab 
---------------- 
    Bb | Ab | Aa

tengo una solución pictórica en mis notas de la conferencia, pero me gustaría ver cómo otros lo describirían. A partir de esto, puedo ver que esencialmente "multiplicamos" estas dos tablas originales usando sus valores de estado para dar como resultado una tabla de transición más grande. El DFA se puede extraer de la tabla resultante. ¿Suena bien y debería funcionar para todos los casos de DFA, o hay algo que me falta?

Fuente

2010-12-15 Old McStopher

La clave para comprender es que debe ejecutar los dos DFA simultáneamente o, en general, debe mantener los estados de ambos DFA en la unión DFA.

Es por eso que debe crear los nuevos estados para la unión DFA como una multiplicación directa de los estados originales. De esta forma, tiene un estado para cada combinación de estados en DFA originales.

Las reglas de transición para el nuevo DFA se pueden calcular directamente a continuación. Por ejemplo, si está en estado Ab y recibe un 0 en la entrada, el primer DFA pasará al estado B y el segundo al estado b, por lo que el próximo estado de la unión DFA para esta entrada será Bb.

Este método funciona en todos los casos cuando necesita realizar una unión de dos o más DFA. El DFA resultante puede no ser óptimo, pero luego puede minimizarlo con cualquier algoritmo que desee.

Fuente

2010-12-15 12:56:50 buc

¿Qué pasa si obtiene una transición que es imposible en uno de los autómatas? –

Agregaría el estado E (error) para el autómata que tiene una transición imposible. Ese autómata permanecería en esa estadística durante el resto de la secuencia de entrada. Digamos que es el primero. Entonces tendrías los estados Aa Ab, Ba, Bb, Ea, Eb en el nuevo autómata. – Nenad

Creo que sería similar si un autómata solo tiene {0,1} como símbolos de entrada, y el otro tiene {1,2} como símbolos de entrada. Tendríamos que extender los dos autómatas con los estados de Error (E para el primero y e para el segundo) donde 1st iría a E si 2 es la entrada, y 2nd pasaría a e state si 0 es la entrada. – Nenad

¿Cómo construyes la unión de dos DFA?

Respuesta

Cuestiones relacionadas