An ε-transition consumes no input. Conversion fails when you take the closure only at the start or only after a move, instead of at both points. These 10 solved MCQs cover ε-closure, elimination, equivalent DFA and NFA behaviour, subset construction, and state counts using one invariant: next(S,a) = ε-closure(move(ε-closure(S),a)). The exact KnowledgeGate pool has over 10 published questions in this subtopic. Use GATE CS Exam Preparation for the wider syllabus, GATE Guidance by Sanchit Sir to rebuild concepts, and the Epsilon NFA & Conversion PYQ Questions hub for more practice. Questions 1-6 also open on their exact solved pages.
1. Epsilon NFA conversion MCQs: the closure-first solving rule
ε-closure(S) contains every state reachable from S through zero or more ε-edges, including every state already in S. An ordinary alphabet edge consumes a symbol. An ε-edge changes state without consuming one.
Calibrate the rule on states {q0,q1,q2}, alphabet {a,b}, start q0, final {q2}, and edges q0 --ε--> q1, q1 --a--> q1, q1 --b--> q2, q2 --b--> q2. Since ε-closure({q0})={q0,q1}, the DFA start is A={q0,q1}.
DFA state | On | On | Final? |
|---|---|---|---|
|
|
| No |
|
|
| No |
|
|
| Yes |
|
|
| No |
Only C contains original final state q2. See NFA to DFA Conversion for GATE for the complete method. The three traps are omitting the source closure, omitting the destination closure, and marking a subset final only when all its states are final. One final NFA state in the subset is enough.
2. Identifier automata and extended transitions: MCQs 1-2
Question 1
Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions:
letter → [A-Za-z]
digit → [0-9]
id → letter (letter | digit)∗
Which one of the following Non-deterministic Finite-state Automata with - transitions accepts the set of valid identifiers? (A double-circle denotes a final state)
(a) 
(b) 
(c) 
(d) 
Answer: (c). It consumes one required letter into a final state. Its ε-branches then take either one letter or one digit edge and return by ε, implementing each repetition. Thus a1b follows letter, digit, letter trips, while 1a has no valid first move. Option (a) bypasses the required letter and accepts ε. Option (b) splits into a letter-only or digit-only suffix, so it cannot accept a1b. Option (d) repeats a fixed letter digit pair, accepting ab1 but rejecting valid ab and a1b.
Question 2
Let \(\delta\) denote the transition function and \(\widehat{\delta}\) denote the extended transition function of the \(\epsilon\)-NFA whose transition table is given below:
!Transition table for Question 2
Then \(\widehat{\delta}(q_2, aba)\) is
(a) \(\emptyset\)
(b) \(\{q_0, q_1, q_3\}\)
(c) \(\{q_0, q_1, q_2\}\)
(d) \(\{q_0, q_2, q_3 \}\)
Answer: (c). The table rows q0,q1,q2,q3 have ε-columns {q2},{q2},{q0},∅, a-columns {q1},{q2},∅,∅, and b-columns {q0},{q3},∅,{q2}. Although the start arrow points to q0, this trace begins at q2.
Stage | Raw move | Closure |
|---|---|---|
Start |
|
|
Read |
|
|
Read |
|
|
Read |
|
|
Option (d) is only the intermediate set after ab.
3. Accepted language and shortest strings: MCQs 3-4
Question 3
What is the complement of the language accepted by the NFA shown below? Assume \(\sum = \{a\}\) and \(\varepsilon\) is the empty string
(a) \(\phi\)
(b) \(\{\varepsilon \}\)
(c) \(a^*\)
(d) \(\{a, \varepsilon \}\)
Answer: (b). The non-final start takes a to the final middle state. The middle has ε to the right state, which has ε back to the start. Therefore ε is rejected, a is accepted, and aa resets by two ε-moves before consuming its second a. The same cycle accepts every a^n for n≥1. Hence L=a+, and relative to Σ*, its complement is {ε}. Flipping an NFA's final circles alone is not a valid complementation method.
Question 4
What is the minimum length of a string that can take the automaton from the start state to the final state?
(a) 0
(b) 1
(c) 2
(d) 3
Answer: (b). Here M=({q0,q1,q2,q3},{a},δ,q0,{q3}). The ε-transitions are q0->{q1}, q1->{q2}, q2->∅, q3->∅; on a, only q2->{q2,q3} is non-empty. Since ε-closure(q0)={q0,q1,q2} excludes q3, length 0 fails. The path q0 --ε--> q1 --ε--> q2 --a--> q3 proves that the one-character string a works. The minimum is 1.
4. Regex recognition and final DFA subsets: MCQs 5-6
Question 5
Consider the regular expression R = (a + b)* (aa + bb) (a + b)*<br>
Which of the following non-deterministic finite automata recognizes the language defined by the regular expression R? Edges labeled λ denote transitions on the empty string.
(a) A
(b) B
(c) C
(d) D
Answer: (a). The expression means "contains aa or bb somewhere." In A, s0 loops on a,b for any prefix, branches on a to s1 or b to s2, detects aa with s1 --a--> s3 or bb with s2 --b--> s3, and final s3 loops for any suffix. For abaa, loop over ab, branch on the third a, then reach s3 on the fourth. abab is rejected because it has neither adjacent pair. Cross-transitions preserve a possible new one-symbol prefix. The other diagrams misplace the free loops and change the required prefix or suffix behaviour.
Question 6
What are the final states of the DFA generated from the following NFA? , ISRO 2013
NFA
(a) q0, q1, q2
(b) [q0, q1], [q0, q2], [ ]
(c) q0, [q1, q2]
(d) [q0, q1], q2
Answer: (a). In the NFA, start q0 loops on 0 and has ε to q1; q1 loops on 1 and has ε to final q2; q2 loops on 2. The accepting DFA subsets are D0=ε-closure({q0})={q0,q1,q2}, D1=ε-closure(move(D0,1))={q1,q2}, and D2=ε-closure(move(D0,2))={q2}. Each contains original final q2. The dead subset ∅ is not final. The option's q0,q1,q2 are assigned DFA-state names, not singleton NFA subsets.
5. Cofinite languages and full epsilon-closures: MCQs 7-8
Question 7
Consider the following statements.
S1: L = {aⁿ | Σ = {a} and n < 10⁹⁹} is a cofinite language.
S2: For any state q, the epsilon closure of q may be an empty set.
Which of the above statements is/are TRUE?
(a) Only S2
(b) Only S1
(c) Both S1 and S2
(d) Neither S1 nor S2
Answer: (d). L={ε,a,a²,...,a^(10⁹⁹−1)} is finite, but its complement inside a*, {a^(10⁹⁹),a^(10⁹⁹+1),...}, is infinite. Therefore L is not cofinite, so S1 is false. Zero ε-moves are allowed, which means q∈ε-closure(q) for every state. The closure cannot be empty, so S2 is also false.
Question 8
Consider the NFA
Epsilon closure of q0 is:
(a) {q4, q3, q5} only
(b) {q3, q4} only
(c) {q0,q5} only
(d) {q0, q1, q2, q3, q4, q5}
Answer: (d). Put q0 in the closure first. ε-reachability adds q1, q2, and q5; then q1 --ε--> q4, q2 --ε--> q3, and q4 --ε--> q5. At the fixed point the closure is {q0,q1,q2,q3,q4,q5}. Do not use q1 --a--> q3 or q3 --b--> q4, because they consume input. Each distractor either omits q0 despite the zero-move rule or stops before transitive ε-reachability is exhausted.
6. Transition signatures and DFA-NFA equivalence: MCQs 9-10
Question 9
Consider the following definition of machine (M) such that
Q: set of states
Σ: alphabet
Q0 : is start state
F ⊆ Q is set of final states
δ: Q × (Σ ∪ {ε}) → Q
M represents
(a) Deterministic finite automata
(b) Non deterministic finite automata
(c) Pushdown automata
(d) None of the above
Answer: (d). Compare both the domain and codomain:
Machine | Standard transition signature |
|---|---|
DFA |
|
NFA |
|
ε-NFA |
|
PDA |
|
The stated function permits ε but returns one state in Q. This hybrid matches none of the standard definitions, and it has no stack alphabet Γ. The codomain matters as much as the presence of ε.
Question 10
Which of the following statements is correct regarding the language accepted by an NFA compared to a DFA?
(a) NFAs accept only context-free languages.
(b) NFAs accept fewer languages than DFAs.
(c) NFAs accept more languages than DFAs.
(d) NFAs and DFAs accept exactly the same set of languages.
Answer: (d). Both recognise exactly the regular languages. Nondeterminism may shorten a description, but it adds no recognition power. For example, take NFA states {s,t}, start s, final {t}, δ(s,0)={s,t}, δ(s,1)={s}, with no outgoing moves from t. It recognises binary strings ending in 0. Its equivalent DFA has non-final A, final B, and transitions A--0-->B, A--1-->A, B--0-->B, B--1-->A. Both accept 1010 and reject 1011. General context-free languages need more than finite-state memory.
7. Epsilon NFA conversion checklist and next practice step
Keep this five-line checklist on your scratch pad:
Write the start closure.
Close before each alphabet move.
Move on exactly one symbol.
Close every destination set.
Mark every subset containing an original final state.
If ordinary NFA branching and ε-movement still blur together, solve NFA Basics & Design MCQs. An ordinary NFA branch consumes a symbol. An ε-NFA branch may move before consuming one.
Once you can reproduce the calibration transition table without help, use the GATE Test Series as your next timed practice step. The short version is closure, move, closure, on every symbol, then mark each subset that contains any original final state.
