8.1. Ways to Prove that a Language is not a Context-Free Language¶
8.1.1. Introduction¶
We now have a lot of evidence that there are languages that are not in the class of CFLs. So, just like we have ways to prove whether a language is regular or not, we now would like to find ways to prove whether a language is context-free or not. When we studied regular languages, we developed two tools to help us tell whether a language is regular. One was closure properties on regular languages. Used correctly, they could help us both to prove that languages are regular and to prove that they are not rebular. In particular, we can prove that a language is regular by generating it from known regular languages operated on by closed properties. And, we could prove that a language is not regular by operating on it using known regular languages and known closed properties to generate a known non-regular language.
In a similar way, there exist closure properties for CFLs. And so we can use these properties in appropriate cases both to prove that a certain language is CFL, and also to prove that other languages are not CFL.
We used a pumping lemma for regular languages to prove that certain languages are not regular (because we were able to prove that 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 this pumping lemma for CFLs can be used to prove that certain languages are not CFL.
8.1.3. A Pumping Lemma for Context-Free Languages¶
As an example, consider the language \(L = a^nb^n\). The string \(a^mb^m\) for any \(m\) can be decomposed such that \(u = a^{m-1}\), \(v = a\), \(x = \lambda\), \(x = b\), and \(z = b^{m-1}\). Clearly, the last \(a\) and first \(b\) in the string can be pumped an arbitrary number of times such that they are each pumped the same amount of times. In terms of the PDA, this means an arbitrary number of \(a\)’s can be put onto the stack and then matched to an equal number of \(b\)’s.
8.1.4. Using the CFL Pumping Lemma to Prove a Language Not CFL: Example 1¶
We were able to use the pumping lemma for regular languages to prove that a language is not regular by showing that it did not obey the pumping lemma. In a similar way, we can prove that a language is not a CFL by showing that it does not obey the CFL pumping lemma.
The pumping lemma implies that a CFL can include strings that must coordinate the behavior of two of its parts. This is a frequent idiom in CFG productions (such as \(S \rightarrow aSb\)), and it fits the concept of loading and then later unloading a stack. But at the same time, we can see from the pumping lemma’s formulation that requiring the coordination of three parts is impossible. So it should be no surprise that \(L = \{a^nb^nc^n : n \ge 1\}\) is not a CFL. This intuition is presented formally in our first example of a CFL pumping lemma proof.
