a. Use the languages A = {a^mbⁿcⁿ|m, n ≥ 0} and B = {aⁿbⁿc^m|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 = {aⁿbⁿcⁿ| 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.