NFA with ε-transitions

 

🧠 What is an NFA with ε-transitions?

An ε-NFA (Epsilon-NFA) is a nondeterministic finite automaton that allows transitions without consuming any input symbol. These transitions are called epsilon (ε) transitions.

💡 Think of ε-transitions as "magical moves" that let the automaton change state spontaneously, without reading any input symbol.

✅ Why ε-transitions are useful

• They allow the automaton to split computation paths.

• Help simplify automata construction (especially for regex-like patterns).

• Useful in Thompson’s Construction of NFAs from regular expressions.

---

🔍 Example: ε-NFA for the regular expression a(b|c)

Let’s build an ε-NFA that accepts strings like:

• "ab"

• "ac"

🔤 Alphabet: Σ = {a, b, c}

🎯 Intuition:

1. First input should be a.

2. Then either b or c.

🧩 States:

• $q_0$: Start

• $q_1$: After reading a

• $q_2$: ε-transition to b path

• $q_3$: after reading b

• $q_4$: ε-transition to c path

• $q_5$: Rafter reading c

• $q_6$: Final state

🛣 Transitions (δ):

• δ(q₀, a) → {q₁}

• δ(q₁, ε) → {q₂, q₄}

• δ(q₂, b) → {q₃}

• δ(q₄, c) → {q₅}

• δ(q₃, ε) → {q₆}

• δ(q₅, ε) → {q₆}

✅ Accepting state: $q_6$

---

🧠 How does it work?

• Start at q0, read a → go to q1

• From q1, make an ε-move to either:

  • q2 → read b → q3 → ε-move → q6 (accept)

  • or q4 → read c → q5 → ε-move → q6 (accept)

So the NFA accepts either "ab" or "ac".

Note:

ε -NFAs add a convenient feature but (in a sense) they bring us nothing new. They do not extend the class of languages that can be represented.

Both NFAs and ε -NFAs recognize exactly the same languages.