Theory of Computation

Finite automata are abstract machines with finite states that recognise regular languages. DFA, NFA, and ε-NFA are all equivalent in power and are the foundation of lexical analysis.

CFGs describe context-free languages (CFL) using production rules. PDAs are the automata equivalent. CFLs are strictly more powerful than regular languages and are used to describe programming language syntax.

Turing machines are the most powerful computational model. Understanding decidability, recognisability, and reducibility is critical for GATE questions on what computers can and cannot solve.

P vs NP is the central open question in computer science. GATE tests whether problems are in P, NP, or NP-complete, and how to prove NP-completeness via polynomial reductions.