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
-
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.
-
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:
-
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:
-
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
-
Saltar. Sin parens.
-
Saltar. No hay estrellas de Kleene.
-
Saltar. No contatenation.
-
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 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í:
Edificio Q
-
Saltar. Sin parens.
-
Saltar. No hay estrellas de Kleene.
-
Saltar. No contatenation.
-
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:
¡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.