Theory of Computation
“Master minimal DFAs, Pumping Lemmas, Pushdown Automata, Turing Machine proofs, Chomsky hierarchy, and Rice's theorem.”
A rigorous, mathematically formal study notebook covering automata theory, formal languages, grammars, computability, and decidability: Deterministic and Non-deterministic Finite Automata (DFA/NFA), Myhill-Nerode minimization, Arden's theorem, Pumping Lemmas for Regular and Context-Free languages, DPDA vs NPDA power asymmetry, DCFL and CFL closure properties, CYK algorithm, Turing Machine formal models, Recursive vs Recursively Enumerable languages, Halting problem diagonalization proofs, Rice's theorem, Post Correspondence Problem (PCP), and the complete 4-tier Chomsky hierarchy for undergraduate excellence and top-rank GATE CS/IT performance.
Structured Notes & Exam Lens
A · B.Tech Structured Study Sequence
5 Sections · Full CurriculumFinite Automata, DFA Minimization & State Equivalence
Formal 5-tuple definitions of DFA, NFA, and epsilon-NFA, subset construction powerset algorithm, modulo state counting, and Myhill-Nerode table-filling DFA minimization.
5-tuple formalisms, trap states, subset powerset construction, and minimal state proofs.
Arden's formula R = Q + RP => R = QP*, state elimination method, and Thompson's construction.
Regular Language Properties & Pumping Lemma
Non-regularity proofs via the Pumping Lemma adversarial game, comprehensive closure property matrices, and decision property algorithms for regular languages.
Adversarial pumping game, s = xyz, and complete closure property proofs.
Emptiness, finiteness, membership, and equivalence decision procedures for regular sets.
Context-Free Grammars, Ambiguity & Pushdown Automata
Derivations, parse trees, grammar ambiguity, Chomsky Normal Form (CNF), DPDA vs NPDA, DCFL vs CFL, and acceptance by final state vs empty stack.
Parse tree multiplicity, inherent ambiguity, CNF 2n-1 steps, and CYK parsing.
Stack transitions, DPDA strictly less powerful than NPDA, and DCFL vs CFL.
CFL Pumping Lemma & Decision Algorithms
Pumping lemma for context-free languages (uvxyz), proving non-CFL languages, and decision properties of context-free languages.
s = uvxyz decomposition, proving a^n b^n c^n is not CFL, and undecidable CFG problems.
Turing Machines, Computability & Rice's Theorem
Turing machines, Recursive vs Recursively Enumerable sets, Halting problem proof by diagonalization, mapping reductions, Post Correspondence Problem, and Rice's Theorem.
Recursive vs RE languages, Halting problem proof by diagonalization, and Rice's Theorem.
Reductions A <=_m B, Post Correspondence Problem (PCP), and the complete 4-tier Chomsky hierarchy.
B · GATE 2027 Syllabus Scope
Official syllabus scope and related lesson coverage; topics outside the syllabus are marked as enrichment.
- •Regular expressions and finite automata: DFA, NFA, epsilon-NFA, equivalence, state minimization, Arden's theorem
- •Regular languages: Pumping lemma, closure properties, decision properties (emptiness, finiteness, equivalence)
- •Context-free grammars and languages: Derivations, parse trees, ambiguity, Chomsky Normal Form (CNF), CYK algorithm
- •Pushdown automata: DPDA, NPDA, equivalence of acceptance modes, DCFL vs CFL closure properties
- •Turing machines and computability: Turing machine model, multi-tape equivalence, Recursive and Recursively Enumerable languages
- •Undecidability: Halting problem, diagonalization, Post Correspondence Problem (PCP), Rice's theorem, Chomsky hierarchy
Interactive Labs & Verified PYQs
Revision & Rapid Review Sheets
Authoritative Textbooks & Video Lectures
All notes in this notebook cross-reference standard academic literature. We do not pretend student notes substitute for classical texts — they guide you through them.
Curated lectures from verified educators (Gate Smashers, Neso Academy, Knowledge Gate, and MIT OCW) selected specifically for difficult concept visualizations.
These notes are open and maintained together.
Found a factual mistake? Have a clearer explanation or mental model? Created a useful diagram or worked out a tricky GATE question? Help make this notebook better for every student who opens it next.