We now have a lot of evidence that there are languages that are not in
the class of CFLs.
So, we want ways to be able to tell the difference.
When we studied regular languages, we developed two tools to help us
tell if a language is regular or not.
One was closure properties on regular languages, that could help us
both to prove in some cases that a language is regular, and could help
us to prove in other cases that a language is not regular.
In a similar way, there exist closure properties for CFLs, and so we
can use these properties in appropriate cases both to prove a language
is a CFL, and also prove that other languages are not CFL.
We used a pumping lemma for regular languages to prove that
certain languages are not regular (because they could not be pumped).
Likewise, we will see that there is a pumping lemma for CFLs (though
it is somewhat different from the pumping lemma for regular
languages), and that it can be used to prove that certain languages
are not a CFL.
8.1.2. Closure Properties for Context-Free Languages¶
For regular languages, we developed a pumping lemma that can help us prove that a language is not regular. While we can't use the same pumping lemma for CFLs, we will see that there is a similar argument to be made that will lead to a CFL pumping lemma that we can make use of to prove certain languages are not CFL.
Prove that the following language is not a CFL: $L = \{w{\bar w}w : w\in \Sigma^*\},\ \Sigma = \{a, b\}$, where $\bar w$ is the string $w$ with each occurence of $a$ replaced by $b$ and each occurence of $b$ replaced by $a$.
