Un autómata finito determinista de estado mínimo que acepta el lenguaje L={w | w ε {0,1} *, el número de 0 y 1 en w son divisibles por 3 y 5, respectivamente} tiene
(A) 15 estados
(B) 11 estados
(C) 10 estados
(D) 9 estados
Respuesta: (A )
Explicación:
Aquí, una string w de 0 y 1 debe tener la propiedad de que el número de 0 en la string w debe ser divisible por 3 (N(0) % 3 = 0), y el número de 1 de la string w debe ser divisible por 5 (N(1) % 5 =0).
Habiendo dicho eso, el lenguaje contendrá strings como: { ε , 000, 11111, 00011111, 00111101 , 11111000, 10101011 , 00000011111,….y así sucesivamente }
Entonces, las strings aceptadas por el autómata deben tener una longitud de 0, 3, 5, 8, 11, 13, 14, 16… y así sucesivamente, es decir, la ecuación para la longitud será 3x + 5y (donde x,y>=0 )
El Módulo 3 da el resto como (0, 1, 2), y el Módulo 5 da el resto como (0, 1, 2, 3, 4). Por lo tanto, 3 * 5 estados, es decir, habrá 15 estados en el autómata para representar esto.
Comente a continuación si encuentra algo incorrecto en la publicación anterior.
Cuestionario de esta pregunta
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