Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

# NFA with ∈-Moves

NFA with ∈ moves is exactly same as NFA without ∈ moves.

But differece exist in the transition function δ. δ must include information about ∈ transitions.

NFA with ∈-Moves has 6 tuples (Q, Σ, δ, q0, F).

Where,

• Q = finite set of states.
• Σ = finite set input symbols.
• δ = transition function that maps Q × (Σ ∪{∈}) to 2Q.
• q0 = initial state.
• F = set of final states.

The non-deterministic finite automaton can be extended to include the transitions on null/empty input ∈.

## For example,

In this NFA with epsilon,

• It accept an input string ‘aabc’.
• Or string as number of a’s followed by number of b’s followed by number of c’s.
• The string ‘aabc’ is accepted by the NFA by following the path with labels a, a, ∈, b, ∈, c.

## Transition table for above NFA.

### ∈-closure

∈-closure of a state q is a set of states following by all transitions of q that are labeled as ∈.

• ∈-closure (q0) = (q0, q1, q2)
• ∈-closure (q1) = (q1, q2)
• ∈-closure (q2) = (q2)

### NFA with ∈ to NFA without ∈

Transition table NFA with ∈

First find out ∈ closure:∈-closure

• (q0) = (q0, q1, q2)
• ∈-closure (q1) = (q1, q2)
• ∈-closure (q2) = (q2)

Transition table NFA without ∈

Reference:

• Introduction to the Theory of Computation” by Michael Sipser.
Categories TOC