¿Cómo convertir un NFA con ciclos superpuestos en una expresión regular?

11

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:

ingrese la descripción de la imagen aquí
[ 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?

zell
fuente
2
Sería bueno si pudiera indicar en el diagrama cuáles son los estados inicial y final: una pequeña flecha hacia el estado inicial y un círculo doble como estado final. Además, es difícil saber a dónde va mal si no da ninguna indicación de lo que ha intentado.
Dave Clarke el
Quizás este documento pueda ayudarlo: explica claramente cómo convertir un NFA a un RE.
Vor
1
¿Por qué es dificil? ¿Has probado uno de los algoritmos canónicos? ¿Cuál es el mejor ansatz que puedes hacer?
Raphael
3
Edité para hacer la pregunta (en mi humilde opinión) interesante y buena para este sitio. Vea el historial de revisiones para formar una opinión.
Raphael
1
Tengo una respuesta lista que transforma su NFA en una expresión regular, pero la eliminé: la respuesta de Raphael le brinda el método que necesita para hacerlo usted mismo (también le da un enlace a un ejemplo), para que pueda practicar un poco si querer. Si todavía quieres mi solución, recuperaré mi respuesta.
Alex ten Brink

Respuestas:

5

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

Qi=qiaqjaQj{{ε}, qiF, else

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.Fqiaqjqiqja+

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.QiqiQ0q0

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.

Rafael
fuente
1
Vea esta pregunta de referencia para otros métodos generales.
Raphael
3

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 3q2q1fq2gq3q4q2q5q4jq5gq3

Si todavía tiene problemas en este punto, observe que el ciclo que involucra corresponde a una expresión regular simple. Cuando llegue a , puede realizar tantas corridas alrededor de este ciclo como desee. En cierto sentido (que puede hacerse técnico), puede reemplazar el estado por la expresión regular .q 3 q 3 ( h j g ) q3,q4,q5q3q3(hjg)

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.

Gilles 'SO- deja de ser malvado'
fuente
3

Split q_1

Jukka Suomela
fuente
Y esto responde a la pregunta ¿cómo?
Raphael
1
Si reescribe la máquina de estado de esta manera, ahora es trivial leer la expresión regular equivalente.
Jukka Suomela
1
Tal vez deberías incluir esto en el texto de respuesta. ¿Esto siempre funciona?
Raphael
@Raphael: Funciona en este caso. :) La idea general detrás de este truco es la siguiente: hicimos los ciclos "correctamente anidados". Es decir, no tenemos la estructura del ciclo [(])sino [()].
Jukka Suomela