What is the fastest way to compute an epsilon closure?

Question

I am working on a program to convert Non-deterministic finite state automata (NFAs) to Deterministic finite state automata (DFAs). To do this, I have to compute the epsilon closure of every state in the NFA that has an epsilon transition. I have already figured out a way to do this, but I always assume that the first thing I think of is usually the least efficient way to do something.

Here is an example of how I would compute a simple epsilon closure:

Input strings for transition function: format is startState, symbol = endState

EPS is an epsilon transition

1, EPS = 2

Results in the new state { 12 }

Now obviously this is a very simple example. I would need to be able to compute any number of epsilon transitions from any number of states. To this end, my solution is a recursive function that computes the epsilon closure on the given state by looking at the state it has an epsilon transition into. If that state has (an) epsilon transition(s) then the function is called recursively within a for loop for as many epsilon transitions as it has. This will get the job done but probably isn't the fastest way. So my question is this: what is the fastest way to compute an epsilon closure in Java?

Answer 1

JFLAP does this. You can see their source - specifically ClosureTaker.java. It's a depth-first search (which is what Peter Taylor suggested), and since JFLAP uses it I assume that's the near-optimal solution.

Answer 2

Did you look into an algorithm book? But I doubt you'll find a significantly better approach. But the actual performance of this algorithm may very well depend on the concrete data structure you use to implement your graph. And you can share work, depending on the order you simplify your graph. Think about subgraphs which are epsilon connected and are referenced from two different nodes. I am not sure whether this can be done in an optimal way, or whether you have to resort to some heuristics.

Scan the the literature on algorithms.

Answer 3

Depth first search (or breadth first search - doesn't really matter) over the graph whose edges are your epilson transitions. So in other words, your solution is optimal provided you efficiently track which states you've already added to the closure.

Answer 4

Just so that people looking only for the specific snippet of code referenced by @Xodarap 's answer don't find themselves in the need of downloading both the source code and an application to view the code of the jar file, I took the liberty to attach said snippet.

public static State[] getClosure(State state, Automaton automaton) {
    List<State> list = new ArrayList<>();
    list.add(state);
    for (int i = 0; i < list.size(); i++) {
        state = (State) list.get(i);
        Transition transitions[] = automaton.getTransitionsFromState(state);
        for (int k = 0; k < transitions.length; k++) {
            Transition transition = transitions[k];
            LambdaTransitionChecker checker = LambdaCheckerFactory
                    .getLambdaChecker(automaton);
            /** if lambda transition */
            if (checker.isLambdaTransition(transition)) {
                State toState = transition.getToState();
                if (!list.contains(toState)) {
                    list.add(toState);
                }
            }
        }
    }
    return (State[]) list.toArray(new State[0]);
}

It goes without saying that all credit goes to @Xodarap and the JFLAP project.