Theory of Computation GATE CSE PYQ Topic Wise (2016–2026)

Explore: GATE CS hub · All GATE CS topics · Syllabus & pattern · GATE CS 2026

Answer first

Theory of Computation has appeared in 11 of the 11 official GATE CS papers from 2016–2026, with 54 questions in all. It averages 7.8 marks a year, which puts it 5th of 11 technical subjects. The last three papers gave it 5 (2026), 8 (2025), 7 (2024).

The concepts that came back most often are Context-Free Languages, Regular Languages, Finite Automata. Context-Free Languages, Regular Languages, Finite Automata, Decidability appeared in at least 7 of the 11 years. 13% of the questions are NAT, so you have to work out an exact value with no options to eliminate.

Marks per year

One official set per year (set 1 where GATE CS ran two sessions). Marks are as printed in the official answer key.

Most-asked concepts

Sorted by how many years a concept appeared in, then by marks.

How to practise Theory of Computation from these PYQs

1. Start with the concepts at the top of the table above. They repeat, so they pay off first.
2. Open the official PDF for a year, solve only that year’s TOC questions against the clock (about 3 minutes a mark), then check the official key listed below.
3. Log each miss by concept and type (MCQ, MSQ, NAT). An MSQ with one extra option scores zero, so log those separately.
4. Once a concept is clean across two or three years, move on to the next one.
5. Then sit a full year paper from the GATE CS hub so the subject drill turns into exam timing.

Questions by year

Each line gives the official question number, marks, type and concept, our one-line summary and the official key. The full question is in the official PDF linked under each year.

GATE CS 2026 (CS1)

• Q.26 · 1 mark · MSQ · Finite Automata: Impossible minimal-DFA sizes for a 6-state NFA (key: B, D)
• Q.51 · 2 marks · MSQ · Regular Languages: Closure facts when L1∩L2 and L2 are regular (key: C)
• Q.52 · 2 marks · MSQ · Context-Free Languages: Properties of a given context-free grammar's language (key: B, D)

Paper: official PDF · GATE CS 2026 page

GATE CS 2025 (CS1)

• Q.19 · 1 mark · MCQ · Context-Free Languages: Language generated by a small context-free grammar (key: A)
• Q.28 · 1 mark · MSQ · Finite Automata: False statements about NFA and DFA state counts for a regular language (key: D)
• Q.44 · 2 marks · MCQ · Regular Languages: Regularity of two languages of the form alpha beta alpha (key: C)
• Q.45 · 2 marks · MCQ · Context-Free Languages: Whether two counting languages are context-free (key: C)
• Q.50 · 2 marks · MSQ · Finite Automata: Language accepted by a given DFA over {a, b} (key: C)

Paper: official PDF · GATE CS 2025 page

GATE CS 2024 (CS1)

• Q.23 · 1 mark · MSQ · Closure Properties: Statements that always hold for regular and non-regular languages (key: C, D)
• Q.50 · 2 marks · MSQ · Finite Automata: Properties of strings accepted by a five-state DFA (key: B, C)
• Q.59 · 2 marks · NAT · Context-Free Languages: Number of derivation steps for a string in a CNF grammar (key: 179)
• Q.61 · 2 marks · NAT · Regular Languages: Count short strings belonging to neither of two regular expressions (key: 44)

Paper: official PDF · GATE CS 2024 page

GATE CS 2023

• Q.14 · 1 mark · MCQ · Finite Automata: Regular expression for the language accepted by a four-state DFA (key: C)
• Q.24 · 1 mark · MSQ · Closure Properties: Closure under intersection of regular, CFL, recursive and RE languages (key: A, C, D)
• Q.39 · 2 marks · MCQ · Context-Free Languages: Language generated by a given context-free grammar (key: B)
• Q.40 · 2 marks · MCQ · Pushdown Automata: Language accepted by a given pushdown automaton (key: A)
• Q.63 · 2 marks · NAT · Finite Automata: Minimum DFA states for strings without three consecutive 1s (key: 4)

Paper: official PDF · GATE CS 2023 page

GATE CS 2022

• Q.12 · 1 mark · MCQ · Regular Languages: Regular expression equivalent to a given finite automaton (key: D)
• Q.23 · 1 mark · MSQ · Decidability: True statements about recursive and recursively enumerable languages (key: B,C,D)
• Q.46 · 2 marks · MSQ · Decidability: Which Turing machine problems are undecidable (key: A,B,C)
• Q.47 · 2 marks · MSQ · Regular Languages: Regularity and context-freeness of two languages with repeated parts (key: A,B,C)
• Q.48 · 2 marks · MSQ · Context-Free Languages: False statements about context-free and deterministic CF languages (key: B,C,D)

Paper: official PDF · GATE CS 2022 page

GATE CS 2021 (set 1)

• Q.1 · 1 mark · MCQ · Context-Free Languages: Which combination of a regular and a CFL may not be context-free (key: C)
• Q.12 · 1 mark · MSQ · Decidability: Which DFA/DPDA/PDA language properties are not recursive (key: D)
• Q.38 · 2 marks · MCQ · Finite Automata: DFA accepting binary strings ending in 011 (key: D)
• Q.39 · 2 marks · MCQ · Decidability: Decidability of Turing machines running beyond a step count (key: A)
• Q.51 · 2 marks · NAT · Pushdown Automata: Number of length-100 strings accepted by a given PDA (key: 50)

Paper: official PDF · GATE CS 2021 page

GATE CS 2020

• Q.7 · 1 mark · MCQ · Regular Languages: Regular expression for binary strings with an odd number of 1s (key: MTA)
• Q.8 · 1 mark · MCQ · Regular Languages: Closure properties of regular languages under union (key: D)
• Q.10 · 1 mark · MCQ · Context-Free Languages: Determinism and LL(k) status of a given language (key: C)
• Q.26 · 2 marks · MCQ · Decidability: Which Turing-machine languages are undecidable (key: A)
• Q.32 · 2 marks · MCQ · Context-Free Languages: Classify two languages as regular or context-free (key: A)
• Q.51 · 2 marks · NAT · Finite Automata: Minimum DFA states for a divisibility condition on a's (key: 6)

Paper: official PDF · GATE CS 2020 page

GATE CS 2019

• Q.7 · 1 mark · MCQ · Regular Languages: Which operation on a regular language gives a non-regular one (key: B)
• Q.15 · 1 mark · MCQ · Regular Languages: Valid pumping length for a given regular language (key: D)
• Q.31 · 2 marks · MCQ · Context-Free Languages: Identify the language that is not context-free (key: C)
• Q.34 · 2 marks · MCQ · Decidability: Which sets of languages or programs are uncountable (key: B)

Paper: official PDF · GATE CS 2019 page

GATE CS 2018

• Q.6 · 1 mark · MCQ · Finite Automata: Bound on minimal DFA states for an n-state NFA (key: D)
• Q.7 · 1 mark · MCQ · Decidability: Closure and countability properties of RE languages (key: B)
• Q.35 · 2 marks · MCQ · Context-Free Languages: Classify languages over a,b,c,d as regular or context-free (key: B)
• Q.36 · 2 marks · MCQ · Decidability: Which grammar and machine problems are decidable (key: D)
• Q.52 · 2 marks · NAT · Regular Languages: Order of a given language (key: 2)

Paper: official PDF · GATE CS 2018 page

GATE CS 2017 (set 1)

• Q.10 · 1 mark · MCQ · Context-Free Languages: Language generated by a context-free grammar (key: B)
• Q.22 · 1 mark · NAT · Finite Automata: Minimum DFA states for a regular expression (key: 4.0)
• Q.34 · 2 marks · MCQ · Context-Free Languages: Which string a given grammar cannot generate (key: D)
• Q.37 · 2 marks · MCQ · Context-Free Languages: Nature of the intersection of two CFG languages (key: B)
• Q.38 · 2 marks · MCQ · Context-Free Languages: Which unions and intersections of languages are context-free (key: A)
• Q.39 · 2 marks · MCQ · Decidability: Computability of a function via a Turing machine construction (key: A)

Paper: official PDF · GATE CS 2017 page

GATE CS 2016 (set 1)

• Q.16 · 1 mark · MCQ · Context-Free Languages: Language generated by a simple right-linear grammar (key: D)
• Q.17 · 1 mark · MCQ · Decidability: Which problems on NFAs and CFGs are undecidable (key: C)
• Q.18 · 1 mark · MCQ · Regular Languages: Regex for binary strings with both 00 and 11 as substrings (key: B)
• Q.42 · 2 marks · MCQ · Context-Free Languages: Languages generated by two context-free grammars (key: D)
• Q.43 · 2 marks · MCQ · Pushdown Automata: Language accepted by a given PDA transition diagram (key: D)
• Q.44 · 2 marks · MCQ · Decidability: Implications of reductions between recursive and RE languages (key: C)

Paper: official PDF · GATE CS 2016 page

Other GATE CS subjects

• General Aptitude
• Engineering Mathematics
• Discrete Mathematics
• Digital Logic
• Computer Organization & Architecture
• Programming & Data Structures
• Algorithms
• Compiler Design
• Operating Systems
• Databases (DBMS)
• Computer Networks

FAQ

How many marks does Theory of Computation carry in GATE CS?

Across the official GATE CS papers from 2016–2026 (one set per year), Theory of Computation carried 7.8 marks a year on average, from 5 in 2026 to 10 in 2017.

Which Theory of Computation topics repeat most in GATE CS?

By the number of years they appeared in: Context-Free Languages, Regular Languages, Finite Automata. The concept table on this page lists every concept with its question count and years.

Are these the official GATE CS Theory of Computation questions?

Yes. Each question comes from the official GATE CS question paper for that year, and the key, marks and question type come from the official answer key. Summaries are ours; open the official PDF for the full question.

What question types does Theory of Computation use in GATE CS?

Of 54 questions: 34 MCQ, 13 MSQ and 7 NAT. MSQ only appears from 2021 onwards. 32 of the 54 questions carry 2 marks.