intersection of a CFL with a regular language

Two CFLs intersected can break out of the family, because that asks one stack to do two jobs. But mix a context-free language with a REGULAR one and the story is friendly again: the intersection L ∩ R, where L is context-free and R is regular, is ALWAYS context-free. The intuition is that a regular language needs no stack at all — a finite automaton has only finite memory — so adding its bookkeeping to a PDA costs the PDA nothing extra; the single stack is still free for the context-free part.

The construction is a product, just like the one for two finite automata, but applied to a PDA and a DFA. Run the PDA for L and the DFA for R side by side on the same input, in lockstep. Build a new PDA whose state is a PAIR (PDA-state, DFA-state); its single stack is the PDA's stack, untouched by the DFA half. On reading a symbol, the PDA half makes its stack move (push or pop) and the DFA half just updates its finite state. Accept only when BOTH halves accept. Because the DFA contributes no stack, one stack still suffices — so the result is a genuine PDA, hence its language is context-free.

This is one of the most useful tools in the whole field, both for design and for proofs. For design, you can carve a context-free language down by a regular filter — for example, keep only the balanced-parenthesis strings that ALSO have even length. For proofs, it is a workhorse for showing a language is NOT context-free: if you suspect L is not context-free, intersect it with a cleverly chosen regular language R to expose a simpler core (often something like a^n b^n c^n), then apply the pumping lemma to that core. If L were context-free, L ∩ R would have to be context-free too — and showing the core is not gives a clean contradiction.