¿Cómo escribirías el lenguaje para este AFD como L(M) = {...}?
Creo que en inglés diría que L(M) se define como { a , b }* que termina en b , ba o aa .
Respuestas
¿Demasiados anuncios?
Hay dos tipos de palabras no vacías que van desde $q_0$ a $q_0$ sin pasar por $q_0$ de nuevo en el camino. Una es la palabra $b$ y la otra es cualquier palabra de la forma $ab^*a$ . Se puede concatenar cualquier número de palabras de estos dos tipos en cualquier orden, por lo que el lenguaje es el dado por la expresión regular $(b\mid ab^*a)^*$ . En términos de conjuntos que es $\left(\{b\}\cup \{a\}\{b\}^*\{a\}\right)^*$ .
Si lo miras con atención, verás que puede coincidir con cualquier palabra que contenga un número par de $a$ ': coinciden con cualquier inicial $b$ 's a $b^*$ y, a continuación, hacer coincidir los dos primeros $a$ y cualquier $b$ entre ellos para $ab^*a$ y repite lo que sea necesario, haciendo coincidir los restos de $b$ 's a $b^*$ . A la inversa, cualquier palabra de la lengua debe contener claramente un número par de $a$ con el fin de conducir el DFA a $q_0$ . Así, la lengua puede expresarse de forma muy sencilla en inglés: es el conjunto de palabras sobre $\{a,b\}$ que contiene un número par de $a$ 's.
iturki
Puntos
106
Asumiré como Gerry Myerson que $q_0$ es el estado inicial y el único estado de aceptación. Creo que el conjunto de cadenas con número par de $a$ es el lenguaje aceptado de este AFD. El $b$ sólo lo mantendrá en el estado actual y el $a$ 'te trasladan al otro estado. Estás en el estado $q_0$ si y sólo si el número de $a$ es uniforme.
Beth
Puntos
9
