epsilonclosure

Epsilon-closure is a concept in automata theory describing the set of states reachable from a given set of states via epsilon-transitions, which are transitions that do not consume an input symbol. Formally, the epsilon-closure of a set S of states is the smallest set that contains S and is closed under epsilon-transitions; that is, if a state p is in the closure and there is an epsilon-transition p -> q, then q is also in the closure. It includes S itself since an empty sequence of transitions is allowed.

To compute the epsilon-closure of S, start with closure = S and repeatedly add any state reachable from a state in closure by a single epsilon-transition. Continue until no new states can be added. This can be implemented with a depth-first or breadth-first search over the epsilon-transitions graph.

Key properties include: the epsilon-closure of S is unique; it is idempotent (epsilon-closure(epsilon-closure(S)) = epsilon-closure(S)); it contains S; and it distributes over union (epsilon-closure(S1 ∪ S2) = epsilon-closure(S1) ∪ epsilon-closure(S2)).

Applications are central in processing epsilon-NFAs. They are used in converting epsilon-NFAs to NFAs or DFAs via the subset construction method, where one starts with the epsilon-closure of the start state and, for each input symbol, moves to reachable states and then takes their epsilon-closure. They also underpin algorithms that remove epsilon-transitions from an automaton, ensuring correct language recognition without empty-input moves.

Example: if there is an epsilon-path from A to B and B to C, then epsilon-closure({A}) = {A, B, C}.

---