## 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 ﬁnite 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 ﬁnite automata but adds some ﬂexibility 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 deﬁned by ﬁve tuples as:__A = (Q, ∑,𝛿, q

_{o}, F),

Where,

Q = set of ﬁnite states

∑ = set of ﬁnite input symbols

𝛿= a transition ﬁmction that maps: Q✕Z ∪ {ε}→ 2^

^{Q}

q

_{o}= Initial state, q

_{o}ЄQ

F = set of ﬁnal 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 deﬁned 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 deﬁned 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 ﬁnal result set contains the one of the ﬁnal state so the string is accepted.

## 0 Comments

Subscribe Us and Thanks for visiting blog.