Sea N un NFA con n estados. Sea k el número de estados de un DFA mínimo que es equivalente a N. ¿Cuál de los siguientes es necesariamente cierto?
(A) k ≥ 2 n
(B) k ≥ n
(C) k ≤ n 2
(D) k ≤ 2 n
Respuesta: (D)
Explicación: el número mínimo de estados en DFA será 1 cuando solo tengamos un estado inicial y todos los demás estados no serán accesibles desde el estado indicado.
El número máximo de estados en DFA será 2 n como el número de subconjuntos de un conjunto con n elementos en el peor de los casos.
Por lo tanto, k ≤ 2 n
La opción (D) es correcta.
Pregunta relacionada – PUERTA | Puerta TI 2008 | Pregunta 6
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