Quiero determinar el lenguaje que corresponde a los siguientes autómatas
Nota: $q_{6}$ tienen flecha para $a$ para sí mismo.
Empecé con las palabras mínimas:
lo único que deduje de aquí es que el número de $a$ necesitan ser $>2$
¿Alguna sugerencia?
Gracias.
La técnica básica consiste en eliminar repetidamente uno de los estados del autómata, adaptando en consecuencia las etiquetas de los estados circundantes. En este caso, no es difícil ver que las transiciones q0-q1-q2 se corresponden con la expresión regular b*ab*a . Del mismo modo q2-q4-q5 (lo que resulta en aa*b ) y q2-q5-q6 (lo que resulta en bb*a ). La dificultad radica en los estados q5 , q6 y q7 que están "entrelazados". Otro enfoque es el método algebraico de Brzozowski, que traduce las transiciones en una serie de ecuaciones que hay que reducir. Estas técnicas se analizan en este artículo de Christoph Neumann por ejemplo, pero son bastante complicados de realizar a mano.
El paquete JFLAP tiene incorporada la capacidad de convertir autómatas en expresiones regulares. Introduciendo su autómata, con el bucle extra en q6 resulta la siguiente expresión: b*((ab*abb*a+ab*aaa*ba)(ba)*+(ab*aaa*bb+(ab*abb*a+ab*aaa*ba)(ba)*bb)(b+a(ba)*bb)*(λ+a(ba)*)) .
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.
