In the theory of computation, epsilon-closure (ε-closure) is a fundamental operation for converting a Non-deterministic Finite Automaton (NFA) with ε-transitions into an equivalent Deterministic Finite Automaton (DFA). The ε-closure of a state s is the set of all states reachable from s by following zero or more ε-transitions alone, without consuming any input symbol. In this post, we implement ε-closure computation in Java using a recursive depth-first approach.
Epsilon Closure Implementation in Java
package eclo;
import java.io.*;
public class EpsilonClosure {
static final int TOTAL_STATES = 8; // Total number of NFA states (0 through 7)
static final int NULL_STATE = -1; // Sentinel value meaning "no transition"
/**
* Delta table for input symbols 'a' (column 0) and 'b' (column 1).
* deltaOnInput[state][0] = next state on 'a', deltaOnInput[state][1] = next state on 'b'
* -1 means no transition exists.
*/
static int[][] deltaOnInput = {
{NULL_STATE, NULL_STATE}, // State 0: no 'a' or 'b' transition
{NULL_STATE, NULL_STATE}, // State 1
{3, NULL_STATE}, // State 2: on 'a' goes to state 3
{NULL_STATE, NULL_STATE}, // State 3
{NULL_STATE, 5 }, // State 4: on 'b' goes to state 5
{NULL_STATE, NULL_STATE}, // State 5
{NULL_STATE, NULL_STATE}, // State 6
{NULL_STATE, NULL_STATE} // State 7
};
/**
* Delta table for epsilon transitions.
* deltaOnEpsilon[state][i] = i-th state reachable by epsilon from given state.
* -1 means no further epsilon-transition at that slot.
*/
static int[][] deltaOnEpsilon = new int[TOTAL_STATES][5];
/** Stores the computed epsilon-closure for each state */
static int[][] epsilonClosure = new int[TOTAL_STATES][50];
/** Index of the state currently being computed (the root state of this closure run) */
static int currentRootState = 0;
/** Current insertion position in the epsilonClosure array for the active root state */
static int closureInsertPos = 0;
/** Initialize all epsilon transitions to NULL_STATE (-1) */
static void initEpsilonTransitions() {
for (int state = 0; state < TOTAL_STATES; state++) {
for (int slot = 0; slot < 5; slot++) {
deltaOnEpsilon[state][slot] = NULL_STATE;
}
}
// Define epsilon-transitions in the NFA
deltaOnEpsilon[0][0] = 1; deltaOnEpsilon[0][1] = 7; // State 0 --eps--> 1, 7
deltaOnEpsilon[1][0] = 2; deltaOnEpsilon[1][1] = 4; // State 1 --eps--> 2, 4
deltaOnEpsilon[3][0] = 6; // State 3 --eps--> 6
deltaOnEpsilon[5][0] = 6; // State 5 --eps--> 6
deltaOnEpsilon[6][0] = 7; deltaOnEpsilon[6][1] = 1; // State 6 --eps--> 7, 1
}
/** Initialize the epsilonClosure result array to NULL_STATE (-1) */
static void initClosureTable() {
for (int state = 0; state < TOTAL_STATES; state++) {
for (int slot = 0; slot < 50; slot++) {
epsilonClosure[state][slot] = NULL_STATE;
}
}
}
/**
* Recursively computes epsilon-closure for the given state,
* adding reachable states into epsilonClosure[currentRootState][].
*/
static void computeClosure(int targetState) {
// Add targetState to the closure if not already present
if (!isAlreadyInClosure(targetState)) {
epsilonClosure[currentRootState][closureInsertPos] = targetState;
closureInsertPos++;
}
// Recursively follow each epsilon-transition from targetState
for (int slot = 0; slot < 5; slot++) {
int nextState = deltaOnEpsilon[targetState][slot];
if (nextState != NULL_STATE) {
if (!isAlreadyInClosure(nextState)) {
epsilonClosure[currentRootState][closureInsertPos] = nextState;
closureInsertPos++;
}
computeClosure(nextState); // recurse
}
}
}
/** Returns true if the given state is already recorded in the current closure */
static boolean isAlreadyInClosure(int state) {
for (int slot = 0; slot < 50; slot++) {
if (epsilonClosure[currentRootState][slot] == state) {
return true;
}
}
return false;
}
public static void main(String[] args) throws IOException {
initEpsilonTransitions();
initClosureTable();
// Compute epsilon-closure for every state
for (int state = 0; state < TOTAL_STATES; state++) {
currentRootState = state;
closureInsertPos = 0;
computeClosure(state);
}
// Display epsilon-closure for user-specified state
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter State Number (0-7):");
int queryState = Integer.parseInt(reader.readLine());
System.out.println("Epsilon-closure of state " + queryState + ":");
for (int slot = 0; slot < 50; slot++) {
if (epsilonClosure[queryState][slot] != NULL_STATE) {
System.out.print(epsilonClosure[queryState][slot] + " ");
}
}
System.out.println();
}
}
How the Code Works
deltaOnEpsilon[][]is the ε-transition table. Each row is a state; each column holds a state reachable via ε from that state (-1means no transition). The NFA here has ε-arcs: 0→1, 0→7, 1→2, 1→4, 3→6, 5→6, 6→7, 6→1.initEpsilonTransitions()fills the epsilon table with-1first, then sets the NFA’s specific ε-transitions.computeClosure(targetState)is a recursive DFS. It addstargetStateto the closure result, then follows every ε-transition and recurses into each reachable state.isAlreadyInClosure()prevents infinite loops and duplicates by checking whether a state already appears in the closure result before adding it again.- The main loop calls
computeClosurefor each state 0–7 and stores the complete ε-closure inepsilonClosure[][]. - The user then queries a specific state number and the program prints all states in its ε-closure.
Sample Output
Enter State Number (0-7):
3
Epsilon-closure of state 3:
3 6 7 1 2 4
Enter State Number (0-7):
6
Epsilon-closure of state 6:
6 7 1 2 4
Output Explanation
- For state 3: Starting at 3, we follow ε to 6 → from 6 we reach 7 and 1 → from 1 we reach 2 and 4. No further ε-transitions exist from 2, 4, or 7. So ε-closure(3) = {3, 6, 7, 1, 2, 4}.
- For state 6: Starting at 6, we follow ε to 7 and 1 → from 1 we reach 2 and 4. So ε-closure(6) = {6, 7, 1, 2, 4}.
- The recursive DFS naturally handles cycles (like 6→1→…→6) because
isAlreadyInClosure()guards against revisiting states.
See Also
- Finite State Machine: Implementing Binary Adder in Java
- Finite State Machine: Check Whether String Contains ‘abb’ or not
- Finite State Machine: Check Whether String Ends with ‘abb’ or not
- Push Down Automata: Equal Number of a’s and b’s in Java
- Turing Machine: Well-Formedness of Parenthesis in Java
Conclusion
The ε-closure algorithm is a cornerstone of NFA-to-DFA subset construction. By using a recursive DFS and a simple duplicate-check guard, we can cleanly compute the reachable set of states for any NFA state. Understanding this concept is essential for building lexers, regex engines, and any system based on automata theory.