Now, we'll discuss language operations. Just like for regular languages, we often want to perform operations on languages and we want to know whether, when applied to context-free languages, the result will also be context-free. As we'll see, there are some important differences with the regular languages.
First, we'll consider the basic regular operations. I already mentioned one of these in passing, but we'll state the result more formally (although we won't go through an entire formal proof).
Theorem. Let $L_A$ and $L_B$ be context-free languages. Then $L_A \cup L_B$, $L_A L_B$, and $L_A^*$ are context-free languages.
Proof. Since $L_A$ and $L_B$ are context-free languages, they are generated by context-free grammars. Let $G_A = (V_A, \Sigma, P_A, S_A$ and $G_B = (V_B, \Sigma, P_B, S_B)$ be context-free grammars such that $L(G_A) = L_A$ and $L(G_B) = L_B$.
First, we will show how to construct a CFG $G'$ for $L_A \cup L_B$. Let $G' = (V,\Sigma,P,S)$. Then $V = V_A \cup V_B \cup \{S\}$ and $P = P_A \cup P_B \cup \{S \to S_A \mid S_B\}$. Then any derivation in $G'$ will begin by applying either $S \Rightarrow S_A$ or $S \Rightarrow S_B$. Then, we have $S_A \Rightarrow w \in L_A$ and the same argument applies for $S_B$.
Next, we will show how to construct a CFG $G'$ for $L_A L_B$. Let $G' = (V,\Sigma,P,S)$. Then $V = V_A \cup V_B \cup \{S\}$ and $P = P_A \cup P_B \cup \{S \to S_A S_B\}$. Again, the first step in any derivation in $G'$ begins with $S \Rightarrow S_A S_B$. Since we know that $S_A \Rightarrow^* w_1 \in L_A$ and $S_B \Rightarrow^* w_2 \in L_B$, we have $S \Rightarrow^* w_1 w_2 \in L_A L_B$.
Finally, we will show how to construct a CFG for $L_A^*$. Let $G' = (V,\Sigma,P,S)$. Then $V = V_A \cup \{S\}$ and $P = P_A \cup \{S \to S S_A, S \to \varepsilon \}$. Consider a leftmost derivation in $G'$. It must begin with a finite number of applications of $S \to S S_A$. Then, to remove $S$ from the derivation, we must apply $S \to \varepsilon$. Therefore, the first few steps in any derivation will look something like \begin{align*} S &\Rightarrow^* \varepsilon \\ S &\Rightarrow^* SS_A \\ S &\Rightarrow^* S S_A S_A \\ S &\Rightarrow^* S S_A S_A S_A \\ &\vdots \end{align*}
Since $S_A \Rightarrow^* w \in L_A$, we can conclude that $G'$ generates $L_A^*$. $$\tag*{$\Box$}$$
We can get a fairly straightforward result for closure of context-free languages under reversal.
Proposition. Let $L \subseteq \Sigma$ be a context-free language. Then $L^R$ is a context-free language.
Proof. Since $L$ is context-free, there must be a CFG $G = (V,\Sigma,P,S)$ that generates it. We define a new CFG $G' (V,\Sigma,P',S)$, where the set of productions $P'$ is defined by $$P' = \{A \to \alpha^R \mid A \to \alpha \in P, A \in V, \alpha \in (V \cup \Sigma)^*\}.$$ That is, every production of $G'$ is a production of $G$ with the right hand side reversed. Then $L(G') = L(G)^R = L^R$ and thus, $L^R$ is context free. $$\tag*{$\Box$}$$
Here, we run into our first problem: we haven't shown yet that the CFLs are not closed under complementation. One immediate consequence of this is that we are not able to prove that the CFLs are closed under intersection using De Morgan's laws like we did for regular languages. Perhaps there is some other way of doing this? But first, we'll have a look at something easier.
Here, we'll show that CFLs are closed under intersection with a regular language. This might seem strange at first, but it turns out to be quite handy. We'll also get to make use of the fact that CFLs are recognized by PDAs.
Theorem. Let $L \subseteq \Sigma$ be a context-free language and let $R \subseteq \Sigma^*$ be a regular language. Then $L \cap R$ is a context-free language.
Proof. Let $A = (Q_A,\Sigma,\Gamma,\delta_A,s_A,Z_0,F_A)$ be a PDA that accepts $L$ and let $B = (Q_B, \Sigma, \delta_B, s_B, F_B)$ be a DFA that recognizes $R$. We will construct a PDA $C = (Q_C, \Sigma, \Gamma, \delta_C, s_C, Z_0, F_C)$ that recognizes $L \cap R$. We have
The PDA $C$ works by simultaneously moving through a computation of $A$ and $B$. When a transition is made, $C$ will keep track of the current state of $A$ via the first component of each state of $C$ and by using the stack as normal. The current state of $B$ is kept track of as the second component of the states of $C$. In addition, when $A$ makes $\varepsilon$-transitions, the state of $B$ does not change.
It is not too difficult to see that in this way, $C$ can move simultanenously through $A$ and $B$. Then, the set of accepting states of $C$ is defined to be pairs of states in $F_A$ and $F_B$. In other words, a word accepted by $C$ must have a computation that ends in a state $\langle p,q \rangle$ with $p \in F_A$ and $q \in F_B$. In other words, there is a computation for $w$ on $A$ that ends in a final state and there is a computation for $w$ on $B$ that ends in a final state. Thus, $C$ accepts $w$ if and only if $w$ is accepted by both $A$ and $B$ and this is only the case if and only if $w \in L \cap R$. Thus, $C$ is a PDA that accepts $L \cap R$ and $L \cap R$ is a context-free language. $$\tag*{$\Box$}$$
So how can we deploy this result? We can use it in much the same way that we used intersection with regular languages.
Proposition. Let $L = \{ w \in \{a,b,c\}^* \mid |w|_a = |w|_b = |w|_c \}$. Then $L$ is not context-free.
Proof. Suppose $L$ is a context-free language. Then it is closed under intersection with regular languages. However, consider the regular language $L(a^* b^* c^*)$ and $$L \cap L(a^* b^* c^*) = \{a^m b^m c^m \mid m \in \mathbb N \}.$$ This language is known to be not context-free. Therefore $L$ must not be context-free. $$\tag*{$\Box$}$$
Note that we can apply the same construction to two DFAs to get a DFA that recognizes the intersection of two regular languages. This is the alternate approach that I mentioned that one can take to show that regular languages are closed under intersection. For two DFAs, the construction is even simpler since we don't need to worry about the stack at all. This construction is called the cross-product construction, since we're essentially taking as our set of states the product of the two state sets.
Unfortunately, we can't use this construction to build a PDA for the intersection of two CFLs. A similar construction would require keeping track of two different stacks and it is unclear how one would manage this with only one stack.
As it turns out, the trouble with trying to simulate two PDAs simultaneously turned out to be prophetic and in fact, the context-free languages are not closed under intersection.
Theorem. There exist context-free languages $L_1, L_2 \subseteq \Sigma$ such that $L_1 \cap L_2$ is not a context-free language.
Proof. Let $L_1 = \{a^i b^i c^j \mid i,j \geq 0\}$ and let $L_2 = \{a^i b^j c^j \mid i,j \geq 0\}$. It is easy to see that $L_1$ and $L_2$ are both context-free. Consider for $\sigma_1, \sigma_2 \in \Sigma$ the languages \begin{align*} L_{\sigma_1,\sigma_2} = \{\sigma_1^m \sigma_2^m \mid m \geq 0 \}, \\ K_{\sigma_1} = \{\sigma_1^i \mid i \geq 0\}. \end{align*} We have already seen that $L_{\sigma_1,\sigma_2}$ is context-free and $K_{\sigma_1}$ is just $\sigma_1^*$, which is regular (and therefore, context-free). Since context-free languages are closed under concatenation, we have $L_1 = L_{a,b} K_c$ and $L_2 = K_a L_{b,c}$. Thus, $L_1$ and $L_2$ are context-free languages. Then, we have $$L_1 \cap L_2 = \{a^i b^i c^i \mid i \geq 0\}.$$ We have already shown that this language is not context-free. $$\tag*{$\Box$}$$
Thus, the class of context-free languages is not closed under intersection.
Now, we will show that the class of context-free languages is not closed under complementation.
Theorem. There exists a context-free languages $L$ such that $\overline L = \Sigma^* \setminus L$ is not a context-free language.
Proof. Let $L_1 = \{ a^i b^j c^k \mid i \neq j\} \cup \{a^i b^j c^k \mid j \neq k\}$ and let $L_2 = \overline{L(a^* b^* c^*})$. It is clear that $L_2$ is regular. To see that $L_1$ is context-free, we observe that we can write $$\{a^i b^j c^k \mid i \neq j\} = \left(\{ a^i b^j \mid i < j\} \cup \{a^i b^j \mid i > j\} \right) \{c^k \mid k \geq 0\}$$ and similarly, we have $$\{a^i b^j c^k \mid j \neq k\} = \{a^i \mid i \geq 0\} \left(\{ b^j c^k \mid j < k\} \cup \{b^j c^k \mid j > k\} \right).$$
Then $L = L_1 \cup L_2$ is a context-free language. However, observe that by DeMorgan's laws, we have $$\overline L = \overline{L_1 \cup L_2} = \overline{L_1} \cap \overline{L_2}.$$ First, we observe that $\overline L_2 = L(a^* b^* c^*)$ and therefore words of $\overline L$ must be of this form. Next, we recall that $\overline{L_1}$ consists of words that are not of the form $a^i b^j c^k$ with $i \neq j$ or $j \neq k$. In other words, if words of $L_1$ are of the form $a^i b^j c^k$, we must have $i = j = k$. But this means that $$\overline L = \overline{L_1} \cap \overline{L_2} = \{a^m b^m c^m \mid m \geq 0\}.$$ Of course, we have already seen that this language is not context-free. $$\tag*{$\Box$}$$
We have now reached the end of the first half of the course and everything about regular languages and context-free languages. From here, we will begin talking about the notion of computability in general. An interesting observation you may have noticed is that while $\{a^n \mid n \geq 0\}$ is accepted by a DFA, the language $\{a^n b^n \mid n \geq 0\}$ is not. And while a PDA can accept $\{a^n b^n \mid n \geq 0\}$, it can't accept $\{a^n b^n c^n \mid n \geq 0\}$. A natural question arises: can we play this game indefinitely? This is one of the things to keep in mind as we begin exploring the limits of computability.
Generally speaking, computability theory is about whether a particular problem can be solved or not. Depending on what you've assumed about computers so far, this statement may or may not be obvious to you, but it's another thing to have it proved.
Computability theory is really the beginnings of the entire field of computer science and to see why, we need to go all the way back to the late 20's to 30's. An ambition of the mathematical community at the time was to be able to axiomize all of mathematics. The idea is that such a task would enable the construction of a machine that when given a statement in first-order logic could answer whether it was true or not.
David Hilbert, in his famous speech in 1900, proposed 23 problems that he believed would be important in the following century. The second of these dealt with the axiomization of mathematics. Later, in 1928, he proposed the problem of finding an algorithm that would describe the operation of the hypothetical machine described above.
Formally, he was asking for a proof system that was:
As it turns out, in 1931, Kurt Gödel showed that no such system existed. Specifically, he showed that every sufficiently powerful system, the system is either incomplete or inconsistent. How powerful is sufficiently powerful? A proof system that deals with addition and multiplication of natural numbers is powerful enough to qualify.
Then, in 1936, Turing showed that we don't even have a system that is decidable. To do this, he tried to formalize the notion of computation into what we now know as a Turing machine.