Sea L⊆{0,1}∗ un lenguaje regular arbitrario aceptado por un DFA mínimo con k estados. ¿Cuál de los siguientes idiomas debe ser necesariamente aceptado por un DFA mínimo con k estados?
(A) L−{01}
(B) L∪{01}
(C) {0,1}*–L
(D) L⋅L
Respuesta: (C)
Explicación: La opción (C) es la opción correcta.
{0,1}*−L = complemento del lenguaje L.
Dado que tenemos un DFA mínimo con k estados para el idioma dado L.
Podemos cambiar los estados final y no final para obtener el DFA que acepta el complemento de L sin cambiar el número de estados.
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