CFG & PDA formulas
Context-free grammars and push-down automata. 3 formulas for GATE CS Theory of Computation, each with when to use it. Each is explained in the topic notes.
IAE Academy: Context-free grammars and push-down automata formulas (GATE CS)
All 3 CFG & PDA formulas
DERIVATION LENGTH IN CHOMSKY NORMAL FORM
For and any derivation of from in a CNF grammar: steps use and steps use . In the parse tree there are variable nodes with two variable children and variable nodes whose only child is a terminal leaf, so variable nodes, one per step.
DERIVATION LENGTH IN GREIBACH NORMAL FORM
For ; each step adds exactly one terminal.
EQUIVALENCE OF CFGS AND PDAS
Every CFG has an equivalent NPDA and every NPDA has an equivalent CFG, with either acceptance mode.
Where this was asked: 2023 (2), 2024 (2), 2025 (2), 2026 (3). See the 9 previous-year questions on CFG & PDA. This shows what was asked, not what will be asked.