CFLs: Non-Closure Properties

Hello! Welcome back to our journey through the Theory of Computation.

In our last lesson, we established that the class of Context-Free Languages (CFLs) is closed under the regular operations: union, concatenation, and Kleene star. We saw how to constructively combine grammars to create new ones for the resulting languages. As previewed, this might suggest that CFLs behave just like regular languages in terms of closure. Today, we'll discover that this is not the case.

This lesson directly addresses the learning outcome: Prove that CFLs are not closed under intersection and complement using counterexamples. We will formalize the intuition we touched upon last time and use a classic non-CFL, ${a^{n} b^{n} c^{n}}$ , as the centerpiece of our proof. This will highlight a crucial difference between the computational power of finite automata and pushdown automata.

Recapping the Strategy

Remember that closure properties are about classes of languages.

To prove a class is closed under an operation, we must show that for any languages in the class, applying the operation yields a language also in the class. This requires a general construction, like we did for union.
To prove a class is not closed, we only need to find one single counterexample—a specific case where applying the operation to languages in the class produces a language that falls outside the class.

Let's begin with intersection.

1. Non-Closure Under Intersection

The strategy is to find two languages, $L_{1}$ and $L_{2}$ , that are both demonstrably context-free, but whose intersection, $L_{1} \cap L_{2}$ , is a language we know is not context-free.

To get an intuitive walkthrough of the proof, please watch the following segment from the Easy Theory video we saw last time.

Closure Properties of Context-Free Languages

This video segment explains the non-closure of CFLs under intersection. It presents the standard counterexample and clearly explains why the intersection results in a non-CFL.

Please watch the segment on intersection, which runs from 08:41 to 11:26. Focus on the choice of the two CFLs and how their intersection forces a property that a PDA cannot handle.

Now, let's formalize the argument presented in the video.

The Counterexample

Consider the following two languages over the alphabet $Σ = {a, b, c}$ :

$L_{1} = {a^{n} b^{n} c^{m} ∣ n, m \geq 0}$
- This language consists of strings with some number of 'a's, followed by an equal number of 'b's, followed by any number of 'c's.
$L_{2} = {a^{m} b^{n} c^{n} ∣ m, n \geq 0}$
- This language consists of strings with any number of 'a's, followed by some number of 'b's, followed by an equal number of 'c's.

Step 1: Prove $L_{1}$ and $L_{2}$ are Context-Free

We can easily construct CFGs for both, proving they are CFLs.

For $L_{1} = {a^{n} b^{n} c^{m}}$ , we can generate the ${a^{n} b^{n}}$ part and the ${c^{m}}$ part independently and concatenate them.

Let a grammar component $A \to a A b ∣ ϵ$ generate strings of the form $a^{n} b^{n}$ .
Let a grammar component $C \to c C ∣ ϵ$ generate strings of the form $c^{m}$ .
A start symbol $S \to A C$ combines them.

Similarly, for $L_{2} = {a^{m} b^{n} c^{n}}$ , a grammar with rules $S \to A C$ , $A \to a A ∣ ϵ$ , and $C \to b C c ∣ ϵ$ would work. Since we can build a CFG for each, $L_{1}$ and $L_{2}$ are both CFLs.

The following image provides a clear visual summary of this step.

Non-Closure of Context-Free Languages Under Intersection — This image shows the grammars for two context-free languages, L1 and L2. It then illustrates that their intersection, L1 ∩ L2, is the language {aⁿbⁿcⁿ}, which is known to be not context-free.

Step 2: Determine the Intersection

A string $w$ is in $L_{1} \cap L_{2}$ if and only if it belongs to both languages.

For $w$ to be in $L_{1}$ , the number of 'a's must equal the number of 'b's.
For $w$ to be in $L_{2}$ , the number of 'b's must equal the number of 'c's.

For a string to satisfy both conditions simultaneously, the number of 'a's must equal the number of 'b's, and the number of 'b's must equal the number of 'c's. This means the number of 'a's, 'b's, and 'c's must all be equal.

Therefore, $L_{1} \cap L_{2} = {a^{n} b^{n} c^{n} ∣ n \geq 0}$ .

Step 3: Conclude the Proof

From our lesson on the Pumping Lemma for CFLs, we have formally proven that ${a^{n} b^{n} c^{n} ∣ n \geq 0}$ is not a context-free language.

Since we have found two CFLs ( $L_{1}$ and $L_{2}$ ) whose intersection is not a CFL, we have our counterexample.
Conclusion: The class of context-free languages is not closed under intersection.

Test your understanding!

When proving that regular languages are closed under intersection, we used a "product construction" to simulate two DFAs in parallel. Why can't we use a similar product construction to simulate two PDAs, say $P_1$ and $P_2$, in parallel to prove closure for CFLs? What is the fundamental obstacle?

Show answer

The fundamental obstacle is the **stack**. A product construction would involve creating a new state that is a pair of states, one from $P_1$ and one from $P_2$. This works for the finite state control. However, both $P_1$ and $P_2$ need their own independent stacks to work correctly. For example, $P_1$ might need to push a symbol 'X' while $P_2$ needs to push 'Y', or $P_1$ might need to pop a symbol while $P_2$ does nothing. It's impossible for a single stack to simultaneously satisfy the potentially conflicting requirements of two independent PDAs.

2. Non-Closure Under Complementation

Now let's investigate complementation. We could try to find a specific CFL whose complement is not a CFL. However, there is a more elegant approach: a proof by contradiction that uses the result we just proved about intersection.

This proof relies on one of De Morgan's laws:
$L_{1} \cap L_{2} = L_{1} \cup L_{2}$

The following video segment explains how this identity is used to show non-closure under complement.

Closure Properties of Context-Free Languages

This final segment from the Easy Theory video provides a concise and brilliant proof by contradiction for why CFLs are not closed under complement.

Please watch from 11:26 to 13:20. Pay close attention to the chain of logic: if CFLs were closed under complement, what would that imply about their closure under intersection?

Let's formalize this powerful argument.

The Proof by Contradiction

Assumption: Assume, for the sake of contradiction, that the class of CFLs is closed under complementation. This means if $L$ is a CFL, then its complement $L$ must also be a CFL.
The Logic: Let $L_{1}$ and $L_{2}$ be any two CFLs.
- According to our assumption, their complements, $L_{1}$ and $L_{2}$ , must also be CFLs.
- From the previous lesson, we know CFLs are closed under union. Therefore, the union of $L_{1}$ and $L_{2}$ , which is $L_{1} \cup L_{2}$ , must be a CFL.
- Now, applying our assumption again: the complement of this resulting language, $L_{1} \cup L_{2}$ , must also be a CFL.
The Contradiction: By De Morgan's laws, $L_{1} \cup L_{2}$ is exactly the same as $L_{1} \cap L_{2}$ . The chain of reasoning above leads to the conclusion that if CFLs are closed under complement, they must also be closed under intersection.
However, we have just definitively proven that CFLs are not closed under intersection. This is a contradiction.
Conclusion: Our initial assumption must be false. Therefore, the class of context-free languages is not closed under complementation.

For a formal write-up of both proofs, you can refer to the following lecture notes.

Closure Properties

These lecture notes from the University of Illinois provide a concise and formal presentation of the proofs for non-closure under both intersection and complementation.

Please read the section titled '1.2 Intersection and Complementation'. It starts on the second page. This will reinforce the formal arguments we've just discussed.

Conclusion

In this lesson, we've established two critical limitations of context-free languages, distinguishing them from the simpler class of regular languages.

Key Takeaways:

CFLs are not closed under intersection. We proved this with a counterexample: $L_{1} = {a^{n} b^{n} c^{m}}$ and $L_{2} = {a^{m} b^{n} c^{n}}$ are both CFLs, but their intersection is the non-CFL ${a^{n} b^{n} c^{n}}$ .
CFLs are not closed under complementation. We proved this by contradiction, showing that if they were closed under complement, they would also have to be closed under intersection, which we know is false.
These properties highlight that the "memory" provided by a single stack is not powerful enough to handle computations that require comparing more than one independent count (like in ${a^{n} b^{n} c^{n}}$ ) or verifying the complex, unrestricted structure that can arise in a complement.

Preview of the Next Lesson:
We've spent a lot of time defining CFLs and exploring their properties. But a fundamental question remains: if I give you a CFG and a string, can you create an algorithm to determine if the string can be generated by the grammar? This is the membership problem. In the next lesson, we will explore a brilliant algorithm based on dynamic programming, the CYK algorithm (Cocke-Younger-Kasami), which solves this very problem.

Recommended resources