a. Use the languages A = {ambncn|m, n ≥ 0} and B = {anbncm|m, n ≥ 0} together with Example 2.36 to show that the class of context-free languages is not closed under intersection.
b. Use part (a) and DeMorgan’s law (Theorem 0.20) to show that the class of context-free languages is not closed under complementation.
Example 2.36
Use the pumping lemma to show that the language B = {anbncn| n ≥ 0} is not context free.
We assume that B is a CFL and obtain a contradiction. Let p be the pumping length for B that is guaranteed to exist by the pumping lemma. Select the string s = apbpcp. Clearly s is a member of B and of length at least p. The pumping lemma states that s can be pumped, but we show that it cannot. In other words, we show that no matter how we divide s into uvxyz, one of the three conditions of the lemma is violated.
First, condition 2 stipulates that eithter v or y is nonempty. Then we consider one of two cases, depending on wether substrings v and contain more than onw type of alphabet symbol.
