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?

Quire

Just to clarify: The epsilon closure of an Epsilon-NFA N is just an NFA without epsilon transitions? – Sparky

@Sparky an epsilon closure is not applied to an NFA. It is applied to a state that has 1 or more epsilon transitions to other state(s), and returns a single state. It is used to get rid of epsilon transitions when converting to a DFA, because a DFA can't have epsilon transitions. – Quire

@Darkhydro, you can't just collapse all the epsilon-reachable states together. Consider s1--a-->s2, s1--b-->s3, s2--eps->s3, s2--c-->s4, starting state s1, accepting state s4. If you collapse s2 and s3 into a single state then you accept the string bc, which isn't accepted by the original NDFA. – Unending

@Peter I see your point. I'm looking into this. – Quire

@Peter actually it will not accept b. State 1 will still transition to 3 on input b, not 23. Creating state 23 does not erase state 3. – Quire

A state in an NFA N=(Q,Sigma,delta,q_0,F) is just an element of the set Q. The state without delta is meaningless. – Sparky

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.

Nahshun

this turned out to be the best solution. Very explicit because i can look at the source code. Thanks! – Quire

Answer 2

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.

Unending

@Peter searches aren't exactly what i am going for. This is more of a conditional traversal. My pattern is very similar to depth-first search, however. – Quire

@Darkhydro, as I understand the problem you're searching for all states epsilon-reachable from a given state. – Unending

@Peter that is a reasonable way of looking at things. However, if a search only returns one state, I would have to search multiple times to get all the states, which would be slower than my implementation because each search starts at the beginning again. – Quire

@Darkhydro, I get the impression that you would find it useful to get your hands on an introduction to datastructures and algorithms and read up on depth first search. The one I keep on my bookshelf is Introduction to Algorithms by Cormen, Leiserson, and Rivest. – Unending

@Peter Maybe i'm looking at this the wrong way. I have my own algorithm literature, and will brush up on depth-first search. The way i understood it searches returned only 1 result. – Quire

As normally understood it labels all reachable vertices. – Unending

@Quire what he means (at least how I understand it, and this is the solution I use) is that you approach the problem like you would a breadth-first search (only using epsilon transitions) and just store all the nodes you traverse to do so. In this case, it would be more of a breath-first traversal rather than a search but the actual algorithm is essentially identical. – Machicolation

DFS or BFS is of course optimal for computing the epsilon closure of a single state, but the conversion from NFA to DFA will require computing the epsilon closures of every state. When a node P has an epsilon transition to a node Q, if Q's epsilon closure has already been computed then it can be more efficient to reuse that result. I don't think this can improve the asymptotic complexity of the algorithm, because a DFS/BFS is linear time in the size of the epsilon closure, and unioning the already-computed closure of Q is also linear time; but the latter might be a bit faster, anyway. – Amoroso

Answer 3

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.

Attire

I agree, the performance will be based on the data structure I use. If you could suggest an optimal data structure plus a traversal algorithm, that would take the cake for best answer. My current data structure is merely a list/tree. – Quire

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.

Cataract