Saltar al contenido

Pasos para crear un NFA a partir de una expresión regular

Solución:

Versión corta para enfoque general.

Existe un algoritmo llamado algoritmo de construcción de Thompson-McNaughton-Yamada o, a veces, simplemente “construcción de Thompson”. Uno construye NFA intermedios, completando las piezas a lo largo del camino, respetando la precedencia de los operadores: primero paréntesis, luego Kleene Star (p. Ej., A *), luego concatenación (p. Ej., Ab), seguida de alternancia (p. Ej., A | b).

Aquí hay un tutorial detallado para la construcción de NFA de (b | a) * b (a | b)

Construyendo el nivel superior

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

  2. Kleene Stars: solo hay uno *, así que construimos una máquina Kleene Star de marcador de posición llamada P (que luego contendrá b | a). Resultado intermedio:
    Autómatas finitos no deterministas para P *

  3. Concatenación: adjunte P a by adjunte b a una máquina de marcador de posición llamada Q (que contendrá (a | b). Resultado intermedio:
    Autómatas finitos no deterministas para P * bQ

  4. No hay alternancia fuera de paréntesis, por lo que lo 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 el NFA para b | a, y reemplazamos el borde Q con el NFA para a | b mediante la aplicación recursiva de los pasos anteriores.


Edificio P

  1. Saltar. Sin parens.

  2. Saltar. No hay estrellas de Kleene.

  3. Saltar. No contatenation.

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


Integrando P

A continuación, volvemos a esa máquina P * bQ y arrancamos el borde P. Tenemos el fuente del borde P sirven como el estado inicial para la máquina P, y el destino del borde P sirven 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í:
ingrese la descripción de la imagen aquí


Edificio Q

  1. Saltar. Sin parens.

  2. Saltar. No hay estrellas de Kleene.

  3. Saltar. No contatenation.

  4. Construya la máquina de alternancia para a | b. Por cierto, la alternancia es conmutativa, por lo que a | b es lógicamente equivalente a b | a. (Leer: omitir este diagrama de nota al pie menor por pereza).


Integrando Q

Hacemos lo que hicimos con P arriba, excepto reemplazar el borde Q con la intermedia b | una máquina que construimos. Este es el resultado:
ingrese la descripción de la imagen aquí

¡Tada! Er, quiero decir, QED.


¿Quieres saber más?

Todas las imágenes anteriores se generaron utilizando una herramienta en línea para convertir automáticamente 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 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ó con algunos detalles en un artículo popular sobre la coincidencia de expresiones regulares.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *