Theory of Computation for GATE

Theory of Computation rewards precise definitions more than any other subject here, because every question turns on a distinction that a loose statement erases. Finite automata questions come down to how many situations a machine must tell apart, which is what the Myhill-Nerode argument formalises and what makes minimisation and non-regularity proofs the same idea. Pushdown automata exist because a stack is exactly the memory that nesting requires, so recognising nesting in a language usually settles its class immediately. The pumping lemma is a game against an adversary and must be argued in the right order, which is where most marks are lost. Undecidability questions rest on self-reference making diagonalisation available, and reduction is the standard tool.