Si entiendo correctamente, NFA tiene el mismo poder expresivo que las expresiones regulares. A menudo, leer expresiones regulares equivalentes de NFA es fácil: traduce ciclos a estrellas, uniones como alternativas, etc. Pero qué hacer en este caso:
[ fuente ]
Los ciclos superpuestos hacen que sea difícil ver qué acepta este autómata (en términos de expresiones regulares). ¿Hay algún truco?
Respuestas:
En lugar de "leer", debe emplear uno de varios métodos canonciales para hacer esto. Con mucho, el mejor que he visto es uno que expresa el autómata como sistema de ecuaciones de lenguajes (regulares) que se pueden resolver. Es particularmente agradable, ya que parece producir expresiones más concisas que otros métodos.
Escribí este documento explicando el método para estudiantes el verano pasado. Se relaciona directamente con una conferencia específica; La referencia mencionada es la definición típica de expresiones regulares. Contiene una prueba del Lema de Arden (un resultado necesario); falta uno para la corrección del método. Como supe en la conferencia, no tengo una referencia, lamentablemente.
En resumen: para cada estado , cree la ecuaciónqi
donde es el conjunto de estados finales y significa que hay una transición de a etiquetada con . Si lee como o (según su definición de expresión regular), verá que esta es una ecuación de expresiones regulares.F qi→aqj qi qj a ∪ + ∣
Resolverlo (usando el Lema de Arden ) produce una expresión regular para cada estado que describe exactamente aquellas palabras que pueden aceptarse comenzando en ; por lo tanto, (si es el estado inicial) es la expresión deseada.Qi qi Q0 q0
La aplicación al autómata dado se deja como ejercicio; Se incluye un ejemplo completo en el documento vinculado anterior .
Vea también aquí donde publiqué una respuesta similar.
fuente
Si solo hubiera una cadena de estados sin bucle, ¿sabrías qué hacer?
Si hubiera un bucle simple sin esta ramificación superpuesta, ¿sabría qué hacer?
(Si la respuesta es "no", piense primero en estos casos).
Ahora, la idea es transformar el autómata progresivamente para ponerlo en una forma en la que pueda detectar esos patrones: cadenas, bucles y caminos divergentes que se vuelven a unir al final (lo que lleva a la alternancia). En cada paso de la transformación, tenga cuidado de que el autómata transformado todavía reconozca el mismo idioma.
Tenga en cuenta que este es un autómata no determinista. El que publicaste resulta ser determinista, pero no tiene que permanecer así cuando lo transformas.
Como el punto es que se puede alcanzar desde dos puntos diferentes, divídalo en dos. Mantenga , elimine la transición de a y agregue en su lugar un nuevo estado con transiciones . Ahora deberías poder detectar un patrón.q 1 f → q 2 g → q 3 q 4 q 2 q 5 q 4 j → q 5 g → q 3q2 q1→fq2→gq3 q4 q2 q5 q4→jq5→gq3
Tenga cuidado de verificar qué estados son finales. Puede ser útil no preocuparse por esto al principio y hacer un gran bucle, luego duplicar las partes que terminan en la mitad del bucle.
Esta no es necesariamente la técnica más eficiente o la que genera la expresión regular más simple, pero es simple.
fuente
fuente
[(])
sino[()]
.