Notebook 4: Epsilon-Closure and Epsilon-Removal

Interactive notebook on epsilon-closure computation and epsilon-removal from NFAs. Covers the full algorithm to convert ε-NFAs into plain NFAs, from the VVT course at UniUD.

Epsilon-Closure & Epsilon-Removal (epsilon-NFA to NFA)

This notebook walks through the epsilon-closure computation and the epsilon-removal algorithm that converts an epsilon-NFA into an equivalent NFA without epsilon-transitions. The running example is the concatenation automaton for the language \(\{ab\}\).

epsilon-NFA states:

  • \(q_0\) — initial (non-accepting)
  • \(q_1\) — reached from \(q_0\) reading \(a\)
  • \(r_0\) — reached from \(q_1\) via the \(\varepsilon\)-edge
  • \(r_1\) — accepting

epsilon-NFA transitions: \(\Delta(q_0,a)=\{q_1\}\), \(\Delta(q_1,\varepsilon)=\{r_0\}\), \(\Delta(r_0,b)=\{r_1\}\). All other transitions yield \(\varnothing\).

This epsilon-NFA recognises exactly the language \(\{ab\}\).

Widget 1: Epsilon-Closure Step-by-Step

Click Step → to compute the epsilon-closure for each state.

Step 0 / 4

ε-NFA

q1 --> a r0 --> ε r1 --> b q₀ q₁ r₀ r₁

ε-Closure Table

State ECl(state)

Widget 2: Epsilon-Removal Algorithm

Click Step → to step through the construction of the new NFA \(\mathcal{A}' = (Q, \Sigma, \Delta', q_0, F')\) from the epsilon-closures above.

For each state \(q\) and symbol \(a\): \[\Delta'(q, a) = \text{ECl}\!\bigl(\textstyle\bigcup_{p \in \text{ECl}(q)} \Delta(p, a)\bigr)\]

Step 0 / 10

ε-NFA (original)

a ε b q₀ q₁ r₀ r₁

New NFA Transition Table (Δ')

State a b

Widget 3: Word Simulation on Both Automata

Type a word over \(\{a,b\}\) (default ab) and step through it on both the original \(\varepsilon\)-NFA and the resulting NFA side by side, confirming they accept the same words.

ε-NFA — active states

a ε b q₀ q₁ r₀ r₁

NFA (ε-free) — active states

q1 (upper) --> a r0 (lower) --> a r1 --> b r1 --> b q₀ q₁ r₀ r₁

Simulation trace

Prefix ε-NFA active NFA active Accepted?

What To Notice

  1. The \(\varepsilon\)-closure absorbs free moves into transition targets. Instead of taking an \(a\)-step and then following \(\varepsilon\)-edges, the \(\varepsilon\)-removal construction folds those free moves directly into the transition function: \(\Delta'(q_0, a) = \{q_1, r_0\}\) already includes \(r_0\), which was originally reachable only via \(q_1 \xrightarrow{\varepsilon} r_0\).

  2. The resulting NFA has no \(\varepsilon\)-edges but accepts the same language. Both Widget 3 traces show identical accept/reject verdicts for every word. The language \(\{ab\}\) is preserved exactly.

  3. States \(q_1\) and \(r_0\) become equivalent in the resulting NFA. After \(\varepsilon\)-removal, both \(q_1\) and \(r_0\) have the same outgoing transitions: nothing on \(a\), and \(\{r_1\}\) on \(b\). They are indistinguishable and could be merged by a subsequent minimisation step.

  4. The accepting set \(F'\) can grow. In this example \(\text{ECl}(q_0) \cap F = \varnothing\), so \(F' = F\). But if the initial state could reach an accepting state via \(\varepsilon\)-edges, we would need to add the initial state to \(F'\), making the empty word \(\varepsilon\) accepted.