Finite automata is the entry point to Theory of Computation, and it is also the subtopic GATE returns to most reliably: DFA design, minimal-state counting, closure under complement, and the cost of turning an NFA into a DFA. Below are 10 solved MCQs from KnowledgeGate's published question bank, every one a previous-year GATE problem with the year marked. Attempt each before reading the explanation, which is short on purpose. A few questions originally referred to a diagram; those have been restated fully in words so nothing is missing. A note on the deep links: each question here carries a GATE tag inside the course, so we link its exact solved page. If the theory feels shaky, the Finite Automata: DFA vs NFA deep dive and the Theory of Computation learn module rebuild it from scratch.
DFA basics and construction
Q1. Which of the following sets can be recognized by a deterministic finite automaton? (GATE 1998)
(a) The numbers 1, 2, 4, 2ⁿ written in unary
(b) The set of binary strings with equal numbers of zeros and ones
(c) The numbers 1, 2, 4, 8, 2ⁿ written in binary
(d) The set { 1, 101, 11011, 1110111, ... }
Answer: (c). A DFA recognizes exactly the regular languages, so it can only use finite memory. The binary representations of powers of two are 1, 10, 100, 1000, and so on, which is precisely the regular expression 10*, so a DFA accepts them. The other three all need unbounded counting, whether of length, of a zero to one balance, or of a growing block pattern (see the solved page).
Q2. A DFA over {0, 1} has three states that track the trailing run of zeros: a start state with no trailing zero, a middle state with exactly one trailing zero, and an accepting state with two or more trailing zeros, where reading a 1 sends you back toward the start. The set of strings it accepts is those that (GATE 2009)
(a) begin either with 0 or 1
(b) end with 0
(c) end with 00
(d) contain the substring 00
Answer: (c). Acceptance depends only on the last two symbols. Any 1 resets the trailing zero count, and only after two consecutive zeros with no later 1 does the machine sit in its accepting state. That is exactly the set of strings ending in 00, which is a stricter condition than merely containing the substring 00 somewhere (see the solved page).
DFA minimization and complement
Q3. A regular language L over the single-letter alphabet {a} has a minimal finite automaton with exactly two states forming a 2-cycle on input a. What can be said about L? (GATE 2000)
(a) L must be { aⁿ | n is odd }
(b) L must be { aⁿ | n is even }
(c) L must be { aⁿ | n ≥ 0 }
(d) Either L must be { aⁿ | n is odd }, or L must be { aⁿ | n is even }
Answer: (d). Two states in a cycle on a flip between each other on every symbol, so they encode the parity of the input length. If the start state is accepting, the language is the even-length strings; if the other state is accepting, it is the odd-length strings. Both are possible, and only those two, since making both or neither accepting would collapse the machine to one state (see the solved page).
Q4. Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimal deterministic finite automaton accepting L is (GATE 1998)
(a) 2
(b) 5
(c) 8
(d) 3
Answer: (b) 5. The machine must remember enough recent history to judge whether the last two symbols matched. Distinct states are needed for the start, for a single trailing 0, for a single trailing 1, and then two accepting states for strings ending in 00 and in 11. Those five cases cannot be merged without losing information, so the minimal DFA has 5 states (see the solved page).
Q5. Consider the regular expression (0+1)(0+1)...(0+1), where (0+1) is repeated n times. The minimal finite automaton recognizing this language contains (GATE 1999)
(a) n states
(b) n + 1 states
(c) n + 2 states
(d) None of the above
Answer: (c) n + 2 states. The expression describes every binary string of exactly length n. The machine needs one state for each count of symbols read, from 0 up to n, which is n + 1 states, with the last one accepting. One more dead state is required to trap any string longer than n, giving n + 2 states in total (see the solved page).
Q6. A DFA over {a, b} accepts exactly the strings that end with ab. If its final and non-final states are interchanged, the new DFA accepts (GATE 2008)
(a) the set of all strings that do not end with ab
(b) the set of all strings that begin with either a or b
(c) the set of all strings that do not contain the substring ab
(d) the set described by the regular expression baa(ba)b
Answer: (a). Swapping accepting and non-accepting states on a complete DFA accepts the complement of the original language. The original accepts strings ending in ab, so the new machine accepts every string that does not end in ab. Do not confuse "does not end with ab" with "does not contain ab", which is a different and smaller language (see the solved page).
NFA and NFA to DFA conversion
Q7. Let N be an NFA with n states and M the minimized DFA with m states recognizing the same language. Which of the following is necessarily true? (GATE 2008)
(a) m ≤ 2ⁿ
(b) n ≤ m
(c) M has one accept state
(d) m = 2ⁿ
Answer: (a). Subset construction builds a DFA whose states are subsets of the NFA's states, and an n-element set has at most 2ⁿ subsets, so the constructed DFA has at most 2ⁿ states. Minimization only removes states, so the minimal DFA also satisfies m ≤ 2ⁿ. The bound is an upper limit, not an equality, and nothing forces a single accept state (see the solved page).
Q8. Let N be an NFA with n states, and let k be the number of states of a minimal DFA equivalent to N. Which one is necessarily true? (GATE 2018)
(a) k ≥ 2ⁿ
(b) k ≥ n
(c) k ≤ n²
(d) k ≤ 2ⁿ
Answer: (d). This is the same subset-construction bound asked a decade later. The determinized DFA has at most 2ⁿ states, and minimizing it can only reduce that count, so k ≤ 2ⁿ always holds. The lower-bound and n² options fail because a minimal DFA can have far fewer states than the NFA, and never needs a quadratic bound (see the solved page).
Q9. For an arbitrary NFA with N states, the number of states in the equivalent minimal DFA can, in the worst case, be as large as (GATE 2001)
(a) N²
(b) 2ᴺ
(c) 2N
(d) N!
Answer: (b) 2ᴺ. While Q7 and Q8 give the upper bound, this question asks whether that bound is actually reached, and it is. There are standard language families where every one of the 2ᴺ subsets of NFA states is genuinely distinguishable, so the minimal DFA truly needs 2ᴺ states. That tightness is why the exponential blow-up matters in practice (see the solved page).
Q10. An NFA over the single-letter alphabet {a} accepts every non-empty string of a's, that is the language a⁺. Its complement is (GATE 2012)
(a) ∅
(b) { ε }
(c) a*
(d) { a, ε }
Answer: (b) { ε }. The machine accepts a, aa, aaa, and so on, but not the empty string, because the start state is not accepting and no epsilon path reaches an accepting state. The complement over {a} therefore contains exactly the one string the NFA rejects, the empty string ε. It is a clean reminder that complementing is taken over the full alphabet, here just powers of a plus ε (see the solved page).
How finite automata is examined
The set mirrors how GATE keeps testing this topic. Construction questions (Q1, Q2) reward reading a machine as a memory of the recent past, usually the last symbol or two. Minimization questions (Q3 to Q6) turn on two ideas: counting the distinguishable states a language actually needs, and knowing that swapping accept states yields the complement. The NFA to DFA block (Q7 to Q10) is almost entirely about one fact, the 2ⁿ subset-construction bound, asked as an upper bound, as a tight worst case, and as a small complement puzzle.
If a question exposed a gap, that is a conceptual gap, not a practice-volume one. Rebuild the ideas in the GATE CS Exam category and drill the full previous-year sets inside GATE Guidance by Sanchit Sir. Solve, review the ones you missed, and return to this set a week later; the second pass is where the marks get locked in.
