// subject deep-dive
Theory of Computation
Understand formal languages, automata theory, and the limits of computation.
📊 Average Weightage: 6–7 Marks (3–4 Questions)
Finite Automata & Regular Languages
Regular expressions, DFA, NFA, equivalence, and conversion between these formalisms.
CFG and Pushdown Automata
Grammar definitions, parse trees, and push-down automata (PDA) basics for context-free languages.
Pumping Lemma
Using the Pumping Lemma to prove languages are non-regular or non-context-free.
Turing Machines & Decidability
Definition of Turing Machines (TM), decidability, and the fundamental Halting problem (undecidability).
💡
High-Yield Topics
Finite automata, regular expressions, and context-free grammars (CFGs) are frequently tested and form the core of the TOC section.