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,