TOC Syllabus

Topic	Subtopics / What to Cover
Introduction to TOC	Alphabets ⭐ Strings ⭐ Languages ⭐
Finite Automata	DFA ⭐ NFA ⭐ DFA vs NFA ⭐
Regular Expressions	RE basics ⭐ RE ↔ FA conversion ⭐
Regular Languages	Properties ⭐ Pumping Lemma ⭐
Closure Properties	Union ⭐ Concatenation ⭐ Kleene Star ⭐
Minimization of DFA	Equivalent states ⭐ Minimization algorithm ⭐
Context-Free Grammar	CFG basics ⭐ Derivations ⭐
Parse Trees	Leftmost derivation ⭐ Rightmost derivation ⭐
Ambiguity in CFG	Ambiguous grammar ⭐ Removal of ambiguity ⭐
Normal Forms	CNF ⭐ GNF ⭐
Pushdown Automata	PDA definition ⭐ CFG ↔ PDA ⭐
Context-Free Languages	Properties ⭐ Pumping Lemma for CFL ⭐
Turing Machine	TM model ⭐ Design examples ⭐
Variants of TM	Multi-tape TM ⭐ Non-deterministic TM ⭐
Decidability	Decidable languages ⭐ Undecidable problems ⭐
Halting Problem	Statement ⭐ Proof idea ⭐
Reducibility	Mapping reduction ⭐ Applications ⭐
Chomsky Hierarchy	Type 0 ⭐ Type 1 ⭐ Type 2 ⭐ Type 3 ⭐
Complexity Basics	Time complexity ⭐ Space complexity ⭐
P and NP	P class ⭐ NP class ⭐ NP-Complete ⭐