Código Fuente

Hola, esta vez no voy a colgar el código fuente. Con el único fin de ver cuanta gente lo consulta, lo enviaré a aquellos que me dejen algún comentario. Por hacer el blog un poco más ameno.

Ya funciona el algoritmo AFD Mínimo

Con paciencia he localizado los errores en el código. Se quedaba bloqueado en un ciclo al calcular los estados distinguibles.

Esta ha sido la evolución con las ER corregidas:

AFNDLT tiempo de carga: 0' 18'' estados: 33455 tiempo de consulta: 10''

AFD primera versión, tiempo de carga: más de 4 horas.

AFD segunda versión, tiempo de carga: más de 1 hora, estados: 17540 compresión: 44,79% tiempo de consulta: inmediato.

AFD tercera versión, tiempo de carga: 40' 21'' estados: 9679 compresión: 71,07% tiempo de consulta: inmediato.

AFD Mínimo, tiempo de carga: 2' 15'' estados: 3407 compresión: 89,82% tiempo de consulta: inmediato.

Me encantan los resultados. De las mejoras que anuncié, he aplicado la primera. Sin embargo la segunda está orientada a la estructura general. Recordar que la estructura general es un AFNDLT que enlaza AFD Mínimos. Cuando se comprima el AFNDLT aplicaré la segunda mejora.
Ahora puedo seguir insertando nuevas ER.

Casi tengo programado al completo el AFD mínimo...

Esta mañana he dejado casi al completo el algoritmo que pasa de un AFD a AFD mínimo. La fase de prueba no la ha superado. Funciona perfectamente para las ER de dígito, natural, entero positivo, entero negativo y entero, cuando agrego la ER de real positivo... ya algo falla. Alguna tontería. Nada, sentarse y buscar el fallo.

He querido hacer una comparativa entre lo que ya funciona. Para las expresiones antes citadas el ANDL genera 398 estados, el AFD 190 siendo una compresión del 52.26% y el AFD mínimo genera 43 estados siendo una compresión del 89,19%. Son unos resultados muy prometedores, pero hasta que no esté completamente probado no puedo hacer la comparativa general con todas las ER insertadas y comprobar los tiempos de procesado y estados generados.

Para cuando esté resuelto, se me han ocurrido ciertas mejoras que podrían agiliar el procesado:

• No realizar el AFD mínimo de aquella AFD cuya expresión ER tenga menos de 3 caracteres, ya será mínimo.
• Para acelerar el proceso de AFD a AFD mínimo he pensado el repartir el peso del AFNDL en otros tres. Uno que sólo contenga las ER que correspondan a números, es decir cuyo alfabeto sea 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, - y el punto. Otro con las letras del abecedario, minúsculas, mayúsculas y acentuadas y por último aquellas ER que sean un pupurrí de números, letras y otros símbolos. Como para calcular los AFD mínimos para cada estado se compueba todas las letras de su alfabeto, al separarlos en estos tres grupos se evitará estar comprobando los números en una ER que sean de sólo letras, ahorrando muchos pasos del proceso, memoría y tiempo. Esto debe de ser transparente al usuario.

Corregido el fallo

Primero observé que habían expresiones regulares mal formuladas, por ejemplo natural estaba expresado como (dígito)* eso significa 0 o infinito dígitos uno tras otro. No puede ser 0. La nueva ER queda (dígito)(dígito)* esto obliga a que por lo menos exista un dígito.

Tras las modificaciones de las ER el ANDLT final pasaba a tener 33516 estados.

Con la corrección en el algoritmo para pasar a AFD a pasado a tener 9679 estados y el cálculo lo ha terminado en 33 minutos, siendo el 71,12% menos.

Estoy muy contento. Ahora toca obtener el AFD Mínimo.

Detectado fallo al pasar a AFD

El programa funciona bien, reconoce las ER. El problema es que cuando genera la tabla de transiciones del AFD inserta muchas transiciones a -1 que es el estado error. Inserta el estado final en un paso recursivo tarde. El resultado es que por ejemplo un AFD de 3 estados se convierta en uno de 15 con más de 100 transiciones.

Es necesario corregir este fallo antes de implementar el AFDMinimo.