By Piyush Wairale (M.Tech, IIT Madras) · Former Instructor, IIT Madras BS Degree Programme · Mentor to 20,000+ GATE aspirants · Updated November 2026

GATE CSE Theory of Computation Syllabus 2027 (Official, IIT Madras)

Section 6 of the CS paper: Regular expressions and finite automata. Context-free grammars and push-down automata. Regular and context-free languages, pumping lemma. Turing machines and undecidability.

See all sections in the GATE CS 2027 syllabus and exam pattern guide.

Topic-wise Weightage and Priority (GATE CSE Theory of Computation)

Regular Expressions and Finite Automata

DFA, NFA, ε-NFA and regular expressions all describe exactly the regular languages. Subset construction turns an n-state NFA into a DFA with up to 2ⁿ states. Minimise a DFA by removing unreachable states and merging equivalent states (table-filling or partition refinement); the Myhill-Nerode theorem says the number of states in the minimal DFA equals the number of equivalence classes of the language. Useful counts: strings where |w| mod n = k need n states; strings ending with a specific substring of length k usually need k + 1 states; strings containing a substring of length k need k + 1 states.

To show a language is not regular, use the pumping lemma: any regular L has a p such that every string of length ≥ p splits as xyz with |xy| ≤ p, |y| ≥ 1 and xyⁱz ∈ L for all i ≥ 0. Classic non-regular languages: aⁿbⁿ, ww, palindromes, a^n², a^prime.

Context-Free Grammars and Push-Down Automata

CFGs generate the context-free languages, which NPDAs accept. DPDAs accept the deterministic CFLs, a strict subset (palindromes ww^R are CFL but not DCFL). A grammar is ambiguous if some string has two leftmost derivations (or two parse trees); some CFLs are inherently ambiguous. Use the CFL pumping lemma (uvxyz) to show languages like aⁿbⁿcⁿ and ww are not context-free.

Closure Properties (the Table You Must Know)

Turing Machines and Undecidability

A language is recursive (decidable) if a TM always halts and decides it, and recursively enumerable (RE) if a TM accepts every string in it (but may loop on others). If both L and its complement are RE, L is recursive. The halting problem is RE but undecidable, and its complement is not RE. Rice’s theorem: every non-trivial property of the language recognised by a TM is undecidable.

D = decidable, U = undecidable.

Five GATE-Style Problems, Solved (GATE CSE Theory of Computation)

Q1 (NAT). Minimum states in a DFA over {a, b} accepting strings where the number of a’s is divisible by 3?
Solution: Track count mod 3: 3 states.

Q2 (NAT). Minimum states in a DFA over {a, b} accepting strings ending with ab?
Solution: States for “no progress”, “seen a”, “seen ab”: 3.

Q3 (MCQ). L = {aⁿbⁿ : n ≥ 0} is: (a) regular (b) CFL but not regular (c) not CFL (d) not decidable.
Solution: (b). A PDA can match counts with a stack; a DFA cannot (pumping lemma).

Q4 (MCQ). L = {aⁿbⁿcⁿ} is:
Solution: Not context-free but decidable (it is context-sensitive; a TM checks the three counts and always halts).

Q5 (MSQ). Which are decidable? (A) Emptiness of a CFG (B) Equivalence of two CFGs (C) Equivalence of two DFAs (D) Whether a TM halts on blank input.
Solution: A and C. B is undecidable, and D is a form of the halting problem.

Common Mistakes to Avoid (GATE CSE Theory of Computation)

Forgetting the dead (trap) state when counting DFA states for a complete DFA.

Using the pumping lemma to prove a language IS regular: it can only prove non-regularity.

Assuming CFLs are closed under intersection or complement.

Confusing “every finite language is regular” (true) with “every subset of a regular language is regular” (false).

Mixing up RE and recursive in decidability MSQs.

4-Week Preparation Strategy (GATE CSE Theory of Computation)

Week 1: DFA, NFA, regex, minimisation (solve 40+ DFA design questions). Week 2: Pumping lemma, closure properties, CFGs and PDAs. Week 3: Turing machines, decidability, Rice’s theorem. Week 4: 10 years of GATE CS TOC questions and the TOC tests in the GATE CSE 2027 Test Series. TOC leads naturally into Compiler Design.

FAQs: GATE CSE Theory of Computation 2027

GATE CSE 2027: All Subject-wise Guides

1. Engineering Mathematics · 2. Digital Logic · 3. Computer Organization & Architecture · 4. Programming & Data Structures · 5. Algorithms · 6. Theory of Computation · 7. Compiler Design · 8. Operating System · 9. Databases (DBMS) · 10. Computer Networks

That completes this GATE CSE Theory of Computation guide. Full paper overview: GATE CS 2027 Syllabus, Exam Pattern & Cutoff. Practise all ten subjects in one place with the GATE CSE 2027 Test Series.