NFA with Epsilon Transitions

Motivation

When combining NFAs, it is useful to have “silent” transitions that consume no input.

Definition

An NFA-$\varepsilon$ is an NFA with an additional $\varepsilon$-transition relation $\tau \subseteq Q \times Q$.

We write $q \xrightarrow{\varepsilon} q'$ if $(q, q') \in \tau$.

Full Specification

$M = (Q, \Sigma, \Delta, \tau, s, F)$ where:

• $Q, \Sigma, s, F$ as before
• $\Delta \subseteq Q \times \Sigma \times Q$: labelled transitions
• $\tau \subseteq Q \times Q$: $\varepsilon$-transitions

Extended Transition Relation

Epsilon Closure

The $\varepsilon$-closure of state $q$, written $E(q)$, is the set of states reachable from $q$ via only $\varepsilon$-transitions:

$E(q) = \{q' : q \xrightarrow{\varepsilon^*} q'\}$

where $\xrightarrow{\varepsilon^*}$ is the reflexive-transitive closure of $\xrightarrow{\varepsilon}$.

Extended Transition

Define $q \Rightarrow w q'$ inductively:

$\frac{}{q \Rightarrow_\varepsilon q} \qquad \frac{q \xrightarrow{a} q'' \quad q'' \Rightarrow_w q'}{q \Rightarrow_{aw} q'} \qquad \frac{q \xrightarrow{\varepsilon} q'' \quad q'' \Rightarrow_w q'}{q \Rightarrow_w q'}$

Language

$w \in L(M) \iff \exists q_f \in F. s \Rightarrow_w q_f$

Example

NFA-$\varepsilon$ for $a^*b$:

• $Q = \{q_0, q_1, q_2\}$
• $q_0 \xrightarrow{a} q_0$ (loop on ‘a’)
• $q_0 \xrightarrow{\varepsilon} q_1$ (epsilon transition)
• $q_1 \xrightarrow{b} q_2$ (accept on ‘b’)
• $F = \{q_2\}$

Accepts: $b$, $ab$, $aab$, $aaab$, … (strings of $a$‘s ending in $b$)

Epsilon Closure Example

For the above NFA:

• $E(q_0) = \{q_0, q_1\}$ (can reach $q_1$ via $\varepsilon$)
• $E(q_1) = \{q_1\}$
• $E(q_2) = \{q_2\}$

Eliminating Epsilon Transitions

Any NFA-$\varepsilon$ can be converted to an equivalent NFA without $\varepsilon$-transitions.

Construction

Given $M = (Q, \Sigma, \Delta, \tau, s, F)$, define NFA $M' = (Q, \Sigma, \Delta', s', F')$:

$\Delta' = \{(q, a, q') : \exists q''. q \xrightarrow{\varepsilon^*} q'' \land q'' \xrightarrow{a} q'\}$

$s' = s$ $F' = F \cup \{q : E(q) \cap F \neq \emptyset\}$

Using Epsilon Transitions for Concatenation

To recognise $L_1 \cdot L_2$, connect NFAs:

1. Add $\varepsilon$-transitions from accepting states of $M_1$ to start of $M_2$
2. Start state is $s_1$
3. Accepting states are those of $M_2$

Using Epsilon for Union

To recognise $L_1 \cup L_2$:

1. Create new start state $s_{\text{new}}$
2. Add $\varepsilon$-transitions to $s_1$ and $s_2$
3. Accepting states are $F_1 \cup F_2$

---

Summary

• NFA-$\varepsilon$ allows transitions that consume no input
• $E(q)$ = set of states reachable via $\varepsilon$-transitions only
• $\varepsilon$-transitions simplify construction of combined automata
• Any NFA-$\varepsilon$ can be converted to equivalent NFA