Sea N un NFA con n estados y sea M el DFA minimizado con m estados que reconocen el mismo idioma. ¿Cuál de los siguientes es NECESARIAMENTE cierto?
(A) m ≤ 2 n
(B) n ≤ m
(C) M tiene un estado aceptado
(D) m = 2 n
Respuesta: (A)
Explicación: un estado en un DFA es un subconjunto propio de estados de NFA del DFA correspondiente
=> conjunto de estados de NFA =n
=> número de subconjuntos de un conjunto con n elementos = 2 n
=> m<=2 n
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