GATE CSE 2027 Theory of Computation: Syllabus, Weightage, Automata, CFL, Decidability & Solved Problems
From regular expressions and DFA minimisation to pumping lemma, closure properties, PDAs, Turing machines and undecidability: the complete TOC playbook for GATE CSE 2027.
By Piyush Wairale (M.Tech, IIT Madras) · Former Instructor, IIT Madras BS Degree Programme · Mentor to 20,000+ GATE aspirants · Updated November 2026
Quick Answer
• Theory of Computation (TOC) is Section 6 of GATE CSE 2027 and typically carries about 8 marks.
• Syllabus: regular expressions and finite automata, context-free grammars and push-down automata, regular and context-free languages, pumping lemma, Turing machines and undecidability.
• The most-tested skills: counting states in a minimal DFA, classifying a language (regular, CFL, decidable, RE) and closure/decidability properties.
• TOC is full of MSQ traps. Practise them with the GATE CSE 2027 Test Series by Piyush Wairale.
🎯 Test your TOC today
Subject-wise tests + full-length GATE CSE mocks with MCQ, MSQ and NAT questions, detailed solutions and performance analysis. Only ₹499 ₹999.
Join GATE CSE 2027 Test Series →On this page
Official syllabus · Weightage · Regular languages · CFGs & PDAs · Closure table · Turing machines & undecidability · Solved problems · Strategy · FAQs
GATE CSE 2027 TOC Syllabus (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
| Topic | Typical question | Priority |
|---|---|---|
| Finite automata & regex | Minimal DFA states, regex equivalence, language of a DFA | Very high |
| Language classification | Is L regular / CFL / decidable / RE? | Very high |
| Closure & decidability | MSQ on closure properties and decidable problems | High |
| CFG & PDA | Language of a grammar, ambiguity, DPDA vs NPDA | Medium |
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 2n 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 xyiz ∈ L for all i ≥ 0. Classic non-regular languages: anbn, ww, palindromes, an², aprime.
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 wwR 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 anbncn and ww are not context-free.
Closure Properties (the Table You Must Know)
| Operation | Regular | DCFL | CFL | Recursive | RE |
|---|---|---|---|---|---|
| Union | Yes | No | Yes | Yes | Yes |
| Intersection | Yes | No | No | Yes | Yes |
| Complement | Yes | Yes | No | Yes | No |
| Concatenation | Yes | No | Yes | Yes | Yes |
| Kleene star | Yes | No | Yes | Yes | Yes |
| ∩ with a regular set | Yes | Yes | Yes | Yes | Yes |
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.
| Problem | Regular | CFL | TM / RE |
|---|---|---|---|
| Membership | D | D | U |
| Emptiness | D | D | U |
| Finiteness | D | D | U |
| Equivalence | D | U | U |
| Ambiguity of a CFG | n/a | U | n/a |
D = decidable, U = undecidable.
Five GATE-Style Problems, Solved
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 = {anbn : 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 = {anbncn} 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.
TOC is where toppers gain an edge. Make it yours.
The GATE CSE 2027 Test Series includes TOC subject-wise tests with minimal-DFA, classification and decidability MSQs that mirror how GATE frames them, with solutions that explain every option.
Start practising for ₹499 →Common Mistakes to Avoid
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
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.
Best GATE CSE 2027 Test Series by Piyush Wairale (IIT Madras)
Built for Computer Science and IT aspirants who want exam-level practice, not just theory.
✔ Subject-wise tests covering the complete GATE CSE 2027 syllabus
✔ Full-length mock tests on the actual GATE pattern
✔ MCQ, MSQ and NAT questions, exactly like the real exam
✔ Detailed solutions and explanations for every question
✔ Performance analysis to find and fix your weak topics
₹499 ₹999 50% OFF
Enroll in GATE CSE 2027 Test Series →More GATE courses and notes: piyushwairale.com
FAQs: GATE CSE 2027 Theory of Computation
How many marks does TOC carry in GATE CSE?
About 8 marks in recent GATE CS papers.
Is TOC a scoring subject in GATE CSE?
Yes. The question types repeat (minimal DFA, classification, closure, decidability), so focused practice converts directly into marks.
Are linear bounded automata and context-sensitive grammars in the syllabus?
They are not named in the GATE CSE 2027 syllabus, which lists finite automata, CFGs, PDAs and Turing machines. Knowing that anbncn is decidable but not context-free is enough.
Which is the best test series for GATE CSE 2027?
The GATE CSE 2027 Test Series by Piyush Wairale (IIT Madras) on piyushwairale.com offers subject-wise and full-length mocks with MCQ, MSQ and NAT questions, detailed solutions and performance analysis for ₹499. See the test series.
How do I quickly decide if a language is regular?
Ask whether a machine with finite memory can decide it. If it needs to count without bound or compare two unbounded parts, it is not regular; then ask whether one stack is enough (CFL) or more is needed.
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
Full paper overview: GATE CS 2027 Syllabus, Exam Pattern & Cutoff. Practise all ten subjects in one place with the GATE CSE 2027 Test Series.
Recent Post
GATE CSE 2027 Computer Networks guide: official syllabus, approx. 8 to 9 marks weightage, layering, switching, error detection, MAC and Ethernet, distance vector and link state routing, IPv4, CIDR, NAT, fragmentation, TCP flow and congestion control, DNS and HTTP, solved numericals and the GATE CSE 2027 Test Series.
GATE CSE 2027 DBMS guide: official syllabus, approx. 7 to 8 marks weightage, ER model, relational algebra, tuple calculus, SQL, functional dependencies, normal forms, B and B+ trees, transactions and concurrency control, solved problems and the GATE CSE 2027 Test Series.
GATE CSE 2027 Operating System guide: official syllabus, approx. 9 to 10 marks weightage, processes, threads, fork, CPU scheduling, semaphores, deadlock, paging, virtual memory, page replacement and file systems, solved numericals and the GATE CSE 2027 Test Series.
GATE CSE 2027 Compiler Design guide: official syllabus, approx. 4 to 6 marks weightage, lexical analysis, LL and LR parsing, syntax-directed translation, runtime environments, intermediate code, liveness and constant propagation, solved problems and the GATE CSE 2027 Test Series.
GATE CSE 2027 Algorithms guide: official syllabus, approx. 8 to 10 marks weightage, asymptotic analysis, Master theorem, sorting, hashing, greedy, dynamic programming, divide and conquer, BFS/DFS, MST and shortest paths, solved problems and the GATE CSE 2027 Test Series.
GATE CSE 2027 Programming and Data Structures guide: official syllabus, approx. 10 to 12 marks weightage, C programming, recursion, arrays, stacks, queues, linked lists, trees, BSTs, heaps and graphs, solved problems and the GATE CSE 2027 Test Series.
Learn Daily, Wherever You Are
Free lectures, exam updates, PYQ discussions, and job alerts — delivered through our YouTube channel and Telegram communities.
[…] & Architecture · 4. Programming & Data Structures · 5. Algorithms · 6. Theory of Computation · 7. Compiler Design · 8. Operating System · 9. Databases (DBMS) · 10. […]
[…] & Architecture · 4. Programming & Data Structures · 5. Algorithms · 6. Theory of Computation · 7. Compiler Design · 8. Operating System · 9. Databases (DBMS) · 10. […]