TOC · about 7 to 9 marks per paper (my estimate, not an official count)

Learn Theory of Computation, with pictures you can poke.

Short concepts, every formula in one place, interactive animations, and the question types that keep repeating in past GATE papers.

Syllabus. Regular expressions and finite automata. Context-free grammars and push-down automata. Regular and context-free languages, pumping lemma. Turing machines and undecidability.

Study order

Highest yield first. Tick a topic when you are done with it.

0 of 7 topics done

What gets asked, at a glance

Most frequent question types across topics (rating is approximate).

★★★
Minimum number of states in a DFA for a language
Finite Automata (DFA, NFA, ε-NFA)
★★★
What language does this automaton accept?
Finite Automata (DFA, NFA, ε-NFA)
★★★
Is this language regular / context-free?
Regular Expressions & Regular Languages
★★★
Closure-property true/false statements
Regular Expressions & Regular Languages
★★★
Which regular expression matches the language/DFA?
Regular Expressions & Regular Languages
★★★
Is the grammar ambiguous? / which grammar is unambiguous
Context-Free Grammars & Languages
★★★
Which languages are context-free
Context-Free Grammars & Languages
★★★
CFL closure true/false
Context-Free Grammars & Languages
★★★
Language generated by a grammar
Context-Free Grammars & Languages
★★★
Which language is accepted by this PDA?
Pushdown Automata
★★★
DPDA vs NPDA
Pushdown Automata
★★★
Statement about closure of a class
Language Hierarchy & Closure Tables
★★★
Which of these languages are CFL / regular / decidable
Language Hierarchy & Closure Tables
★★★
Recursive / RE / neither for a described language
Turing Machines
★★★
Which problems are decidable?
Decidability & Undecidability
★★★
Apply reductions correctly
Decidability & Undecidability
★★★
Recursive / RE classification
Decidability & Undecidability

Importance and frequency ratings are my reading of recurring GATE CSE patterns, not an official count. Cross-check against a PYQ set before relying on them for exact marks.

Frequently asked questions

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

By my estimate about 7 to 9 marks per paper. This is an estimate from recurring patterns in past papers, not an official count, and it varies from year to year.

What topics are in Theory of Computation for GATE CSE?

Finite Automata (DFA, NFA, ε-NFA); Regular Expressions & Regular Languages; Context-Free Grammars & Languages; Pushdown Automata; Language Hierarchy & Closure Tables; Turing Machines; Decidability & Undecidability.

Which Theory of Computation topics are most important for GATE?

The highest-yield topics are Finite Automata (DFA, NFA, ε-NFA); Regular Expressions & Regular Languages; Context-Free Grammars & Languages; Pushdown Automata; Language Hierarchy & Closure Tables; Decidability & Undecidability. Importance is my estimate from recurring question patterns.

Where can I find solved GATE Theory of Computation previous year questions?

This page links to 53 previous year question entries from 2012 to 2025, each with the official answer key and a worked solution.