theory - non - Pasos para crear una NFA a partir de una expresión regular

non deterministic finite automata to dfa

Question

Tengo problemas para ''describir cada paso'' al crear una NFA a partir de una expresión regular. La pregunta es la siguiente:

Convierta la siguiente expresión regular en un autómata de estado fi nito no determinista (NFA), describiendo claramente los pasos del algoritmo que usa: (b | a) * b (a | b)

He hecho una máquina simple de 3 estados pero es muy por intuición. Esta es una pregunta de un examen anterior escrito por mi profesor, quien también escribió la siguiente explicación del algoritmo de Thompson: http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html

¿Alguien puede aclarar cómo "describir cada paso con claridad"? Simplemente parece un conjunto de reglas básicas en lugar de un algoritmo con pasos a seguir.

Tal vez haya un algoritmo que he pasado por alto en alguna parte, pero hasta ahora los he creado con una conjetura educada.

Answer 1

En el repositorio de GitHub a continuación, puede encontrar una implementación Java de la construcción de Thompson donde primero se crea una NFA a partir de la expresión regular y luego se compara una cadena de entrada con esa NFA:

https://github.com/meghdadFar/regex

Answer 2

Versión corta para aproximación general.
Hay un algoritmo por ahí llamado el algoritmo de construcción Thompson-McNaughton-Yamada o, a veces, simplemente "Construcción Thompson". Uno construye NFA intermedios, rellenando las piezas a lo largo del camino, respetando la precedencia del operador: primero paréntesis, luego Kleene Star (por ejemplo, a *), luego concatenación (por ejemplo, ab), seguido de alternancia (por ejemplo, a | b).

Aquí hay un tutorial en profundidad para la construcción (b | a) * b (a | b) ''s NFA

Construyendo el nivel superior

1. Manejar paréntesis. Nota: En la implementación real, puede tener sentido manejar paréntesis a través de una llamada recursiva en su contenido. Para mayor claridad, diferiré la evaluación de cualquier cosa dentro de los parens.

2. Kleene Stars: solo hay un * allí, por lo que construimos una máquina de Kleene Star llamada P (que luego contendrá b | a). Resultado intermedio:
   

3. Concatenación: Adjunte P a b, y adjunte b a una máquina de marcador de posición llamada Q (que contendrá (a | b). Resultado intermedio:
   

4. No hay alternancia fuera de paréntesis, así que la omitimos.

Ahora estamos sentados en una máquina P * bQ. (Tenga en cuenta que nuestros marcadores de posición P y Q son solo máquinas de concatenación). Reemplazamos el borde P con la NFA para b | a, y reemplazamos el borde Q con la NFA para a | b mediante la aplicación recursiva de los pasos anteriores.

Edificio p

1. Omitir. No hay parens.

2. Omitir. No hay estrellas Kleene.

3. Omitir. No hay contatenación.

4. Construye la máquina de alternancia para b | a. Resultado intermedio:
   

Integrando p

A continuación, volvemos a esa máquina P * bQ y arrancamos el borde P. Tenemos la fuente del borde P como estado de inicio para la máquina P, y el destino del borde P sirve como estado de destino para la máquina P. También hacemos que ese estado rechace (quita su propiedad de ser un estado de aceptación). El resultado se ve así:

Edificio q

1. Omitir. No hay parens.

2. Omitir. No hay estrellas Kleene.

3. Omitir. No hay contatenación.

4. Construye la máquina de alternancia para a | b. Incidentalmente, la alternancia es conmutativa, por lo que a | b es lógicamente equivalente a b | a. (Leer: omitir este pequeño diagrama de notas de pie fuera de la pereza.)

Integrando q

Hacemos lo que hicimos con P arriba, excepto que reemplazamos el borde Q con la máquina intermedia que construimos. Este es el resultado:

Tada! Er, quiero decir, QED.

¿Quiere saber más?

Todas las imágenes anteriores se generaron utilizando una herramienta en línea para convertir automáticamente las expresiones regulares en autómatas finitos no deterministas . Puede encontrar su código fuente para el algoritmo de construcción Thompson-McNaughton-Yamada en línea.

El algoritmo también se aborda en los compiladores de Aho: Principios, técnicas y herramientas , aunque su explicación es escasa en los detalles de implementación. También puede aprender de una implementación de Thompson Construction en C por el excelente Russ Cox, quien lo describió en detalle en un artículo popular sobre la comparación de expresiones regulares .