What is the fastest way to calculate epsilon closure?

Question

I am working on a program for converting non-deterministic finite state machines (NFAs) to deterministic finite state machines (DFAs). To do this, I need to calculate the epsilon closure of each state in the NFA that has an epsilon transition. I already figured out a way to do this, but I always assume that the first thing I think about it is usually the least effective way to do something.

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

Input lines for the transition function: format - startState, symbol = endState

EPS - epsilon transition

1, EPS = 2

Results in new condition {12}

Now, obviously, this is a very simple example. I would need to calculate any number of epsilon transitions from any number of states. To this end, my solution is a recursive function that calculates the closure of epsilon on a given state by looking at the state in which it has epsilon transition. If this state has (a) epsilon transition (s), then the function is called recursively in the for loop for as many epsilon transitions as it takes place. This will do the job, but it's probably not the fastest way. So my question is: what is the fastest way to calculate epsilon closure in Java?

Answer 1

JFLAP does this. You can see their source - in particular, ClosureTaker.java. This is a depth search (as suggested by Peter Taylor), and since JFLAP uses it, I assume it is an almost optimal solution.

Answer 2

The first depth search (or the first width search - it doesn't really matter) on a graph whose edges are your epilson transitions. In other words, your solution is optimal if you effectively track which states you have already added to the closure.

Answer 3

Have you looked into the book of algorithms? But I doubt that you will find a much better approach. But the actual performance of this algorithm can very much depend on the specific data structure that you use to implement your graph. And you can share the work, depending on which order you simplify. Think of the subgraphs that are associated with epsilon and refer to two different nodes. I'm not sure if this can be done in an optimal way, or you need to resort to some heuristics.

Scanning literature on algorithms.