Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/ii/paper-3/4h/b/solution

The context-free languages and have context-free grammars , , , and , , , respectively.
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!