Estoy trabajando en un programa para convertir autómatas de estados finitos no deterministas (NFA) a autómatas de estados finitos determinísticos (DFA). Para hacer esto, tengo que calcular el cierre épsilon de cada estado en el NFA que tiene una transición épsilon. Ya he descubierto una manera de hacerlo, pero siempre asumo que lo primero que pienso es la forma menos eficiente de hacer algo.¿Cuál es la forma más rápida de calcular un cierre épsilon?
Aquí es un ejemplo de cómo iba a calcular un cierre simple épsilon: cadenas
de entrada para la función de transición: formato se startState, símbolo = estado final
EPS es una transición épsilon
1, EPS = 2
resultados en el nuevo estado {12}
Ahora, obviamente esto es un ejemplo muy sencillo. Necesitaría poder calcular cualquier número de transiciones épsilon desde cualquier número de estados. Con este fin, mi solución es una función recursiva que calcula el cierre épsilon en el estado dado al observar el estado en el que tiene una transición épsilon. Si ese estado tiene (an) transición épsilon, entonces la función se llama recursivamente dentro de un bucle for para tantas transiciones épsilon como tenga. Esto hará el trabajo, pero probablemente no sea la manera más rápida. Así que mi pregunta es esta: ¿cuál es la forma más rápida de calcular un cierre épsilon en Java?
Solo para aclarar: ¿El cierre épsilon de un Epsilon-NFA N es solo un NFA sin transiciones épsilon? – tkr
@tkr un cierre épsilon no se aplica a un NFA. Se aplica a un estado que tiene 1 o más transiciones epsilon a otro (s) estado (s) y devuelve un único estado. Se utiliza para deshacerse de las transiciones épsilon cuando se convierte a un DFA, porque un DFA no puede tener transiciones épsilon. – Darkhydro
@Darkhydro, no se puede simplemente colapsar todos los estados épsilon-alcanzables juntos. Considere s1 - a -> s2, s1 - b -> s3, s2 - eps-> s3, s2 - c -> s4, comenzando el estado s1, aceptando el estado s4. Si contrae s2 y s3 en un solo estado, entonces acepta la cadena bc, que no es aceptada por el NDFA original. –