Theory of Computation (TOC) is worth about 7 marks per GATE CS paper, or roughly 7.1% of the 100-mark paper, and it has been rising. We counted every TOC question in the official GATE CS papers from 2014 to 2026. TOC averaged 7.1 marks per paper, ranged from 3 to 10, and averaged 7.4 marks from 2021. It is the most multiple-select (MSQ)-heavy subject in the paper: since 2021, 49% of TOC marks have come from MSQs, which give no partial credit. Context-free languages are now the largest topic. This guide covers the official 2027 syllabus, topic-by-topic numbers, five worked questions from past papers and a study order based on that data.
How we counted: we classified all 1,495 GATE CS questions from 2014 to 2026 by subject and topic, using the official papers as reproduced on Success Tracker's GATE CS PYQ archive. The 2015 Set 1 paper on that archive has duplicated questions where some TOC questions should be, so we left that paper out of the TOC figures. All TOC averages here use the other 22 papers. Confirm the syllabus on the official GATE 2027 syllabus page (IIT Madras).
GATE CS 2027 Theory of Computation Syllabus
Theory of Computation is Section 6 of the official GATE 2027 CS syllabus. The official text lists:
- Regular expressions and finite automata
- Context-free grammars and push-down automata
- Regular and context-free languages, pumping lemma
- Turing machines and undecidability
This is identical to the GATE 2026 CS syllabus. Complexity classes (P, NP) are not listed. Linear bounded automata and context-sensitive grammars are not named either, though basic facts about the language hierarchy still help with closure questions. For the full CS syllabus, see our GATE CS syllabus page.
How Many Marks Does TOC Carry in GATE CS?
The official question paper pattern fixes marks only for General Aptitude (15) and Engineering Mathematics (13). This is what TOC carried in each paper:
| Year | Marks per paper (set-wise) | % of the 100-mark paper | Questions |
|---|---|---|---|
| 2014 | 6 / 6 / 5 | 6% / 6% / 5% | 4 / 4 / 3 |
| 2015 | — / 6 / 3 | — / 6% / 3% | — / 3 / 2 |
| 2016 | 9 / 9 | 9% / 9% | 6 / 6 |
| 2017 | 10 / 9 | 10% / 9% | 6 / 6 |
| 2018 | 8 | 8% | 5 |
| 2019 | 4 | 4% | 3 |
| 2020 | 8 | 8% | 5 |
| 2021 | 8 / 9 | 8% / 9% | 5 / 6 |
| 2022 | 8 | 8% | 5 |
| 2023 | 8 | 8% | 5 |
| 2024 | 7 / 7 | 7% / 7% | 4 / 4 |
| 2025 | 8 / 7 | 8% / 7% | 5 / 5 |
| 2026 | 6 / 6 | 6% / 6% | 4 / 4 |
| Average (22 papers) | 7.1 | 7.1% (range 3–10%) | 4.5 |
What this means: from 2020 onwards, TOC has carried 6 to 9 marks in every paper. It is one of the most consistent subjects, which makes it a dependable source of marks once you are fluent in it. For how TOC compares with other subjects, see our GATE CSE subject-wise weightage analysis.
Topic-Wise Weightage: Where TOC Marks Come From
We grouped the 100 TOC questions by syllabus heading, with the average marks per paper across all 22 papers:
| Topic | Questions | Total marks | Avg marks per paper (22 papers) | Last asked |
|---|---|---|---|---|
| Context-free grammars, PDAs and CFLs | 46 | 74 | 3.4 | 2026 |
| Regular expressions, finite automata and regular languages | 43 | 64 | 2.9 | 2026 |
| Turing machines and undecidability | 11 | 19 | 0.9 | 2026 |
Looking at individual topics, the most-asked across all papers were context-free grammars and ambiguity (12 questions, 19 marks), closure properties of CFLs (12 questions, 17 marks), DFA design and counting (11 questions, 18 marks), and closure properties of regular languages and regular expressions (8 and 7 questions).
Three patterns stand out:
- Context-free languages lead and are growing. At about 3.7 marks per paper since 2021, CFLs are now the biggest TOC topic. Recent questions ask whether a grammar is ambiguous, whether a language with counting constraints is context-free (worked example 1), and what is preserved under union, intersection and complement.
- Regular languages are close behind. At about 3.2 marks per paper, they are mostly DFA and NFA reasoning, minimisation, and "is this language regular" questions.
- Undecidability has shrunk from 1.2 to 0.5 marks per paper, but it still appeared in 2026. The questions are almost always "which of these are decidable", answered with Rice's theorem plus a few standard decidable cases.
Question Types: TOC Is an MSQ Subject
From 2021 to 2026, the 47 TOC questions split into 23 MSQs, 17 MCQs and 7 NATs. By marks, MSQs carried 36 of 74 (49%), the highest MSQ share of any subject in our count. An MSQ has no negative marking but gives credit only if you choose exactly the right set of options (official marking rules). For TOC this means:
- Treat every option as its own true-or-false question.
- Have a standard counterexample ready for each closure property, such as anbncn for "not context-free" and anbn for "not regular".
- "Always true" means one counterexample is enough to rule an option out (worked example 4).
Topic by Topic: What GATE Asks and How to Prepare
1. Context-Free Grammars, PDAs and CFLs
What gets asked: whether a grammar is ambiguous, the language a grammar generates, whether languages with index constraints are context-free, closure and decision properties of CFLs, the pumping lemma for CFLs, and PDA behaviour.
How to prepare: learn the matching rule. Constraints that nest (a matched with d, and b matched with c, inside it) are context-free. Constraints that cross (a matched with c, and b matched with d) are not. Sums that a single counter can track are context-free. Learn the closure table: CFLs are closed under union, concatenation, star and intersection with a regular language, but not under intersection or complement.
Recent PYQs: grammar ambiguity (2026, MSQ), which grammars are ambiguous (2026, MSQ), index constraints and CFLs (2026, MSQ).
2. Regular Expressions, Finite Automata and Regular Languages
What gets asked: the minimum number of DFA states, NFA-to-DFA conversion bounds, equivalence of regular expressions, closure properties, and whether a language is regular.
How to prepare: practise building minimal DFAs for counting conditions, such as "number of a's divisible by 3" or "ends with ab". Know that an n-state NFA always has an equivalent DFA with at most 2n states, and that the minimal DFA may be much smaller (worked example 2). To show a language is not regular, use the pumping lemma or Myhill–Nerode.
Recent PYQs: 6-state NFA to DFA (2026, MSQ), comparing two automata (2026, MSQ), closure with intersection (2026, MSQ).
3. Turing Machines and Undecidability
What gets asked: decidable versus undecidable problems, Rice's theorem, recursive versus recursively enumerable languages, and their closure properties.
How to prepare: Rice's theorem settles any non-trivial question about the language of a Turing machine: it is undecidable. Questions about a machine's behaviour within a fixed number of steps are decidable (worked example 3). Learn the standard facts. Recursive languages are closed under complement. RE languages are not. If both L and its complement are RE, then L is recursive.
Recent PYQs: what "decides" means (2026), recursive and RE languages (2021), undecidable languages (2020).
Worked Examples from Official GATE CS Papers
Each answer below matches the official answer key, as reproduced on the linked question page.
Example 1: Which constraints keep it context-free? (GATE CS 2026 Set 2, Q48, 2 marks, MSQ)
Question: L = {aibjckdℓ}. Which constraints make L context-free: (A) i + k = j + ℓ, (B) i = k and j = ℓ, (C) i = ℓ and j = k, (D) i + j = k + ℓ?
Solution: (D) is context-free: push for a and b, then pop for c and d. (C) nests bjcj inside ai…di, so it is context-free. (A) needs only one counter that can go negative, since i − j + k − ℓ = 0. A PDA can track it with two stack symbols, so it is context-free. (B) has crossing dependencies (a with c, b with d), which is the classic non-context-free pattern. The answer is A, C and D. Practise this question.
Example 2: NFA to DFA bounds (GATE CS 2025 Set 1, Q28, 1 mark, MSQ)
Question: L is accepted by an n-state NFA. Which statements are FALSE? (A) L may have an NFA with fewer than n states. (B) L may have a DFA with fewer than n states. (C) Some DFA with at most 2n states accepts L. (D) Every DFA for L has more than 2n states.
Solution: (A) and (B) are possible, because the given NFA need not be minimal. (C) is the subset construction. (D) contradicts (C), so it is false. The answer is D only. Practise this question.
Example 3: Which problems are undecidable? (GATE CS 2022, Q46, 2 marks, MSQ)
Question: which are undecidable? (A) Is L(M1) = L(M2)? (B) Is L(M) regular? (C) Does M accept all strings? (D) Does M take more than 1073 steps on every string?
Solution: (A), (B) and (C) are non-trivial properties of the language M accepts, so they are undecidable by Rice's theorem and the standard equivalence and totality results. (D) is about a fixed step bound. In 1073 steps, M can only read the first 1073 symbols, so checking finitely many inputs settles it, and it is decidable. The answer is A, B and C. Practise this question.
Example 4: Closure with a counterexample (GATE CS 2026 Set 1, Q51, 2 marks, MSQ)
Question: L1 ∩ L2 and L2 are regular. Which statements are always true? (A) L1 is regular. (B) L1 ∪ L2 is regular. (C) The complement of L2 is context-free. (D) L1 is context-free.
Solution: regular languages are closed under complement, and every regular language is context-free, so (C) always holds. For the others, take L2 = ∅ and L1 = {anbncn}. Both conditions are met, yet L1 is not context-free, and L1 ∪ L2 = L1 is not regular. The answer is C only. Practise this question.
Example 5: What "decides" means (GATE CS 2026 Set 2, Q13, 1 mark)
Question: which statement is equivalent to "M decides L ⊆ {0,1}*"?
Solution: to decide L, M must halt on every input, accepting the strings in L and rejecting all the others. "Accepts all of L" alone only means M recognises L, and it may loop on other inputs. The answer is M accepts all strings in L and rejects all strings not in L. Practise this question.
Study Order and Time Plan
TOC takes roughly 4 to 5 weeks at 2 hours a day. Study Discrete Mathematics first, since sets, relations and logic come up throughout TOC.
- Finite automata (6–7 days): DFA and NFA design, subset construction and minimisation.
- Regular expressions and regular languages (5 days): equivalence, closure and the pumping lemma.
- Context-free grammars and PDAs (6–7 days): ambiguity, derivations, and nested versus crossing constraints.
- CFL properties (4 days): the closure and decision tables, and the CFL pumping lemma.
- Turing machines and undecidability (3–4 days): Rice's theorem, recursive versus RE languages, and standard decidable problems.
- PYQ sweep (3–4 days): all 100 TOC questions from 2014 to 2026 on the GATE CS PYQ archive.
For where TOC fits among all the subjects, see the GATE CSE 2027 month-by-month study plan.
Best Books for GATE CS TOC
| Book | Use it for |
|---|---|
| Michael Sipser, Introduction to the Theory of Computation (3rd ed.) | The primary text: clear proofs of closure, pumping and undecidability. |
| Hopcroft, Motwani & Ullman, Introduction to Automata Theory, Languages, and Computation (3rd ed.) | A deeper treatment of grammars and PDAs. |
| Peter Linz, An Introduction to Formal Languages and Automata | Lots of worked examples and practice exercises. |
For other subjects, see our best books for GATE CSE 2027. The full course, covering all subjects with lectures and mock tests, is on the GATE CS course page.
Common Mistakes in GATE TOC
- Assuming CFLs are closed under intersection or complement. They are not, except for intersection with a regular language.
- Mixing up nested and crossing constraints when deciding whether a language is context-free (Example 1).
- Confusing "recognises" with "decides". Deciding requires halting on every input (Example 5).
- Applying Rice's theorem to questions about running time or steps. It covers only properties of the language (Example 3).
- Marking only the obvious option in an MSQ. Check every option with a counterexample.
Key Takeaways
- TOC averaged 7.1 marks per paper (7.1% of the paper) across 22 official GATE CS papers (2014–2026), and has carried 6 to 9 marks in every paper since 2020.
- Context-free languages (74 marks) and regular languages (64 marks) make up nearly all of TOC.
- MSQs carried 49% of TOC marks from 2021 to 2026, the highest MSQ share of any subject.
- Undecidability fell to about 0.5 marks per paper. Rice's theorem covers most of it.
Frequently Asked Questions
How many marks does Theory of Computation carry in GATE CS?
The official pattern does not fix marks per CS subject. Across 22 official GATE CS papers from 2014 to 2026, TOC averaged 7.1 marks per paper, which is 7.1% of the 100-mark paper, with a range of 3 to 10. It has averaged 7.4 since 2021.
Which TOC topics are most important for GATE CS 2027?
Context-free grammars and languages (about 3.7 marks per paper since 2021) and regular languages and finite automata (about 3.2). Turing machines and undecidability carry less, about 0.5 marks per paper.
Is TOC hard for GATE CS?
TOC is abstract, and Success Tracker rates 13 of its 100 questions as hard. The question patterns repeat, though: closure tables, nested versus crossing constraints, DFA minimisation and Rice's theorem. With practice, it becomes one of the most dependable subjects.
Which book is best for TOC for GATE CS?
Michael Sipser's Introduction to the Theory of Computation covers the full syllabus clearly. Add Hopcroft, Motwani and Ullman for grammars, and Linz for practice exercises.
Is P vs NP in the GATE CS TOC syllabus?
No. The official 2027 TOC syllabus lists regular expressions and finite automata, context-free grammars and PDAs, regular and context-free languages with the pumping lemma, and Turing machines and undecidability. Complexity classes are not listed.
Where can I practise GATE CS TOC PYQs?
Every GATE CS question from 2014 to 2026 is free on Success Tracker's GATE CS PYQ archive, with the official answer and a worked solution.
Next in This Series
- Discrete Mathematics for GATE CS 2027
- Compiler Design for GATE CS 2027
- Algorithms for GATE CS 2027
- GATE CSE subject-wise weightage
- GATE CS 2027 complete guide
Sources
- GATE 2027 CS Syllabus (PDF), IIT Madras: Section 6, Theory of Computation
- GATE 2026 CS Syllabus (PDF), IIT Guwahati
- GATE 2027 Question Paper Pattern, IIT Madras: marks distribution and negative marking
- Official GATE CS question papers and answer keys, 2014–2026, as reproduced on Success Tracker. Weightage figures are The ML Hub's own count, done on 25 October 2026. 2015 Set 1 is excluded for TOC (see the method note above).