IAE Academy

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.

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.