Simulación de NFA

Tu parser ya reconoce el patrón. Ahora convierte su estructura en un autómata con transiciones por carácter y transiciones vacías (épsilon). En nfa-match, el patrón debe consumir el texto completo; search de etapas anteriores conserva su comportamiento.

Contrato observable

Entrada: {"op":"nfa-match","pattern":"(a|aa)*b","text":"aaaab"}. Salida: {"matched":true} seguida de salto de línea. En esta operación no se devuelven capturas ni un contador de pasos declarado por el programa. El punto excluye \n.

Mantén un conjunto de estados activos y calcula su clausura épsilon sin visitar dos veces un estado en la misma expansión. Después de cada carácter, calcula el conjunto siguiente y vuelve a expandir. Acepta solo si, al agotar el texto, el conjunto contiene el estado final.

Complejidad y comprobación

Las pruebas incluyen 4,096 letras a seguidas de b o c con (a|aa)*b, y el proceso debe terminar dentro de los 2,000 ms del contrato. El tiempo incluye el arranque: compila antes de ejecutar. Esta prueba detecta el retroceso exponencial ingenuo; no demuestra por sí sola una complejidad asintótica. Razona además que cada paso procesa a lo sumo los estados del autómata, para un costo O(longitud del texto × estados).

No delegues al motor regex de tu lenguaje. Usa conjuntos e identifica cada estado con un ID estable. Prueba también texto vacío, ciclos épsilon y un patrón que deja caracteres sin consumir. Ante JSON inválido, campos ausentes o patrón inválido, emite error en stderr, deja stdout vacío y termina con código 1; las entradas válidas terminan con código 0.

Los ejemplos multilínea se muestran así para facilitar la lectura. Emite JSON compacto, sin espacios opcionales, con las propiedades en el orden de los ejemplos de salida y un salto de línea final. No escribas logs en stdout. Las pruebas comparan texto exacto. Para entradas inválidas, usa stderr con la palabra error, stdout vacío y código 1. Para entradas válidas, código 0. Usa números JSON enteros cuando el resultado sea entero.