NFA with Epsilon-Transition (ε-NFA) | Epsilon-Closure (ε-Closure) of a state | Extended Transition Function of ε-NFA | Theory Of Computation (TOC)

NFA with Epsilon(ε) Transition (ε-NFA):

The NFA with epsilon-transition is a finite state machine in which the transition from one state to another state is allowed without any input symbol i.e. empty string ε. Adding the transition for the  empty string doesn’t increase the computing power of the finite automata but adds some flexibility to construct then DFA and NFA. This are very helpful when we study regular expression (RE) and prove the equivalence between class of language accepted by RE and finite automata.

Formally, ε-NFA is defined by five tuples as:
A = (Q, ∑,𝛿, q_o, F),
Where,
Q = set of finite states
∑ = set of finite input symbols
𝛿= a transition fimction that maps: Q✕Z ∪ {ε}→ 2^^Q
q_o= Initial state, q_oЄQ
F = set of final states; F⊆Q

For Example:-

Fig: ε-NFA accepting the language {a, aa, ab, abb, b, bbb, ................... 

Transition Table:-

Epsilon-closure (ε-closure) of a state:

The s-closure of a state of ε-NFA is the set of stats those can be eased from that state with s-transition. The a-closure is defined as recursively as:

Basis: state q is in ε-closure (q).

Induction: If state q is reached with s-transition from state q, p is in ε-closure (q). And if there is

an arc from p to r labeled 2, then r is in ε-closure (q) and so on.

For Example:

ε-closure (P) = {p,q,r,s} 

ε-closure (q) = {q, s}

ε-closure (r) = {r} 

ε-closure (s) = {s}  

ε-closure (t) = {t} 

ε-closure (u) = {u,w,y}

ε-closure (v) = {v, x, y}

ε-closure (w) = {w, y}

ε-closure (x) = {x, y}

ε-closure (y) = {y}

Extended Transition Function of ε-NFA:

The extended transition function of ε-NFA denoted by 𝛿_cap, is defined as:

Basis: 𝛿_cap(q, e) = ε-closure (q)

Induction:

Let w = xa be a string, where x is substring of w without last symbol a and a ∈ E but a≠ε.

Let 𝛿_cap(q, x) = {p1, p2,...., p_k} i.e. p_i are the states that can be reached from q following path labeled x which can end with many ε & can have many ε.

Also let,

Then,

Example:

Compute for string ba

𝛿_cap(p, 2) = e-closure (p) = {p, q, r, u}

Compute for b

𝛿(p, b)∪ 𝛿(q, b) ∪ 𝛿(r, b) ∪ 𝛿(u, b) = {s, v)

ε-colsure (s) ∪ ε-closure (v) = {s, t, v}

Compurerfor next input a

𝛿(s, a) ∪ 𝛿(t, a) ∪ 𝛿(v, a) = {y, w}

ε-closure (y) ∪ ε-closure (w) = { y, w}

The final result set contains the one of the final state so the string is accepted.