Estoy tratando de entender la respuesta aquí para FA que acepta sólo las palabras baa, ab, abb y no other strings longer or shorter . Entiendo de dónde sacaron baa y ab pero cómo consiguieron que tuviera abb ?
Si alguien tiene otra forma de hacer esto se lo agradecería... Esto me confunde con tener un estado q7 aquí.
Entiendo de dónde han sacado baa y ab, pero ¿cómo han conseguido que tenga abb?
Sólo hay que seguir las flechas. "a" te lleva a q1, luego "b" te lleva a q2, y otra "b" te lleva a q3, que es un estado de aceptación.
esto me confunde con tener un estado q7 aquí.
El q7 representa un estado de fallo. Una vez que el autómata entra en él, no puede salir, por lo que nunca aceptará esa cadena de entrada.
Claro que puedes salir de la q2. Hay una flecha que sale de ella. (No pienses en q2 como un estado final --- el programa NO termina una vez que entra en q2. Es simplemente que cuando el programa está en q2, puede aceptar la cadena de entrada hasta el momento. Piensa en q2 como un "estado de aceptación").
@Ris La máquina no se detiene una vez que llega a $q2$ aunque $q2$ a veces se llama estado "final". (Es un mal término, pero así lo llaman algunos). La máquina continúa hasta que lee el final de la cadena de entrada. Entonces, si el estado actual es $q2, q3, $ o $q6$ La máquina acepta la entrada.
Ampliando el punto de Newb, puedes pensar en Q7 como una 'trampa' - el autómata nunca puede escapar, ya que tanto A como B conducen de vuelta a Q7. Es necesario para que todas las cadenas sean entradas válidas para el AF, actuando como un "cajón de sastre" para las cadenas de más de cuatro caracteres; sin embargo, como hemos señalado antes, sólo ab , abb y baa se aceptará.
Como quieres dibujar un NFA, el estado de la trampa no es necesario. Pero, si usted quiere dibujar un DFA, como usted sabe, todos los estados deben tener exactamente un vértice que sale de cada estado. por lo tanto, nos vemos obligados a dibujar un nuevo estado (llamado TRAP), y la transferencia de todos los vértices no utilizados a ese estado. en tu pregunta, por ejemplo, el estado q3 no tiene vértices de salida por 'a' , 'b' y no es un DFA. para hacer que esta máquina sea DFA, deberíamos añadir vértices con la etiqueta 'a' , 'b' a este estado. pero, no necesitamos que estas transiciones acepten cadenas. así que las guiamos a trap. buena suerte
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
2 votos
El $q7$ se denomina estado "muerto": una vez que la máquina entra en el estado q7, queda atrapada allí, porque no hay transición para salir de q7. Ningún cálculo que entre en q7 puede ser un cálculo de aceptación. Así nos aseguramos de que la máquina no aceptará ninguna cadena que no sea
ab,abbybaa.0 votos
Cuando dice que no hay otras cadenas, eso no tiene sentido porque puedo ir de q0,q1 a q7 y eso me dará aa y debería ser cualquier otra cadena
6 votos
La máquina no acepta
aaporque cuando haya terminado de leeraaestá en el estado $q7$ que no es un estado de aceptación.0 votos
Eso tiene sentido