An NFA with null transition is also denoted by a 5-tuple

M = ( Q, Σ, δ, F q

_{0})

Where Q, Σ, q

_{0}, F have their usual meaning and transition δ defines a mapping from Q x (Σ U {є})->2

^{Q}

Consider the NFA in the above diagram. Null transition makes the designing of an NFA simpler as it reduces the complexity of the design and in some cases reduces the number of states too. In the above example for the NFA with null transition on giving input a to q_{1} the set of states that the NFA is in is {q_{2}, q_{3}}. When a state is reached and if it has null transition the states that can be reached by the null transition are also included in the current set of states.

**Null Closure**

Let M = ( Q, Σ, δ, F q_{0}) be an NFA with null transitions, and let S be any subset of Q. The є- closure of S is the set є(s) defined as follows

- Every element of S is an element of є(S);
- For any q є є(s), every element of δ(q, є) is in є(S);
- No other element of Q are in є(S)

In simple words, є(S) is set of all the states that can be reached from S without giving any input

**Calculating null closure є (S)**

Start with T = S. Make a sequence of passes, in each pass considering every q є T and adding to T all elements of δ(q, є) that are not already in T. Stop after any pass in which T does not change. The set є(S) is the final value of T.

Null closure for the given NFA

є (q_{1}) = {q_{1}, q_{2}, q_{3}}

є (q_{2}) = {q_{2}, q_{3}}

є (q_{3}) = {q_{3}}

**Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.**

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Apply for Computer Science Internship
- Check Computer Science Books
- Practice Computer Science MCQs
- Check Automata Theory Books