Sea w cualquier string de longitud n {0,1}*. Sea L el conjunto de todas las substrings de w. ¿Cuál es el número mínimo de estados en un autómata finito no determinista que acepta L?
(A) n-1
(B) n
(C) n+1
(D) 2n-1
Respuesta: (C)
Explicación: Necesitamos un mínimo de n+1 estados para construir NFA que acepte todas las substrings de una string binaria. Por ejemplo, seguir NFA acepta todas las substrings de «010» y tiene 4 estados.
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