GATE CS - THEORY OF COMPUTATION:Introduction to Theory of Computation
Mastering introduction to theory of computation concepts and implementation.
Theory of Computation for GATE CS
Theory of Computation (ToC) asks a precise question: which problems can a machine solve, and with what resources? In GATE CS it usually contributes about 6–9 marks. Questions are short but unforgiving — one wrong closure property or pumping-lemma setup costs the whole mark.
This chapter is the map. Later chapters fill in DFA/NFA, CFGs/PDAs, Turing machines, and complexity.
The three models you must keep distinct
| Model | Extra memory | Languages (Chomsky) | Typical GATE ask |
|---|---|---|---|
| Finite automaton (DFA/NFA) | None | Regular (Type 3) | Construct / minimize / regex ↔ FA |
| Pushdown automaton | One stack | Context-free (Type 2) | CFG ↔ PDA, membership |
| Turing machine | Unlimited tape | Recursively enumerable (Type 0) | Decidable vs RE, reductions |
A language is a set of strings over a finite alphabet Σ. ε is the empty string; Σ* is every finite string over Σ.
Grammars in one line each
A grammar G = (V, T, P, S) generates a language: start from S, rewrite using productions in P until only terminals from T remain.
Chomsky hierarchy (strict inclusions for the standard definitions):
- Type 3 — Regular: productions like
A → aBorA → a(right-linear form). FA recognizes them. - Type 2 — Context-free:
A → αwith A a single non-terminal. PDA recognizes them. - Type 1 — Context-sensitive:
αAβ → αγβwith |γ| ≥ 1 (non-contracting). Linear-bounded automaton. - Type 0 — Unrestricted: any
α → β. Turing machine.
Exam trap: “context-sensitive” is rarely tested in depth; GATE leans on Types 2–3 plus decidability on TMs. Do not spend weeks on Type 1 machinery.
What “decidable” means in GATE language
- Decidable: a TM that always halts with yes/no for every input.
- Recognizable (RE): a TM that accepts yes-instances (may loop on no).
- Regular ⊂ CFL ⊂ CSL ⊂ recursive ⊂ RE (remember the picture; questions love “which is not closed under X?”).
How to study this subject
- Build small DFAs by hand until conversion from regex is muscle memory.
- Memorize closure tables (union, concat, star, complement, intersection) for regular and CFL — these are free marks when you know them cold.
- Practise one pumping-lemma disproof template; do not try to “prove” regularity with pumping.
Next: Finite Automata and Regular Languages, or browse all subjects from the GATE hub.