PUERTA | PUERTA-CS-2006 | Pregunta 34

Considere el lenguaje regular L = (111 + 11111)*. El número mínimo de estados en cualquier DFA que acepte este lenguaje es:
(A) 3
(B) 5
(C) 8
(D) 9

Respuesta: (D)
Explicación: El autómata de estado finito es:

Explicación:

Se da que lenguaje L = (111 + 11111)*
Las strings que pertenecen al lenguaje son
L = {null, 111, 11111, 111111, 11111111, 111111111, 1111111111, ……. formar string de longitud 8, (número de 1), ahora podemos generar cualquier longitud de string de longitud 3 y 5 (es decir, longitud 8, longitud 9, longitud 10, longitud 11, etc.)}
L = {null, 111, 11111, 111111 , 11111111 , 111111111* }
Strings de longitud , que pertenecen al lenguaje
L = {0 ,3, 5, 6, 8, 9, 10, 11, …}
Entonces, hay 5 estados que son estados finales y 4 estados que son estados no finales
Por lo tanto, el número total de estados son 9 estados.
por lo tanto, la opción D es verdadera.
Esta explicación ha sido aportada por Namita Singh.

Cuestionario de esta pregunta