Saltar al contenido

¿Cuál es la forma más fácil de determinar el lenguaje aceptado de un autómata finito determinista (DFA)?

Si encuentras algún error en tu código o proyecto, recuerda probar siempre en un ambiente de testing antes aplicar el código al trabajo final.

Solución:

Este es un DFA muy pequeño, por lo que usaría un bastante ad hoc Acercarse. Nótese primero que su lenguaje es precisamente el conjunto de palabras que llegan a $q_2$: una vez que llega a $q_2$, se queda ahí, y no hay otro estado aceptor. Por lo tanto, solo necesitamos ver qué palabras llegan a $q_2$.

Claramente necesitamos un $1$ en algún momento. Puede aparecer de inmediato, gracias a la transición $q_0overset1longrightarrow q_2$, o puede aparecer después de unos $0$s. ¿Cuántos $0$s? Un $0$ nos lleva a $q_1$, momento en el cual un $1$ nos lleva a $q_2$. Dos $0$ nos llevan de regreso a $q_0$, momento en el cual un $1$ nos lleva a $q_2$. De hecho, parece que cualquier número de $0$ (incluido ninguno) seguido de $1$ nos llevará a $q_2$. Por lo tanto, cualquier cosa que se ajuste a la expresión regular $0^*1$ nos lleva a $q_2$. Después de eso, podemos tener cualquier cosa, por lo que el idioma de DFA debe ser $0^*1(0+1)^*$.

Podemos empezar a analizar desde el estado final $q_2$: $$ u(0|1)^* $$ donde $u$ es un prefix palabra. Llegada solo aceptando un $1$ proveniente de $q_1$ o $q_0$: $$ v1(0|1)^* $$ donde $v$ es otro prefix palabra. Unirse al estado inicial $q_0$ a través del borde superior (a través de $q_1$) o inferior (directo): $$ (00)^*(0|epsilon)1(0|1)^* $$ que se simplifica a $ $ 0^*1(0|1)^* $$

Si guardas alguna vacilación y forma de aclarar nuestro artículo puedes añadir una anotación y con gusto lo observaremos.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *