Theory of Computation: notes and questions
For CSE/IT students
Notes for each topic, a formula sheet, practice questions and 48 past GATE questions from 10 papers (2018–2026), 44 of them solved step by step.
- previous-year questions
- 48previous-year questions
- solved step by step
- 44solved step by step
- GATE papers, 2018–2026
- 10GATE papers, 2018–2026
- topics with notes
- 5topics with notes
Foundation
Learn the subject one topic at a time. Each topic has notes, the key formulas and practice questions.
Topic notes and formulas
Notes on every topic, with the key formulas and practice.
Regular expressions and finite automata
Regular languages are exactly the languages that DFAs, NFAs, epsilon-NFAs and regular expressions describe.
5 practice questions
Regular languages: closure properties and the pumping lemma
Regular languages are closed under many operations, so you can often prove a language regular or non-regular without building a machine.
6 practice questions
Context-free grammars and push-down automata
A context-free grammar generates strings by rewriting variables, and a push-down automaton (a finite automaton with a stack) accepts exactly the same languages.
5 practice questions
Context-free languages: closure properties and the pumping lemma
Context-free languages are closed under some operations (union, concatenation, star, reversal, homomorphism, substitution, inverse homomorphism, intersection with a regular language) and not under others (intersection, complement).
5 practice questions
Turing machines, decidability and undecidability
A Turing machine is the most general model of computation in the GATE syllabus: it defines which languages can be recognised (recursively enumerable) or decided (recursive) by any algorithm.
5 practice questions
Theory of Computation formulas by topic
GATE
Past GATE questions on Theory of Computation by topic and year, the full papers, practice and the GATE syllabus.
48 questions, by topic and year
How many questions each topic had in the CS papers of each year. This shows what was asked, not what will be asked. We placed each question under a topic ourselves; the exam paper does not label topics.
| Topic | 2018 | 2020 | 2022 | 2023 | 2024 | 2025 | 2026 | Total |
|---|---|---|---|---|---|---|---|---|
| Finite automata | 2 | 2 | 1 | 3 | 5 | 3 | 2 | 18 |
| Regular languages | · | 1 | · | · | 1 | 2 | 1 | 5 |
| CFG & PDA | · | · | · | 2 | 2 | 2 | 3 | 9 |
| Context-free languages | 1 | 2 | 2 | · | · | 2 | 1 | 8 |
| Turing machines | 2 | 1 | 2 | 1 | · | 1 | 1 | 8 |
Solved papers
GATE CSE question papers with solutions: 2026 Set 1, 2026 Set 2, 2025 Set 1, 2025 Set 2, 2024 Set 1, 2024 Set 2, 2023, 2022, 2020, 2018
GATE 2023 comes from IIT Kanpur's own copy of the paper and its answer key, which numbers the CS questions Q.11 to Q.65. For 2024, 2025 and 2026 both sessions (CS1 and CS2) are included.
26 practice questions
The GATE syllabus for Theory of Computation, paper by paper
From the GATE 2027 syllabus PDF: CS Section 6, “Theory of Computation”. Parsing is listed under Section 7, Compiler Design, not here.
Show the GATE CS wordingHide the GATE CS wording
Regular expressions and finite automata. Context-free grammars and push-down automata. Regular and context-free languages, pumping lemma. Turing machines and undecidability.
Preparing in Kolkata? See IAE Academy’s GATE CS coaching.
Other exams
13 questions on Theory of Computation from ISRO's Scientist/Engineer written test (ISRO CS 2025, ISRO CS 2023), by topic. They are not counted in the GATE numbers on this page.
IF YOU WOULD RATHER TALK IT THROUGH