¿Cómo puedo demostrar que $ALL_{DFA}$ está en P ?
$ALL_{DFA} = \{ \langle A \rangle \mid A \text{ is a DFA and } L(A) = \Sigma^* \}$
Respuestas
¿Demasiados anuncios?
Obsérvese que un DFA acepta $\Sigma^*$ si y sólo si todos los estados alcanzables desde el estado inicial, $q_0$ están aceptando. Esto puede decidirse fácilmente en tiempo polinómico realizando una búsqueda de amplitud o profundidad en el DFA de $q_0$ . Si en algún momento se visita un estado no aceptable, rechazar , en caso contrario, si sólo se encuentran estados de aceptación, aceptar .
Curiosamente, este problema es mucho más difícil para las NFA; $\{ \langle A \rangle \mid A \text{ is an NFA and } L(A) = \Sigma^* \}$ es NP-difícil.
jani
Puntos
1
Mi respuesta a este problema en una tarea reciente fue originalmente similar a la otra respuesta en esta pregunta: Realizar una búsqueda de amplitud en la entrada, Si se visita un estado de no aceptación, rechazar, de lo contrario aceptar. Sin embargo, esta solución es equivocado . Este decididor aceptará un AFD que no acepte todas las entradas si, por ejemplo, no hay transición para uno de los caracteres de Σ. El siguiente DFA (con un alfabeto de 0 y 1) es un ejemplo de esto. No aceptará entradas con un 1, pero no hay ningún estado de rechazo que haga que este DFA sea rechazado por el decidor.
La respuesta es, en realidad, construir el complemento a la entrada y comprobar si el lenguaje del complemento es un conjunto vacío. Puede hacer esto haciendo una búsqueda de amplitud o profundidad en el complemento y si se encuentra un estado de aceptación, rechazar la entrada y en caso contrario, aceptar.
