An NFA can keep several states alive after one symbol. Tracing a single path, treating a branch as deterministic, or skipping the no-merge check turns a plausible answer into a wrong one. Commit to an option and write a transition set or a state-count argument before reading each explanation.
Five skills decide the 12 questions below: naming closure properties, counting states from residues or positions, sharing a prefix across a union, tracing a set instead of a path, and proving two accepting states equivalent. Where a question has its own worked solution page, the link follows its explanation; the others sit on the NFA Basics & Design PYQ Questions page, which holds over 20 questions on this subtopic. For the syllabus around them, work through GATE CS Exam Preparation.
1. NFA basics to fix before solving the 12 MCQs
Task | Reliable method |
|---|---|
Acceptance | At least one complete path must end in a final state. |
State-set tracing | Union every transition from every currently reachable state. |
Construction | Give an upper bound, then explain why fewer states fail. |
Closure | NFAs and DFAs recognise exactly the regular languages. |
Calibrate with an NFA over {0,1} for strings whose third symbol from the right is 1. State q0 is the start, q3 is final, and q0 loops on both symbols. On 1, it can also branch to q1; from q1, either symbol goes to q2; from q2, either goes to q3. State q3 has no outgoing transition. Each branch guesses that its chosen 1 is the target. It survives exactly two more symbols, so it accepts only when that 1 is third from the right.
For 1100, the sets are {q0} -> {q0,q1} -> {q0,q1,q2} -> {q0,q2,q3} -> {q0,q3}. Since q3 remains after the full input, accept. For 1010, the sets are {q0} -> {q0,q1} -> {q0,q2} -> {q0,q1,q3} -> {q0,q2}. The final set lacks q3, so reject.
2. NFA MCQs 1-3: closure, uniqueness and residue tracking
Question 1 (BPSC 2024)
Under which of the following operation, NFA is not closed?
(a) Negation
(b) Kleene
(c) Concatenation
(d) More than one of the above
(e) None of the above
Answer: (e) None of the above. NFA languages are closed under complement, Kleene star and concatenation. For complement, determinise a complete DFA before swapping final and non-final states. Solved page.
Question 2
Q. Let L be a regular language. Consider the following statements:
Statement 1: The minimal DFA for L is unique.
Statement 2: The minimal NFA for L is unique.
Which of the above statement(s) is/are correct?
(a) Only Statement 1
(b) Only Statement 2
(c) Both 1 and 2
(d) Neither 1 Nor 2
Answer: (a) Only Statement 1. Minimal DFAs are unique up to renaming because states represent Myhill-Nerode classes. Minimum NFAs may have different non-isomorphic structures, so Statement 2 fails.
Question 3
The smallest finite automaton which accepts the language {x | length of x is divisible by 500} has
(a) 200 states
(b) 300 states
(c) 400 states
(d) 500 states
Answer: (d) 500 states. Track residues 0 to 499 modulo 500; each symbol advances one, and only 0 accepts. Different residues need different suffix lengths to accept, so none can merge.
3. NFA MCQs 4-6: minimum states for unary and fixed-length languages
Question 4 (UGC NET 2018)
Consider the language L given by
L = { 2ⁿᵏ | k > 0, and n is non-negative integer number }
The minimum number of states of finite automaton which accepts the language L is
(a) n
(b) n + 1
(c) n(n+1)/2
(d) 2ⁿ
Answer: (b) n + 1. Epsilon is rejected because lengths are positive multiples of n. A non-final start plus an n-state cycle uses n+1 states and accepts residue 0 only after input. Solved page.
Question 5
Consider a language L over Σ = {a, b} such that
L = {w ∈ {a, b}* | |w| = 51 and w ends with “b”}.
The number of states in the minimum NFA of L are ____
(a) 50
(b) 51
(c) 52
(d) Can’t say
Answer: (c) 52. Use q0 through q51 to record input length. Both symbols advance until q50, where only b reaches final q51; merging positions destroys exact length.
Question 6
Consider a language L over Σ = {a} generated by regular expression {aaa+aaaaa}*.
The number of states in min NFA which recognize L are ____
(a) 2
(b) 3
(c) 4
(d) 5
Answer: (d) 5. Make q0 start and final, with q0 -a-> q1 -a-> q2. On the third a, branch to q0 for aaa, or to q3; q3 -a-> q4 -a-> q0 finishes aaaaa. This rejects lengths 1, 2, 4 and 7.
4. NFA MCQs 7-9: union constructions, shared prefixes and substrings
Question 7
Consider a language L = {w | w ∈ {a,b}* and |w| mod 3=0 OR |w| mod 5=0}. The NFA which accepts L has total number of states and final states respectively.
(a) 8 and 1
(b) 9 and 3
(c) 16 and 1
(d) 8 and 2
Answer: (b) 9 and 3. Final start state S handles length 0; the first symbol branches into separate 3-state and 5-state cycles. Thus 1+3+5=9 states, while S and both residue-0 states give 3 finals.
Question 8 (UGC NET 2012)
The minimum number of states of the non-deterministic finite automaton (NFA) which accepts the language
{ aba bⁿ | n ≥ 0 } ∪ { ab aⁿ | n ≥ 0 }
(a) 3
(b) 4
(c) 5
(d) 6
Answer: (c) 5. Share q0 -a-> q1 -b-> q2, making q2 final for ab. On the next a, branch to final q3 and q4, which loop on a and b. Merging them admits mixed tails. Solved page.
Question 9 (GATE 2010)
Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
(a) n - 1
(b) n
(c) n + 1
(d) 2ⁿ⁻¹
Answer: (c) n + 1. Make q0 the start and all n+1 boundary states final. It jumps to every first-symbol match, then follows consecutive characters of w. Solved page.
5. NFA MCQs 10-12: transition sets and equivalent accepting states
Question 10 (GATE 2014)
Consider the finite automaton in the following figure.
What is the set of reachable states for the input string 0011 ?
(a) {q0, q1, q2}
(b) {q0, q1}
(c) {q0, q1, q2, q3}
(d) {q3}
Answer: (a) {q0, q1, q2}. For 0011, trace {q0} -> {q0} -> {q0} -> {q0,q1} -> {q0,q1,q2}. The final set excludes q3. Solved page.
Question 11
Consider the following NFA:
The NFA Accepts
(a) All the strings which has substring “11”.
(b) All strings which has exactly two one’s.
(c) All strings which has at least two one’s and ends with a 0.
(d) All strings which has at least two one’s.
Answer: (d) All strings which has at least two one’s. States q0 and q1 skip symbols while choosing two 1s that reach final q2. Choose the last two, leaving only zeroes for q2, so adjacency is unnecessary and extra ones are allowed.
Question 12 (GATE 2005)
Consider the non-deterministic finite automaton (NFA) shown in the figure.
State X is the starting state of the automaton. Let the language accepted by the NFA with Y as the only accepting state be L1. Similarly, let the language accepted by the NFA with Z as the only accepting state be L2. Which of the following statements about L1 and L2 is TRUE?
(a) L1 = L2
(b) L1 ⊂ L2
(c) L2 ⊂ L1
(d) None of the above
Answer: (a) L1 = L2. After every prefix, Y is reachable exactly when Z is: 0 from X reaches both, and later transitions preserve the pair. Since 1 at X stays there, a string reaches either precisely when it reaches the other. Solved page.
6. NFA design traps exposed by these 12 questions
Trap | Fix |
|---|---|
One path versus a state set | Q10-12: retain every reachable state. |
DFA versus NFA uniqueness | Q2: only the minimal DFA is unique up to renaming. |
Positive multiple versus epsilon | Q4: keep the start non-final. |
Fixed length versus final symbol | Q5: count 51 symbols, then enforce |
Separate loops versus mixed tails | Q6 and Q8: keep different suffix branches apart. |
Closure versus direct state flipping | Q1: determinise and complete before complementing. |
For a timed solve, write the condition, mark whether epsilon belongs, trace sets, construct an upper bound, then try merging states. Test any merge with the shortest counterexample string.
Question 8 must accept ab, aba, abaa and abab, but reject abb, ababa and abaab. The separate tail loops make that happen. Next, read Finite Automata: DFA vs NFA Explained, then attempt Finite Automata MCQs: 10 Solved DFA and NFA (GATE).
7. NFA basics and design: the short version and next practice step
Redo Questions 4, 6, 8, 10 and 12 without looking. Together they test epsilon handling, block construction, shared-prefix design, state-set simulation and language-equivalence proof.
An NFA accepts through at least one complete path.
A reachable configuration is a set of states.
Nondeterminism can share prefixes and guess positions.
A state-count answer needs a construction and a no-merge argument.
NFAs and DFAs recognise the same regular languages, although their minimal structures behave differently.
GATE Guidance by Sanchit Sir provides a sequenced Theory of Computation route beside DFA, regular expressions and conversions. When a wrong answer comes from following only one path, rewrite the solution as a set sequence before attempting another MCQ.
