Considere un DFA sobre ∑ = {a, b} aceptando todas las strings que tienen un número de a divisible por 6 y un número de b divisible por 8. ¿Cuál es el número mínimo de estados que tendrá el DFA?
(A) 8
(B) 14
(C) 15
(D) 48
Respuesta: (D)
Explicación:
Construimos un DFA para strings divisibles por 6.
Requiere un mínimo de 6 estados como longitud de string mod 6 = 0, 1, 2 , 3, 4, 5
Construimos un DFA para strings divisibles por 8.
Requiere un mínimo de 8 estados como longitud de string mod 8 = 0, 1, 2, 3, 4, 5, 6, 7
Si el primer DFA es mínimo y el segundo DFA también es mínimo, luego de fusionar ambos DFA, el DFA resultante también será mínimo. Tal DFA se llama autómata compuesto.
Entonces, estados mínimos en el DFA resultante = 6 * 8 = 48
Por lo tanto, la opción (D) es la respuesta.
Comente a continuación si encuentra algo incorrecto en la publicación anterior.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA