TOC GATE Practice Set
Mixed GATE-style questions on DFAs, NFAs, regular expressions, closure properties, grammars, PDAs, Turing machines and decidability.
These questions mix every lesson of the Theory of Computation track, in the three GATE formats. For DFA-size questions, list the distinct situations the machine must remember, and do not forget the dead state. For "is it regular / context-free?" questions, ask what has to be counted or compared. Every numerical answer is recomputed by a program when the site is built.
Finite automata and regular languages
[Minimal DFA] How many states does the minimal DFA have for strings over {a, b} that contain an even number of a's and end with b?
Show answer and explanation
Answer: 3A product of a 2-state and a 2-state DFA has 4 states, but two of them merge. When the number of a's is odd, it does not matter whether the string ends in b: no continuation behaves differently. So the classes are (even, ends in b), (even, does not end in b) and (odd): 3 states.
[Minimal DFA] How many states does the minimal DFA have for binary numbers (read from the most significant bit) divisible by 6?
Show answer and explanation
Answer: 4Reading bit b takes remainder r to (2r + b) mod 6, and 2(r + 3) + b ≡ 2r + b (mod 6), so r and r + 3 always move to the same state. Remainders 1 and 4 therefore merge, and so do 2 and 5 (none of them accepts). 0 and 3 stay apart because only 0 is accepting. The classes are {0}, {3}, {1, 4}, {2, 5}: 4 states.
[DFA vs NFA] An NFA for "the 4th symbol from the end is a" over {a, b} has 5 states. How many states does the minimal DFA for this language have?
Show answer and explanation
Answer: 16The DFA must remember the last 4 symbols, and any two different 4-symbol windows are distinguishable: 2⁴ = 16 states.
[Subset construction] The NFA s –a→ {s, t}, s –b→ {s}, t –b→ {u}, u –a→ {u}, u –b→ {u}, with start s and accepting state u, accepts strings containing ab. How many reachable states does the subset construction produce?
Show answer and explanation
Answer: 4The reachable subsets are {s}, {s, t}, {s, u} and {s, t, u}. (The last two are both accepting and accept everything afterwards, so minimization would merge them into a 3-state DFA.)
[Counting strings] How many strings of length 6 over {0, 1} have no two consecutive 1s?
Show answer and explanation
Answer: 21Let f(n) be the count. A valid string ends in 0 (any valid string of length n − 1 before it) or in 01 (any valid string of length n − 2 before it), so f(n) = f(n − 1) + f(n − 2), with f(1) = 2 and f(2) = 3: 2, 3, 5, 8, 13, 21.
[Regular?] Which languages are regular? (Select all that apply.)
Show answer and explanation
Answer: A, CThe difference mod 3 needs only 3 states. n ≥ m compares unbounded counts. A language with n ≤ 50 is finite. The primes have unboundedly growing gaps, which the pumping lemma rules out.
Context-free languages and machines
[CFL?] Which languages are context-free? (Select all that apply.)
Show answer and explanation
Answer: A, Caⁿbᵐcᵐdⁿ is nested (match the b's with the c's inside the a's and d's). aⁿbᵐcⁿdᵐ has crossing comparisons. Comparing two counts with a fixed ratio needs one stack. aⁿbⁿcⁿ needs three equal counts.
[Ambiguity] How many parse trees does a + a * a + a * a have in the grammar E → E + E | E * E | a?
Show answer and explanation
Answer: 14The grammar gives no precedence, so every way of fully parenthesising the 5 operands is a parse tree: the Catalan number C₄ = 14.
[CNF] In Chomsky normal form, how many steps does a derivation of a string of length 10 take?
Show answer and explanation
Answer: 19n − 1 = 9 steps of the form A → BC and n = 10 steps of the form A → a: 19.
[Closure] L₁ is context-free and L₂ is regular. Which of these is not necessarily context-free?
Show answer and explanation
Answer: DCFLs are closed under union and concatenation, and under intersection with a regular language. They are not closed under complement: the complement of a CFL need not be context-free.
[PDA] Which language needs a nondeterministic PDA (no DPDA accepts it)?
Show answer and explanation
Answer: CWithout a centre marker, the PDA must guess where w ends. The others are deterministic: the counts are compared in order, and the marker c tells the PDA when to start popping.
Turing machines and decidability
[Turing machine] The binary increment TM (move right to the end, then add 1 with carry going left) runs on input 1111. What is on the tape when it halts?
delta = {("right", "0"): ("right", "0", "R"), ("right", "1"): ("right", "1", "R"),
("right", "_"): ("carry", "_", "L"), ("carry", "1"): ("carry", "0", "L"),
("carry", "0"): ("done", "1", "L"), ("carry", "_"): ("done", "1", "L")}
tape, state, head = dict(enumerate("1111")), "right", 0
while state != "done":
state, tape[head], move = delta[(state, tape.get(head, "_"))]
head += 1 if move == "R" else -1
print("".join(tape[i] for i in sorted(tape)).strip("_"))Show answer and explanation
Answer: CAll four 1s become 0 as the carry moves left, and the carry then writes a 1 into the blank cell before the number: 1111 (15) + 1 = 10000 (16).
[Decidability] Which problems are decidable? (Select all that apply.)
Show answer and explanation
Answer: A, BDFA emptiness is reachability, and CFG membership is CYK. CFG universality is undecidable, and halting on ε is a form of the halting problem.
[RE and recursive] L is recursively enumerable and its complement L̄ is also recursively enumerable. What follows?
Show answer and explanation
Answer: ARun the recognisers for L and for L̄ alternately, one step each. One of them must accept, so this always halts and decides L.