PUERTA | PUERTA 2017 MOCK II | Pregunta 39

Considere un DFA que acepta todas las strings sobre {a, b} donde el número de a mod 3 = 2 y el número de b son impares.
¿Cuál es el número mínimo de estados de tal DFA?
(A) 4
(B) 2
(C) 6
(D) 8

Respuesta: (C)
Explicación:
La pregunta anterior es un ejemplo de autómatas producto. Si tenemos dos casos para los que podemos tener DFA separados, podemos fusionar los dos por autómatas de producto. El DFA resultante tiene un número de estados igual al producto de los estados de los DFA separados.
Aquí DFA para aceptar todas las strings sobre {a, b} donde el número de mod de a 3 = 2 tendría 3 estados. (el número de mod 3 de a daría un resto 0, 1, 2, por lo que 3 estados representan cada uno).

De manera similar, DFA acepta todas las strings sobre {a, b} donde el número de b es impar (número de b mod 2 = 0) tendría 2 estados.
Por lo tanto, el DFA resultante para ambas condiciones tendría 2*3 = 6 estados.

Cuestionario de esta pregunta