Context-free languages formulas

Context-free languages: closure properties and the pumping lemma. 2 formulas for GATE CS Theory of Computation, each with when to use it. Each is explained in the topic notes.

All 2 Context-free languages formulas

INTERSECTION WITH A REGULAR LANGUAGE

L CFL, R regular \Rightarrow L \cap R is a CFL

Proved by running a PDA and a DFA together; the same holds for DCFLs. Hence $L - R = L \cap \overline{R}$ is a CFL, but $R - L$ need not be.

PUMPING LEMMA FOR CONTEXT-FREE LANGUAGES

L CFL \Rightarrow \exists p \geq 1 \forall z \in L with ∣ z ∣ \geq p \exists u, v, w, x, y : z = uv w x y, ∣ v w x ∣ \leq p, ∣ v x ∣ \geq 1, u v^{i} w x^{i} y \in L for all i \geq 0

A necessary condition only: it can prove a language is not context-free, never that it is. If L is generated by a Chomsky normal form grammar with k variables, $p = 2^{k}$ works.

Where this was asked: 2018 (1), 2020 (2), 2022 (2), 2025 (2), 2026 (1). See the 8 previous-year questions on Context-free languages. This shows what was asked, not what will be asked.

KEEP GOING

Context-free languages: the notes and 8 solved previous-year questions