Los dos DFA que describe pueden representarse gráficamente de la siguiente manera
El DFA azul es la primera máquina que describió y el DFA rojo es la segunda.
Para tomar el producto de estas máquinas, literalmente puede cruzar los estados entre sí para obtener un nuevo estado para cada par de estados anteriores.
- ¿Cuál es el origen del nombre "Informática"?
- ¿Cuáles son los libros recomendados para los exámenes de acceso lateral en IIIT Hyderabad para ece?
- ¿Qué tan grande puede llegar a ser un átomo?
- Cómo recuperar archivos después de una recuperación del sistema de Windows
- ¿Quién es el Einstein de la informática?
El estado inicial es el estado que corresponde a los dos estados iniciales originales, en este caso, estado (1, 1).
Las transiciones en la construcción de este producto se realizan siguiendo dos bordes para cada personaje, uno rojo y otro azul. Puede verificar por sí mismo que no importa qué ventaja tome primero.
Los estados de aceptación en la intersección serán precisamente aquellos estados que corresponden a un estado de aceptación en ambas máquinas originales. En este caso, solo indique (3, 2).
Los estados de aceptación en la unión serán precisamente aquellos estados que corresponden a un estado de aceptación en al menos una de las máquinas originales. En este caso, los estados (3, 1), (1, 2), (2, 2) y (3, 2).
Normalmente, los DFA no se dibujan de una manera que requiera pasar por dos estados en cada transición. Puede contraer cada una de esas transiciones a la transición real para obtener el siguiente DFA.
La construcción del subconjunto (o construcción del conjunto de potencia) no es una imagen tan bonita; Es mucho más difícil dibujar un número exponencial de estados.
La diferencia básica entre la construcción del producto y la construcción del conjunto de potencia es que cada estado en la construcción del producto representa un par de estados en las máquinas originales, mientras que cada estado en la construcción del conjunto de potencia representa un subconjunto de los estados en la máquina original.
La construcción del conjunto de potencia generalmente se usa para modelar un NFA como un DFA, usando cada estado en el DFA para representar el conjunto de estados en los que podría estar en el NFA.
La construcción del producto generalmente se usa para modelar la ejecución de dos DFA en paralelo.