21 Limitations of CFL
% noend hides “end for”; drop it to keep them
In this chapter we see some techniques to show that a language is not context free and we will use them to show that \mathbf{CFL} is not closed under intersection and complement.
This page is still under development and will be updated during the course.
For regular languages, a prototypical example of language not in \mathbf{Regular} was \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n :n \in \mathbb{N}\}. For context-free languages, a prototypical example of language not in \mathbf{CFL} is \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^n :n \in \mathbb{N}\}.
Example 21.1 \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^n :n \in \mathbb{N}\}\notin \mathbf{CFL}.
We prove this by contradiction. Suppose L=\{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^n :n\in \mathbb{N}\}\in \mathbf{CFL} and let G a context-free grammar generating it. Since every context-free grammar can be put in Chomsky Normal Form (see Section 18.2) we can assume w.l.o.g. that G is in Chomsky Normal Form. The crucial point of having the grammar in Chomsky Normal Form is that the parse trees are binary trees. Hence, in particular, to generate a word w the parse tree must have depth at least \log_2|w|.
The idea of the argument is similar to the one for the regular languages: start with a very long word in L, which the grammar hence must generate, and show that we can construct another word not in L which G also generates.
Let N be the number of variables of G. Take the word z=\textcolor{darkred}{\mathtt{a}}^{2^N}\textcolor{darkred}{\mathtt{b}}^{2^N}\textcolor{darkred}{\mathtt{c}}^{2^N}. The parse tree for z must have depth at least \log_2|\textcolor{darkred}{\mathtt{a}}^{2^N}\textcolor{darkred}{\mathtt{b}}^{2^N}\textcolor{darkred}{\mathtt{c}}^{2^N}|=\log_2(3\cdot 2^N)=N+\log_2 3>N+1. So there is a root-to-leaf path \pi in the tree mentioning at least N+1 variables. By the pigeonhole principle (see Section 2.2.1) since the grammar has only N variables, there must be a variable which appears in \pi at least twice. There might be more than one variable that repeats multiple times or one that repeats more than twice. Choose as repeated variable the first occurrence of a repetition in \pi scanning it from the leaf. Let A be this variable. The bottom-most occurrence of A and occurrence of A immediately before that in \pi give 3 trees inside the parse tree for z:
- the one rooted at the starting symbol (T_0);
- the one rooted at the bottom-most occurrence of A (T_2);
- the one rooted at the occurrence of A immediately before that (T_1).
This partitions z naturally into 5 parts, z=uvwxy:
- u and y are the parts of z belonging to T_0 but not T_1 (u at the left and y at the right);
- v and x are the parts of z belonging to T_1 but not T_2 (v at the left and x at the right);
- w is the part of z that belongs to T_2.
See Figure 21.1 below for a diagram representing T_0,T_1,T_2 and uvwxy.
Now, we can take the tree T_1 and place it at the root of T_2 over and over. This gives valid productions in G and for all i\in \mathbb N, uv^iwx^iy\in \mathscr{L}(G).
See Figure 21.2 and Figure 21.3 for a diagram representing the parsing tree resulting from i=0 and i=2.
What do we know about u,v,w,x,y? By the choice of A, the depth of T_1 is at most N and hence |vwx|\leq 2^N. Moreover, since the parsing tree is binary, T_1\neq T_2, which means |vx|\geq 1 since the grammar does not allow \varepsilon-productions (apart from S\ \boldsymbol{\to}\ \varepsilon) and the repeated variable cannot be S.
We can take i=0, that is the word uwy and show it cannot belong to L. Since |vwx|\leq 2^N this word cannot contain \textcolor{darkred}{\mathtt{a}}s, \textcolor{darkred}{\mathtt{b}}s, and \textcolor{darkred}{\mathtt{c}}s at the same time. Since a subword of \textcolor{darkred}{\mathtt{a}}^{2^N}\textcolor{darkred}{\mathtt{b}}^{2^N}\textcolor{darkred}{\mathtt{c}}^{2^N} that contains $s, \textcolor{darkred}{\mathtt{b}}s, and \textcolor{darkred}{\mathtt{c}} must contain all \textcolor{darkred}{\mathtt{b}}^{2^N} and some \textcolor{darkred}{\mathtt{a}}s and \textcolor{darkred}{\mathtt{c}}s, that is it must have length at leat 2+2^N>|vwx|. No matter what vwx is there is always at least one symbol \textcolor{darkred}{\mathtt{s}}\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}},\textcolor{darkred}{\mathtt{c}}\} not contained in vwx and hence modifying vwx into w will not change the \textcolor{darkred}{\mathtt{s}}^{2^N} part of z. But |vx|\geq 1, so going from vwx to w we removed at least one symbol different from \textcolor{darkred}{\mathtt{s}}. Hence it is impossible that uwy has the form \textcolor{darkred}{\mathtt{a}}^k\textcolor{darkred}{\mathtt{b}}^k\textcolor{darkred}{\mathtt{c}}^k for some k, that is uwy\notin L. Contradiction.
In the case of regular languages just from the fact that \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n :n \in \mathbb{N}\}\notin \mathbf{Regular} and using closure properties of regular languages we can obtain several results. Here we are in a similar situation. We can use the fact that \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^n :n \in \mathbb{N}\}\notin \mathbf{CFL} and closure properties of context-free languages to obtain several results (see Section 21.2 for more examples).
Exercise 21.1 Show that \{w\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}},\textcolor{darkred}{\mathtt{c}}\}^* :|w|_{\textcolor{darkred}{\mathtt{a}}}=|w|_{\textcolor{darkred}{\mathtt{b}}}=|w|_{\textcolor{darkred}{\mathtt{c}}}\}\notin \mathbf{CFL}.
Theorem 21.1 \mathbf{CFL} is not closed under intersection.
Theorem 21.2 \mathbf{CFL} is not closed under complement.
The proof of Theorem 21.2 does not explicitly provide an example of a context-free language whose complement is not context-free. An example of such a language is the complement of \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^n :n \in \mathbb{N}\} (see Exercise 22.1).
21.1 The Pumping Lemma for Context-Free Languages
The argument used to prove Example 21.1 can be abstracted to the following statement which is known as the pumping lemma for context-free languages. The proof in Example 21.1 constructs a pumping length n=2^N for this particular grammar; the abstract lemma packages this argument into an arbitrary pumping length n.
Lemma 21.1 (Pumping Lemma for CFL) Let L\subseteq \Sigma^*. If for every n\in \mathbb{N}, there exist a word z\in \Sigma^* s.t.
- |z|\geq n,
- z\in L, and
- for every u,v,w,x,y\in \Sigma^* s.t. z=uvwxy with |vwx|\leq n and |vx|\geq 1, there exists i\in \mathbb N s.t. uv^iwx^iy\notin L,
then L\notin \mathbf{CFL}.
As for the pumping lemma for regular languages (Lemma 14.1), the use of the pumping lemma for context-free languages is essentially describing a winning strategy for the following game. Given a language we want to prove is not context-free:
- the “adversary” picks n\in \mathbb N;
- we choose a word z\in L with |z|\geq n (as a function of n);
- the adversary chooses u,v,w,x,y s.t.
- z=uvwxy
- |vwx|\leq n
- |vx|\geq 1
- we choose i\in \mathbb N (as a function of n,u,v,w,x,y)
- if we prove that uv^iwx^iy\notin L we win (i.e. we proved L is not context-free).
Hence a “template” for a proof using the pumping lemma for context-free languages is as follow:
We prove that L is not context-free using the pumping lemma for context-free languages. Let n be the pumping-lemma constant. Consider the word z=..... We have that |z|\geq n and z\in L (this needs an argument, possibly trivial, but you need to check it). Given an arbitrary decomposition of z as z=uvwxy, with |vwx|\leq n and |vx|\geq 1, consider i=..... We prove that uv^iwx^iy\notin L (this needs an argument, usually quite non-trivial).
Example 21.2 As an example, see how the template is filled following the argument we saw for Example 21.1:
We prove that L is not context-free using the pumping lemma for context-free languages. Let n be the pumping-lemma contant. Consider the word z=\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^n. It is immediate to check that |z|\geq n and z\in L. Given an arbitrary decomposition of z as z=uvwxy, with |vwx|\leq n and |vx|\geq 1, consider i=0. We prove that uv^iwx^iy\notin L. Since |vwx|\leq n this word cannot mention \textcolor{darkred}{\mathtt{a}}s, \textcolor{darkred}{\mathtt{b}}s, and \textcolor{darkred}{\mathtt{c}}s at the same time. Since otherwise it must contain all copues of \textcolor{darkred}{\mathtt{b}}s and some \textcolor{darkred}{\mathtt{a}}s and \textcolor{darkred}{\mathtt{b}}s, that is it must have length at least n+2>|vwx|. No matter what vwx is there is always at least one symbol \textcolor{darkred}{\mathtt{s}}\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}},\textcolor{darkred}{\mathtt{c}}\} not mentioned in vwx and hence modifying vwx into w will not change the \textcolor{darkred}{\mathtt{s}}^n part of z. But |vx|\geq 1, so going from vwx to w we removed at least one symbol different from s. Hence it is impossible that uwy has the form \textcolor{darkred}{\mathtt{a}}^k\textcolor{darkred}{\mathtt{b}}^k\textcolor{darkred}{\mathtt{c}}^k for some k, that is uv^0wx^0y=uwy\notin L.
Although the overall structure is similar, usually applications of the pumping-lemma for context-free languages (Lemma 21.1) require a more detailed case analysis than the pumping lemma for regular languages (Lemma 14.1). This typically leads to quite “inelegant” proofs, and as in the case of regular languages often it is possible to prove the non-context-freeness of languages using closure properties and the known fact that some notable language is not context-free.
Exercise 21.2 Since L=\{\textcolor{darkred}{\mathtt{a}}^{n}\textcolor{darkred}{\mathtt{b}}^{n}:n\in \mathbb{N}\}\in \mathbf{CFL}, if we try to apply the Pumping Lemma for CFL to L we must fail, that is “adversary” has a way to win the game no matter our choices of w and i. Give a winning strategy for the adversary.
Exercise 21.3 Same question as Exercise 21.2 but for L=\{\textcolor{darkred}{\mathtt{a}}^{n}\textcolor{darkred}{\mathtt{b}}^{m}\textcolor{darkred}{\mathtt{c}}^{n+m}:n,m\in \mathbb{N}\}\in \mathbf{CFL}.
Exercise 21.4 Show that the following languages are not in \mathbf{CFL} using the Pumping Lemma for CFL (Lemma 21.1):
- \{\textcolor{darkred}{\mathtt{a}}^{2^n}:n\in \mathbb{N}\}
- \{\textcolor{darkred}{\mathtt{a}}^{n^2}:n\in \mathbb{N}\}
- \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^{2^n}:n\in \mathbb{N}\}
- \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^{n^2}:n\in \mathbb{N}\}
- \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^m\textcolor{darkred}{\mathtt{c}}^{nm}:n,m\in \mathbb{N}\}
- \{ww :w\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^*\}
21.2 Non context-freeness via closure properties
As for regular languages (see Section 14.2), it is often useful when proving that a given language is not context-free, to use closure properties of context-free languages (see Table 16.1).
Example 21.3 As an example let’s show that L=\{\textcolor{darkred}{\mathtt{a}}^n(\textcolor{darkred}{\mathtt{bc}})^n\textcolor{darkred}{\mathtt{c}}^n :n\in \mathbb{N}\}\notin \mathbf{CFL} using Example 21.1.
Towards a contradiction assume L\in \mathbf{CFL}.
Consider the homomorphism \sigma\colon \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}},\textcolor{darkred}{\mathtt{c}}\}^*\to \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}},\textcolor{darkred}{\mathtt{c}}\}^* given by \sigma(\textcolor{darkred}{\mathtt{a}})=\textcolor{darkred}{\mathtt{a}}, \sigma(\textcolor{darkred}{\mathtt{b}})=\textcolor{darkred}{\mathtt{bc}}, \sigma(\textcolor{darkred}{\mathtt{c}})=\textcolor{darkred}{\mathtt{c}}. Now, \sigma^{-1}(L)=\{w:\sigma(w)\in L\}\in \mathbf{CFL} and since \mathbf{CFL} is closed under intersection with regular languages then \sigma^{-1}(L)\cap \mathscr{L}(\textcolor{darkred}{\mathtt{a}}^*\textcolor{darkred}{\mathtt{b}}^*\textcolor{darkred}{\mathtt{c}}^*)\in \mathbf{CFL}. But on the other hand we have that
\sigma^{-1}(L)\cap \mathscr{L}(\textcolor{darkred}{\mathtt{a}}^*\textcolor{darkred}{\mathtt{b}}^*\textcolor{darkred}{\mathtt{c}}^*)=\{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^n :n\in \mathbb{N}\}\ , which we know by Example 21.1 is not in \mathbf{CFL}. Contradiction.
Exercise 21.5 Only using that \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^n :n\in \mathbb{N}\}\notin\mathbf{CFL} and the closure properties of \mathbf{CFL} show that the following languages are also not in \mathbf{CFL}:
- (🌱) \{\textcolor{darkred}{\mathtt{0}}^n\textcolor{darkred}{\mathtt{1}}^n\textcolor{darkred}{\mathtt{2}}^n :n\in \mathbb{N}\}
- \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^n :n\in \mathbb{N} \land n\geq 1\}
- \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^n\textcolor{darkred}{\mathtt{d}}^n :n\in \mathbb{N}\}
- \{\textcolor{darkred}{\mathtt{a}}^{2n}\textcolor{darkred}{\mathtt{b}}^n \textcolor{darkred}{\mathtt{c}}^n:n\in \mathbb{N}\}
- \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^n :n\in 2\mathbb{N}\}
- \{w\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}},\textcolor{darkred}{\mathtt{c}}\}^* :|w|_{\textcolor{darkred}{\mathtt{a}}} = |w|_{\textcolor{darkred}{\mathtt{b}}} = |w|_{\textcolor{darkred}{\mathtt{c}}}\}
21.3 Inherently ambiguous languages
Often, for context-free languages, we can provide a non-ambiguous grammar generating them. This is not always the case.
Theorem 21.3 Every CFG generating \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^m\textcolor{darkred}{\mathtt{c}}^m :n,m\in \mathbb{N}\}\cup \{\textcolor{darkred}{\mathtt{a}}^m\textcolor{darkred}{\mathtt{b}}^m\textcolor{darkred}{\mathtt{c}}^n :n,m\in \mathbb{N}\} is ambiguous.
Theorem 21.4 Every CFG generating \{\textcolor{darkred}{\mathtt{0}}^n\textcolor{darkred}{\mathtt{1}}^n\textcolor{darkred}{\mathtt{0}}^m\textcolor{darkred}{\mathtt{1}}^m :n,m\in \mathbb{N}\}\cup \{\textcolor{darkred}{\mathtt{0}}^n\textcolor{darkred}{\mathtt{1}}^m\textcolor{darkred}{\mathtt{0}}^m\textcolor{darkred}{\mathtt{1}}^n :n,m\in \mathbb{N}\} is ambiguous.
These results above justify the existence of the class of all inherently ambiguous context-free languages, that is all context-free languages with the property that every CFG generating them is ambiguous.
Figure 4.2 shows how the inherently ambiguous CFL fit w.r.t. other classes of languages.
Exercise 21.6 Show that DCFL is not contained into the inherently ambiguous CFL, and viceversa.
We do not prove Theorem 21.3 nor Theorem 21.4, but we only mention that they both can be proved using a generalization of Lemma 21.1 known as the Ogden Lemma, which (informally) allows to select zones to pump.