Practice tests · GATE

GATE theory of computation: 5 practice questions

By the PrepMatic team · Updated 9 Oct 2026 · 4 min read

Theory of Computation (TOC) is a section of the GATE CS paper, and it is the most conceptual one: you reason about languages, machines and what can or cannot be computed. Unlike the numerical subjects, the questions test whether you can classify a language, count states, or apply a closure property correctly. The five original questions below cover the patterns that repeat.

What GATE tests in TOC

The 2027 CS paper lists Theory of Computation as a section, and the topic list was revised, so check it on the official syllabus page. The standard content is regular expressions and finite automata, context-free grammars and pushdown automata, the regular and context-free classes with their closure properties and pumping lemmas, and Turing machines with decidability. Typical questions ask for the minimum number of DFA states, whether a language is regular or context-free, the language of a grammar, which closure property holds, or which problem is decidable. The real paper also has MSQ ("select all true statements"), which suits TOC well, and NAT; all five below are MCQ.

Practice questions

Question 1

The minimum number of states in a DFA over the alphabet {0, 1} that accepts exactly the strings whose third symbol from the right end is 1 is:

• A. 4
• B. 5
• C. 8
• D. 16

Question 2

Which one of the following languages is regular?

• A. {aⁿbⁿ | n ≥ 0}
• B. {ww | w ∈ {a, b}*}
• C. {a^(n²) | n ≥ 0}
• D. {aⁿbᵐ | n, m ≥ 0 and n + m is even}

Question 3

Consider the grammar S → aSb | SS | ε. The number of distinct strings of length 6 generated by it is:

• A. 3
• B. 5
• C. 8
• D. 14

Question 4

Which one of the following problems is undecidable?

• A. Whether two given context-free grammars generate the same language.
• B. Whether a given DFA accepts a given string.
• C. Whether the language generated by a given context-free grammar is empty.
• D. Whether a given regular expression generates every string over its alphabet.

Question 5

Let L1 = {aⁿbⁿcᵐ | n, m ≥ 0} and L2 = {aᵐbⁿcⁿ | n, m ≥ 0}. Both are context-free. The language L1 ∩ L2 is:

• A. regular
• B. context-free but not regular
• C. not context-free
• D. not recursive (undecidable)

Answers and explanations

1. C. The DFA must remember the last three symbols, because the symbol that is "third from the right" moves with each new input. There are 2³ = 8 possible three-symbol histories, and no two of them can be merged: any two differ in some position, and a suitable suffix then separates them. So 8 states are necessary and sufficient. An NFA needs only 4 states for the same language, which is the classic contrast.
2. D. The language is the set of even-length strings of the form a*b*. A DFA only needs to track the parity of the length read so far, plus whether a b has been seen. A is the standard non-regular example, B requires comparing two halves, and C has gaps between consecutive squares that grow without bound, so the pumping lemma rules both out.
3. B. The grammar generates exactly the balanced strings with a as an opening bracket and b as a closing one. Length 6 means 3 pairs, and the number of balanced arrangements of 3 pairs is the Catalan number C₃ = 5: aaabbb, aababb, aabbab, ababab and abaabb.
4. A. Equivalence of two context-free grammars is undecidable. Option B is decidable by simulation, C is decidable by checking whether the start symbol can derive a terminal string, and D is decidable for regular expressions because they convert to DFAs, where universality can be checked.
5. C. A string is in both languages only if the number of a's equals the number of b's, and the number of b's equals the number of c's. So L1 ∩ L2 = {aⁿbⁿcⁿ | n ≥ 0}, which is the standard example of a language that is not context-free (by the pumping lemma for CFLs). It is still decidable, since a Turing machine can check it, so D is wrong. This also shows that context-free languages are not closed under intersection.

How to prepare theory of computation

• Build a "language classification" table: regular, deterministic CFL, CFL, decidable and recognisable, with a standard example in each. Many questions compare a new language with one of these.
• Learn the closure properties as a grid. Regular languages are closed under union, intersection, complement, concatenation, star and reversal. CFLs are closed under union, concatenation, star and reversal, but not intersection or complement. Deterministic CFLs are closed under complement but not union.
• Practise DFA design by tracking what must be remembered: residues (mod k), recent symbols or flags. Verify minimality with distinguishing suffixes (Myhill-Nerode), and remember that an n-state NFA needs at most 2ⁿ DFA states.
• Know the pumping lemma proof pattern for regular and context-free languages. Seeing which part of the string gets pumped finds the answer faster.
• Memorise a short decidability list. Decidable: emptiness, membership and equivalence for regular languages, emptiness and membership for CFLs. Undecidable: equivalence and universality for CFLs, and every non-trivial property of Turing machine languages (Rice's theorem).

Pair TOC with compiler design, because lexical analysis and parsing apply regular and context-free languages directly. The GATE CSE preparation guide shows where TOC fits in the subject order, and algorithms covers the complexity side.

Take the full topic test on PrepMatic

PrepMatic's topic tests run about 15 questions in 30 minutes, which suits conceptual questions where speed comes from a clear table in your head. The free assessment shows your weakest subjects first.

← All practice tests