Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/ii/paper-3/4h/b/solution
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 3 4H b Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-05
Their intersection is . Suppose satisfied the pumping lemma for context-free languages with length . In a decomposition with and , the window cannot meet both the and blocks. Pumping down changes at least one count and leaves at least one count unchanged. Thus the three counts are unequal, or the word order is invalid, contrary to the pumping lemma for context-free languages. Hence CFLs are not closed under intersection.
New to topics? Read the docs here!