Theory of Computation – Nondeterministic Finite Automata with Null Transitions

An NFA with null transition is allowed to make transition not only on input from the alphabet but also with null input, i.e. without any input symbol. This transition without input is called null transition.
An NFA with null transition is also denoted by a 5-tuple
M = ( Q, Σ, δ, F q0)
Where Q, Σ, q0, F have their usual meaning and transition δ defines a mapping from Q x (Σ U {є})->2Q

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 q1 the set of states that the NFA is in is {q2, q3}. 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 q0) 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

  1. Every element of S is an element of є(S);
  2. For any q є є(s), every element of δ(q, є) is in є(S);
  3. 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
є (q1) = {q1, q2, q3}
є (q2) = {q2, q3}
є (q3) = {q3}

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

Note: Join free Sanfoundry classes at Telegram or Youtube

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]

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.